Changeset 6752 for branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4
- Timestamp:
- 09/13/11 16:00:19 (13 years ago)
- Location:
- branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4
- Files:
-
- 15 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs
r6713 r6752 38 38 39 39 #region IVRPEncoding Members 40 public virtual List<Tour> GetTours() { 41 List<Tour> result = new List<Tour>(); 42 43 foreach(Tour tour in Tours) { 44 if (tour.Stops.Count > 0) 45 result.Add(tour.Clone() as Tour); 40 public void Repair() { 41 List<Tour> toBeRemoved = new List<Tour>(); 42 foreach (Tour tour in Tours) { 43 if (tour.Stops.Count == 0) 44 toBeRemoved.Add(tour); 46 45 } 47 46 48 while (result.Count > ProblemInstance.Vehicles.Value) { 49 Tour tour = result[result.Count - 1]; 50 result[result.Count - 2].Stops.AddRange(tour.Stops); 47 foreach (Tour tour in toBeRemoved) 48 Tours.Remove(tour); 51 49 52 result.Remove(tour); 53 } 50 while (Tours.Count > ProblemInstance.Vehicles.Value) { 51 Tour tour = Tours[Tours.Count - 1]; 52 Tours[Tours.Count - 2].Stops.AddRange(tour.Stops); 54 53 55 return result; 54 Tours.Remove(tour); 55 } 56 } 57 58 public virtual List<Tour> GetTours() { 59 Repair(); 60 61 List<Tour> result = new List<Tour>(); 62 foreach (Tour tour in Tours) 63 result.Add(tour.Clone() as Tour); 64 65 return result; 56 66 } 57 67 -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs
r6710 r6752 156 156 return false; 157 157 158 bool bestFeasible = false; 158 if (tour.Stops.Count == 0) { 159 place = 0; 160 return true; 161 } 162 159 163 double minDetour = 0; 160 161 164 VRPEvaluation eval = ProblemInstance.Evaluate(tour); 162 double length = eval.Quality; 165 bool originalFeasible = ProblemInstance.Feasible(eval); 166 163 167 for (int i = 0; i <= tour.Stops.Count; i++) { 164 tour.Stops.Insert(i, city); 165 166 eval = ProblemInstance.Evaluate(tour); 167 bool feasible = ProblemInstance.Feasible(eval); 168 169 if (feasible || allowInfeasible && !bestFeasible) { 170 double newLength = eval.Quality; 171 double detour = newLength - length; 172 173 if (place < 0 || detour < minDetour || feasible && !bestFeasible) { 168 bool feasible; 169 double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible); 170 if (feasible || allowInfeasible) { 171 if (place < 0 || detour < minDetour) { 174 172 place = i; 175 173 minDetour = detour; 176 177 if (feasible)178 bestFeasible = true;179 174 } 180 175 } 181 182 tour.Stops.RemoveAt(i);183 176 } 184 177 … … 248 241 249 242 int place = -1; 250 if (FindRouteInsertionPlace(childTour, city, allowInfeasible, out place)) { 243 bool found = FindRouteInsertionPlace(childTour, city, allowInfeasible, out place); 244 if (found) { 251 245 childTour.Stops.Insert(place, city); 252 246 -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs
r6710 r6752 39 39 public List<int> Unrouted { get; set; } 40 40 41 [Storable]42 public double PenaltyFactor { get; set; }43 44 41 public PotvinEncoding(IVRPProblemInstance instance) 45 42 : base(instance) { 46 43 Unrouted = new List<int>(); 47 PenaltyFactor = 1;48 44 } 49 45 … … 60 56 : base(original, cloner) { 61 57 this.Unrouted = new List<int>(original.Unrouted); 62 this.PenaltyFactor = original.PenaltyFactor;63 58 } 64 59 … … 87 82 double minQuality = -1; 88 83 84 VRPEvaluation eval = ProblemInstance.Evaluate(tour); 85 89 86 for (int i = 0; i <= tour.Stops.Count; i++) { 90 tour.Stops.Insert(i, city); 91 92 VRPEvaluation eval = ProblemInstance.Evaluate(tour); 93 double quality = eval.Quality + eval.Penalty * (PenaltyFactor - 1.0); 94 87 bool feasible; 88 double quality = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible); 95 89 if (place < 0 || quality < minQuality) { 96 90 place = i; 97 91 minQuality = quality; 98 92 } 99 100 tour.Stops.RemoveAt(i);101 93 } 102 94 … … 110 102 route = -1; 111 103 place = -1; 112 bool bestFeasible = false;113 104 double minDetour = double.MaxValue; 105 106 VRPEvaluation eval = ProblemInstance.Evaluate(this); 107 bool originalFeasible = ProblemInstance.Feasible(eval); 114 108 115 109 for (int tour = 0; tour < Tours.Count; tour++) { 116 110 if (tour != routeToAvoid) { 117 VRPEvaluation eval = ProblemInstance.Evaluate(Tours[tour]);118 111 double length = eval.Quality; 119 112 120 113 for (int i = 0; i <= Tours[tour].Stops.Count; i++) { 121 Tours[tour].Stops.Insert(i, city); 122 123 eval = ProblemInstance.Evaluate(Tours[tour]); 124 bool feasible = ProblemInstance.Feasible(eval); 125 126 if (feasible || allowInfeasible && !bestFeasible) { 127 double newLength = eval.Quality; 128 double detour = newLength - length; 129 130 if (route < 0 || detour < minDetour || feasible && !bestFeasible) { 114 bool feasible; 115 double detour = ProblemInstance.GetInsertionCosts(eval, city, tour, i, out feasible); 116 117 if (feasible || allowInfeasible) { 118 if (route < 0 || detour < minDetour) { 131 119 route = tour; 132 120 place = i; 133 121 minDetour = detour; 134 135 if (feasible)136 bestFeasible = true;137 122 } 138 123 } 139 140 Tours[tour].Stops.RemoveAt(i);141 124 } 142 125 } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPEvaluator.cs
r4378 r6752 35 35 VRPEvaluation Evaluate(IVRPProblemInstance instance, Tour tour); 36 36 bool Feasible(VRPEvaluation evaluation); 37 double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible); 37 38 } 38 39 } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs
r6607 r6752 54 54 VRPEvaluation Evaluate(Tour tour); 55 55 bool Feasible(VRPEvaluation eval); 56 double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible); 56 57 } 57 58 } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluation.cs
r4454 r6752 24 24 using System.Linq; 25 25 using System.Text; 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 using HeuristicLab.Core; 28 using HeuristicLab.Common; 26 29 27 30 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances { 31 public class CVRPInsertionInfo : StopInsertionInfo { 32 private double spareCapacity; 33 34 public double SpareCapacity { 35 get { return spareCapacity; } 36 } 37 38 public CVRPInsertionInfo(int start, int end, double spareCapacity) 39 : base(start, end) { 40 this.spareCapacity = spareCapacity; 41 } 42 } 43 28 44 public class CVRPEvaluation: VRPEvaluation { 29 45 public double Overload { get; set; } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs
r4752 r6752 48 48 49 49 protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) { 50 TourInsertionInfo tourInfo = new TourInsertionInfo(); 51 eval.InsertionInfo.AddTourInsertionInfo(tourInfo); 52 50 53 IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance; 51 54 DoubleArray demand = instance.Demand; … … 54 57 double overweight = 0.0; 55 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; 56 70 57 71 //simulate a tour, start and end at depot … … 68 82 distance += currentDistace; 69 83 70 delivered += demand[end]; 84 CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity); 85 tourInfo.AddStopInsertionInfo(stopInfo); 71 86 } 72 87 … … 77 92 eval.VehicleUtilization += 1; 78 93 79 double capacity = cvrpInstance.Capacity.Value;80 94 if (delivered > capacity) { 81 95 overweight = delivered - capacity; … … 86 100 eval.Penalty += penalty; 87 101 eval.Quality += penalty; 102 tourInfo.Penalty = penalty; 103 } 104 105 protected override double GetTourInsertionCosts(IVRPProblemInstance instance, 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); 116 double newDistance = 117 instance.GetDistance(insertionInfo.Start, customer) + 118 instance.GetDistance(customer, insertionInfo.End); 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; 88 132 } 89 133 -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluation.cs
r6710 r6752 24 24 using System.Linq; 25 25 using System.Text; 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 using HeuristicLab.Common; 26 28 27 29 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances { 30 public class CVRPPDTWInsertionInfo : CVRPTWInsertionInfo { 31 private List<int> visited; 32 33 public List<int> Visited { 34 get { return visited; } 35 } 36 37 private double arrivalSpareCapacity; 38 39 public double ArrivalSpareCapacity { 40 get { return arrivalSpareCapacity; } 41 } 42 43 public CVRPPDTWInsertionInfo(int start, int end, double spareCapacity, double arrivalTime, double leaveTime, double spareTime, double waitingTime, List<int> visited, double arrivalSpareCapacity) 44 : base(start, end, spareCapacity, arrivalTime, leaveTime, spareTime, waitingTime) { 45 this.visited = visited; 46 this.arrivalSpareCapacity = arrivalSpareCapacity; 47 } 48 } 49 28 50 public class CVRPPDTWEvaluation: CVRPTWEvaluation { 29 51 public int PickupViolations { get; set; } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs
r6710 r6752 48 48 49 49 protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) { 50 TourInsertionInfo tourInfo = new TourInsertionInfo(); 51 eval.InsertionInfo.AddTourInsertionInfo(tourInfo); 52 50 53 IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance; 51 54 DoubleArray demand = instance.Demand; … … 86 89 distance += currentDistace; 87 90 91 double arrivalTime = time; 92 88 93 //check if it was serviced on time 89 94 if (time > dueTime[end]) … … 94 99 if (time < readyTime[end]) 95 100 currentWaitingTime = readyTime[end] - time; 101 102 double waitTime = readyTime[end] - time; 103 96 104 waitingTime += currentWaitingTime; 97 105 time += currentWaitingTime; 106 107 double spareTime = dueTime[end] - time; 98 108 99 109 //service … … 103 113 104 114 //Pickup / deliver 115 double arrivalSpareCapacity = capacity - currentLoad; 116 105 117 bool validPickupDelivery = 106 118 validPickupDelivery = … … 110 122 if (validPickupDelivery) { 111 123 currentLoad += demand[end]; 112 113 if (currentLoad > capacity)114 overweight += currentLoad - capacity;115 124 } else { 116 125 pickupViolations++; 117 126 } 127 128 if (currentLoad > capacity) 129 overweight += currentLoad - capacity; 130 131 double spareCapacity = capacity - currentLoad; 132 CVRPPDTWInsertionInfo stopInfo = new CVRPPDTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime, new List<int>(stops.Keys), arrivalSpareCapacity); 133 tourInfo.AddStopInsertionInfo(stopInfo); 118 134 119 135 stops.Add(end, true); … … 126 142 127 143 (eval as CVRPEvaluation).Overload += overweight; 144 double tourPenalty = 0; 128 145 double penalty = overweight * cvrpInstance.OverloadPenalty.Value; 129 146 eval.Penalty += penalty; 130 147 eval.Quality += penalty; 148 tourPenalty += penalty; 131 149 132 150 (eval as CVRPTWEvaluation).Tardiness += tardiness; … … 136 154 eval.Penalty += penalty; 137 155 eval.Quality += penalty; 156 tourPenalty += penalty; 138 157 139 158 (eval as CVRPPDTWEvaluation).PickupViolations += pickupViolations; 140 159 penalty = pickupViolations * pdp.PickupViolationPenalty.Value; 141 160 eval.Penalty += penalty; 161 tourPenalty += penalty; 142 162 143 163 eval.Quality += penalty; 144 164 eval.Quality += time * vrptw.TimeFactor.Value; 165 tourInfo.Penalty = tourPenalty; 166 } 167 168 protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, 169 out bool feasible) { 170 CVRPPDTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPPDTWInsertionInfo; 171 172 double costs = 0; 173 feasible = tourInsertionInfo.Penalty < double.Epsilon; 174 bool tourFeasible = true; 175 176 ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance; 177 double overloadPenalty = cvrp.OverloadPenalty.Value; 178 179 ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance; 180 DoubleArray dueTime = vrptw.DueTime; 181 DoubleArray readyTime = vrptw.ReadyTime; 182 DoubleArray serviceTimes = vrptw.ServiceTime; 183 double tardinessPenalty = vrptw.TardinessPenalty.Value; 184 185 IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance; 186 IntArray pickupDeliveryLocation = pdp.PickupDeliveryLocation; 187 double pickupPenalty = pdp.PickupViolationPenalty.Value; 188 189 double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End); 190 double newDistance = 191 instance.GetDistance(insertionInfo.Start, customer) + 192 instance.GetDistance(customer, insertionInfo.End); 193 costs += instance.DistanceFactor.Value * (newDistance - distance); 194 195 double demand = instance.Demand[customer]; 196 if (demand > insertionInfo.ArrivalSpareCapacity) { 197 tourFeasible = feasible = false; 198 if (insertionInfo.ArrivalSpareCapacity >= 0) 199 costs += (demand - insertionInfo.ArrivalSpareCapacity) * overloadPenalty; 200 else 201 costs += demand * overloadPenalty; 202 } 203 int destination = pickupDeliveryLocation[customer]; 204 205 bool validPickup = true; 206 if (demand < 0 && !insertionInfo.Visited.Contains(destination)) { 207 tourFeasible = feasible = false; 208 validPickup = false; 209 costs += pickupPenalty; 210 } 211 212 double time = 0; 213 double tardiness = 0; 214 215 if (index > 0) 216 time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime; 217 time += instance.GetDistance(insertionInfo.Start, customer); 218 if (time > dueTime[customer]) { 219 tardiness += time - dueTime[customer]; 220 } 221 if (time < readyTime[customer]) 222 time += readyTime[customer] - time; 223 time += serviceTimes[customer]; 224 time += instance.GetDistance(customer, insertionInfo.End); 225 226 double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime; 227 for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) { 228 CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo; 229 230 if (demand >= 0) { 231 if (nextStop.End == destination) { 232 demand = 0; 233 costs -= pickupPenalty; 234 if (tourInsertionInfo.Penalty == pickupPenalty && tourFeasible) 235 feasible = true; 236 } else if (nextStop.SpareCapacity < 0) { 237 costs += demand * overloadPenalty; 238 } else if (nextStop.SpareCapacity < demand) { 239 tourFeasible = feasible = false; 240 costs += (demand - nextStop.SpareCapacity) * overloadPenalty; 241 } 242 } else if (validPickup) { 243 if (nextStop.SpareCapacity < 0) { 244 costs += Math.Max(demand, nextStop.SpareCapacity) * overloadPenalty; 245 } 246 } 247 248 if (additionalTime < 0) { 249 //arrive earlier than before 250 //wait probably 251 if (nextStop.WaitingTime < 0) { 252 double wait = nextStop.WaitingTime - additionalTime; 253 if (wait > 0) 254 additionalTime += wait; 255 } else { 256 additionalTime = 0; 257 } 258 259 //check due date, decrease tardiness 260 if (nextStop.SpareTime < 0) { 261 costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty; 262 } 263 } else { 264 //arrive later than before, probably don't have to wait 265 if (nextStop.WaitingTime > 0) { 266 additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime); 267 } 268 269 //check due date 270 if (nextStop.SpareTime > 0) { 271 double spare = nextStop.SpareTime - additionalTime; 272 if (spare < 0) 273 tardiness += -spare; 274 } else { 275 tardiness += additionalTime; 276 } 277 } 278 } 279 280 costs += additionalTime * vrptw.TimeFactor.Value; 281 282 if (tardiness > 0) { 283 tourFeasible = feasible = false; 284 } 285 286 costs += tardiness * tardinessPenalty; 287 288 return costs; 145 289 } 146 290 -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluation.cs
r4454 r6752 24 24 using System.Linq; 25 25 using System.Text; 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 using HeuristicLab.Common; 26 28 27 29 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances { 30 public class CVRPTWInsertionInfo : CVRPInsertionInfo { 31 private double arrivalTime; 32 33 public double ArrivalTime { 34 get { return arrivalTime; } 35 } 36 37 private double leaveTime; 38 39 public double LeaveTime { 40 get { return leaveTime; } 41 } 42 43 private double spareTime; 44 45 public double SpareTime { 46 get { return spareTime; } 47 } 48 49 private double waitingTime; 50 51 public double WaitingTime { 52 get { return waitingTime; } 53 } 54 55 public CVRPTWInsertionInfo(int start, int end, double spareCapacity, double arrivalTime, double leaveTime, double spareTime, double waitingTime) 56 : base(start, end, spareCapacity) { 57 this.arrivalTime = arrivalTime; 58 this.leaveTime = leaveTime; 59 this.spareTime = spareTime; 60 this.waitingTime = waitingTime; 61 } 62 } 63 28 64 public class CVRPTWEvaluation: CVRPEvaluation { 29 65 public double Tardiness { get; set; } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs
r4752 r6752 52 52 53 53 protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) { 54 TourInsertionInfo tourInfo = new TourInsertionInfo(); 55 eval.InsertionInfo.AddTourInsertionInfo(tourInfo); 56 54 57 IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance; 55 58 DoubleArray demand = instance.Demand; … … 67 70 double overweight = 0.0; 68 71 double distance = 0.0; 72 73 double capacity = cvrpInstance.Capacity.Value; 74 for (int i = 0; i <= tour.Stops.Count; i++) { 75 int end = 0; 76 if (i < tour.Stops.Count) 77 end = tour.Stops[i]; 78 79 delivered += demand[end]; 80 } 81 82 double spareCapacity = capacity - delivered; 69 83 70 84 //simulate a tour, start and end at depot … … 82 96 distance += currentDistace; 83 97 98 double arrivalTime = time; 99 84 100 //check if it was serviced on time 85 101 if (time > dueTime[end]) … … 90 106 if (time < readyTime[end]) 91 107 currentWaitingTime = readyTime[end] - time; 108 109 double waitTime = readyTime[end]-time; 110 92 111 waitingTime += currentWaitingTime; 93 112 time += currentWaitingTime; 113 114 double spareTime = dueTime[end] - time; 94 115 95 116 //service … … 97 118 serviceTime += currentServiceTime; 98 119 time += currentServiceTime; 99 delivered += demand[end]; 120 121 CVRPTWInsertionInfo stopInfo = new CVRPTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime); 122 tourInfo.AddStopInsertionInfo(stopInfo); 100 123 } 101 124 … … 105 128 eval.VehicleUtilization += 1; 106 129 107 double capacity = cvrpInstance.Capacity.Value;108 130 if (delivered > capacity) { 109 131 overweight = delivered - capacity; … … 111 133 112 134 (eval as CVRPEvaluation).Overload += overweight; 135 double tourPenalty = 0; 113 136 double penalty = overweight * cvrpInstance.OverloadPenalty.Value; 114 137 eval.Penalty += penalty; 115 138 eval.Quality += penalty; 139 tourPenalty += penalty; 116 140 117 141 (eval as CVRPTWEvaluation).Tardiness += tardiness; … … 121 145 eval.Penalty += penalty; 122 146 eval.Quality += penalty; 147 tourPenalty += penalty; 123 148 eval.Quality += time * vrptw.TimeFactor.Value; 149 tourInfo.Penalty = tourPenalty; 150 } 151 152 protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, 153 out bool feasible) { 154 CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo; 155 156 double costs = 0; 157 feasible = tourInsertionInfo.Penalty < double.Epsilon; 158 159 ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance; 160 double overloadPenalty = cvrp.OverloadPenalty.Value; 161 162 ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance; 163 DoubleArray dueTime = vrptw.DueTime; 164 DoubleArray readyTime = vrptw.ReadyTime; 165 DoubleArray serviceTimes = vrptw.ServiceTime; 166 double tardinessPenalty = vrptw.TardinessPenalty.Value; 167 168 double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End); 169 double newDistance = 170 instance.GetDistance(insertionInfo.Start, customer) + 171 instance.GetDistance(customer, insertionInfo.End); 172 costs += instance.DistanceFactor.Value * (newDistance - distance); 173 174 double demand = instance.Demand[customer]; 175 if (demand > insertionInfo.SpareCapacity) { 176 feasible = false; 177 if (insertionInfo.SpareCapacity >= 0) 178 costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty; 179 else 180 costs += demand * overloadPenalty; 181 } 182 183 double time = 0; 184 double tardiness = 0; 185 186 if (index > 0) 187 time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime; 188 time += instance.GetDistance(insertionInfo.Start, customer); 189 if (time > dueTime[customer]) { 190 tardiness += time - dueTime[customer]; 191 } 192 if (time < readyTime[customer]) 193 time += readyTime[customer] - time; 194 time += serviceTimes[customer]; 195 time += instance.GetDistance(customer, insertionInfo.End); 196 197 double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime; 198 for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) { 199 CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo; 200 201 if (additionalTime < 0) { 202 //arrive earlier than before 203 //wait probably 204 if (nextStop.WaitingTime < 0) { 205 double wait = nextStop.WaitingTime - additionalTime; 206 if (wait > 0) 207 additionalTime += wait; 208 } else { 209 additionalTime = 0; 210 } 211 212 //check due date, decrease tardiness 213 if (nextStop.SpareTime < 0) { 214 costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty; 215 } 216 } else { 217 //arrive later than before, probably don't have to wait 218 if (nextStop.WaitingTime > 0) { 219 additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime); 220 } 221 222 //check due date 223 if (nextStop.SpareTime > 0) { 224 double spare = nextStop.SpareTime - additionalTime; 225 if (spare < 0) 226 tardiness += -spare; 227 } else { 228 tardiness += additionalTime; 229 } 230 } 231 } 232 233 costs += additionalTime * vrptw.TimeFactor.Value; 234 235 if (tardiness > 0) { 236 feasible = false; 237 } 238 239 costs += tardiness * tardinessPenalty; 240 241 return costs; 124 242 } 125 243 -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs
r4752 r6752 41 41 public class SingleDepotVRPEvaluator: VRPEvaluator { 42 42 protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) { 43 TourInsertionInfo tourInfo = new TourInsertionInfo(); 44 eval.InsertionInfo.AddTourInsertionInfo(tourInfo); 45 43 46 double distance = 0.0; 44 47 double quality = 0.0; … … 56 59 double currentDistace = instance.GetDistance(start, end); 57 60 distance += currentDistace; 61 62 StopInsertionInfo stopInfo = new StopInsertionInfo(start, end); 63 tourInfo.AddStopInsertionInfo(stopInfo); 58 64 } 59 65 … … 67 73 68 74 eval.Quality += quality; 75 } 76 77 protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, 78 out bool feasible) { 79 StopInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index); 80 81 double costs = 0; 82 feasible = true; 83 84 double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End); 85 double newDistance = 86 instance.GetDistance(insertionInfo.Start, customer) + 87 instance.GetDistance(customer, insertionInfo.End); 88 89 costs += instance.DistanceFactor.Value * (newDistance - distance); 90 91 return costs; 69 92 } 70 93 -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluation.cs
r4454 r6752 24 24 using System.Linq; 25 25 using System.Text; 26 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 27 using HeuristicLab.Core; 28 using HeuristicLab.Common; 26 29 27 30 namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances { 31 public class StopInsertionInfo { 32 private int start; 33 34 public int Start { 35 get { return start; } 36 } 37 38 private int end; 39 40 public int End { 41 get { return end; } 42 } 43 44 public StopInsertionInfo(int start, int end) 45 : base() { 46 this.start = start; 47 this.end = end; 48 } 49 } 50 51 public class TourInsertionInfo { 52 public double Penalty { get; set; } 53 54 private List<StopInsertionInfo> stopInsertionInfos; 55 56 public TourInsertionInfo() 57 : base() { 58 stopInsertionInfos = new List<StopInsertionInfo>(); 59 } 60 61 public void AddStopInsertionInfo(StopInsertionInfo info) { 62 stopInsertionInfos.Add(info); 63 } 64 65 public StopInsertionInfo GetStopInsertionInfo(int stop) { 66 return stopInsertionInfos[stop]; 67 } 68 69 public int GetStopCount() { 70 return stopInsertionInfos.Count; 71 } 72 } 73 74 public class InsertionInfo { 75 private List<TourInsertionInfo> tourInsertionInfos; 76 77 public InsertionInfo() 78 : base() { 79 tourInsertionInfos = new List<TourInsertionInfo>(); 80 } 81 82 public void AddTourInsertionInfo(TourInsertionInfo info) { 83 tourInsertionInfos.Add(info); 84 } 85 86 public TourInsertionInfo GetTourInsertionInfo(int tour) { 87 return tourInsertionInfos[tour]; 88 } 89 } 90 28 91 public class VRPEvaluation { 29 92 public double Quality { get; set; } 30 93 public double Distance { get; set; } 31 94 public int VehicleUtilization { get; set; } 95 public InsertionInfo InsertionInfo { get; set; } 32 96 33 97 public double Penalty { get; set; } 98 99 public VRPEvaluation() { 100 InsertionInfo = new InsertionInfo(); 101 } 34 102 } 35 103 } -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs
r5127 r6752 109 109 } 110 110 111 protected abstract double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible); 112 113 public double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible) { 114 bool tourFeasible; 115 double costs = GetTourInsertionCosts( 116 instance, 117 eval.InsertionInfo.GetTourInsertionInfo(tour), index, 118 customer, out tourFeasible); 119 120 feasible = tourFeasible; 121 122 return costs; 123 } 124 111 125 public VRPEvaluation Evaluate(IVRPProblemInstance instance, IVRPEncoding solution) { 112 126 VRPEvaluation evaluation = CreateTourEvaluation(); -
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs
r6711 r6752 230 230 } 231 231 232 public double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible) { 233 return evaluator.GetInsertionCosts(this, eval, customer, tour, index, out feasible); 234 } 235 232 236 protected void EvalBestKnownSolution() { 233 237 if (BestKnownSolution != null) {
Note: See TracChangeset
for help on using the changeset viewer.