Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs @ 6851

Last change on this file since 6851 was 6851, checked in by svonolfe, 13 years ago

Added support for multi depot CVRP instances (#1177)

File size: 5.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Problems.VehicleRouting.Interfaces;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Core;
29using HeuristicLab.Parameters;
30using HeuristicLab.Data;
31using HeuristicLab.Optimization;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Problems.VehicleRouting.Variants;
34using HeuristicLab.Problems.VehicleRouting.Encodings;
35using HeuristicLab.Common;
36
37namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
38  [Item("CVRPEvaluator", "Represents a single depot CVRP evaluator.")]
39  [StorableClass]
40  public class CVRPEvaluator: VRPEvaluator {
41    public ILookupParameter<DoubleValue> OverloadParameter {
42      get { return (ILookupParameter<DoubleValue>)Parameters["Overload"]; }
43    }
44
45    protected override VRPEvaluation CreateTourEvaluation() {
46      return new CVRPEvaluation();
47    }
48
49    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour, IVRPEncoding solution) {
50      TourInsertionInfo tourInfo = new TourInsertionInfo();
51      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
52     
53      IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
54      DoubleArray demand = instance.Demand;
55
56      double delivered = 0.0;
57      double overweight = 0.0;
58      double distance = 0.0;
59
60      double capacity = cvrpInstance.Capacity.Value;
61      for (int i = 0; i <= tour.Stops.Count; i++) {
62        int end = 0;
63        if (i < tour.Stops.Count)
64          end = tour.Stops[i];
65
66        delivered += demand[end];
67      }
68
69      double spareCapacity = capacity - delivered;
70
71      //simulate a tour, start and end at depot
72      for (int i = 0; i <= tour.Stops.Count; i++) {
73        int start = 0;
74        if (i > 0)
75          start = tour.Stops[i - 1];
76        int end = 0;
77        if (i < tour.Stops.Count)
78          end = tour.Stops[i];
79
80        //drive there
81        double currentDistace = instance.GetDistance(start, end, solution);
82        distance += currentDistace;
83
84        CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
85        tourInfo.AddStopInsertionInfo(stopInfo);
86      }
87
88      eval.Quality += instance.FleetUsageFactor.Value;
89      eval.Quality += instance.DistanceFactor.Value * distance;
90
91      eval.Distance += distance;
92      eval.VehicleUtilization += 1;
93
94      if (delivered > capacity) {
95        overweight = delivered - capacity;
96      }
97
98      (eval as CVRPEvaluation).Overload += overweight;
99      double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
100      eval.Penalty += penalty;
101      eval.Quality += penalty;
102      tourInfo.Penalty = penalty;
103    }
104
105    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, IVRPEncoding solution, TourInsertionInfo tourInsertionInfo, int index, int customer,
106      out bool feasible) {
107      CVRPInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPInsertionInfo;
108     
109      double costs = 0;
110      feasible = tourInsertionInfo.Penalty < double.Epsilon;
111
112      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
113      double overloadPenalty = cvrp.OverloadPenalty.Value;
114
115      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End, solution);
116      double newDistance =
117        instance.GetDistance(insertionInfo.Start, customer, solution) +
118        instance.GetDistance(customer, insertionInfo.End, solution);
119      costs += instance.DistanceFactor.Value * (newDistance - distance);
120
121      double demand = instance.Demand[customer];
122      if (demand > insertionInfo.SpareCapacity) {
123        feasible = false;
124
125        if(insertionInfo.SpareCapacity >= 0)
126          costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
127        else
128          costs += demand * overloadPenalty;
129      }
130     
131      return costs;
132    }
133
134    protected override void InitResultParameters() {
135      base.InitResultParameters();
136
137      OverloadParameter.ActualValue = new DoubleValue(0);
138    }
139
140    protected override void SetResultParameters(VRPEvaluation tourEvaluation) {
141      base.SetResultParameters(tourEvaluation);
142
143      OverloadParameter.ActualValue.Value = (tourEvaluation as CVRPEvaluation).Overload;
144    }
145   
146    [StorableConstructor]
147    protected CVRPEvaluator(bool deserializing) : base(deserializing) { }
148
149    public CVRPEvaluator() {
150      Parameters.Add(new LookupParameter<DoubleValue>("Overload", "The overload."));
151    }
152
153    public override IDeepCloneable Clone(Cloner cloner) {
154      return new CVRPEvaluator(this, cloner);
155    }
156
157    protected CVRPEvaluator(CVRPEvaluator original, Cloner cloner)
158      : base(original, cloner) {
159    }
160  }
161}
Note: See TracBrowser for help on using the repository browser.