Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2434_crossvalidation/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs

Last change on this file was 12012, checked in by ascheibe, 10 years ago

#2212 merged r12008, r12009, r12010 back into trunk
File size: 14.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.VehicleRouting.Interfaces;
31using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
32using HeuristicLab.Problems.VehicleRouting.Variants;
33
34namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
35  [Item("PushForwardInsertionCreator", "The push forward insertion heuristic. It is implemented as described in Sam, and Thangiah, R. (1999). A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III, pp 347–381.")]
36  [StorableClass]
37  public sealed class PushForwardInsertionCreator : PotvinCreator, IStochasticOperator {
38    #region IStochasticOperator Members
39    public ILookupParameter<IRandom> RandomParameter {
40      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
41    }
42    #endregion
43
44    public IValueParameter<DoubleValue> Alpha {
45      get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
46    }
47    public IValueParameter<DoubleValue> AlphaVariance {
48      get { return (IValueParameter<DoubleValue>)Parameters["AlphaVariance"]; }
49    }
50    public IValueParameter<DoubleValue> Beta {
51      get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
52    }
53    public IValueParameter<DoubleValue> BetaVariance {
54      get { return (IValueParameter<DoubleValue>)Parameters["BetaVariance"]; }
55    }
56    public IValueParameter<DoubleValue> Gamma {
57      get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
58    }
59    public IValueParameter<DoubleValue> GammaVariance {
60      get { return (IValueParameter<DoubleValue>)Parameters["GammaVariance"]; }
61    }
62
63    [StorableConstructor]
64    private PushForwardInsertionCreator(bool deserializing) : base(deserializing) { }
65
66    public PushForwardInsertionCreator()
67      : base() {
68      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
69      Parameters.Add(new ValueParameter<DoubleValue>("Alpha", "The alpha value.", new DoubleValue(0.7)));
70      Parameters.Add(new ValueParameter<DoubleValue>("AlphaVariance", "The alpha variance.", new DoubleValue(0.5)));
71      Parameters.Add(new ValueParameter<DoubleValue>("Beta", "The beta value.", new DoubleValue(0.1)));
72      Parameters.Add(new ValueParameter<DoubleValue>("BetaVariance", "The beta variance.", new DoubleValue(0.07)));
73      Parameters.Add(new ValueParameter<DoubleValue>("Gamma", "The gamma value.", new DoubleValue(0.2)));
74      Parameters.Add(new ValueParameter<DoubleValue>("GammaVariance", "The gamma variance.", new DoubleValue(0.14)));
75    }
76
77    public override IDeepCloneable Clone(Cloner cloner) {
78      return new PushForwardInsertionCreator(this, cloner);
79    }
80
81    private PushForwardInsertionCreator(PushForwardInsertionCreator original, Cloner cloner)
82      : base(original, cloner) {
83    }
84
85    // use the Box-Mueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables
86    private static double Gauss(IRandom random) {
87      double u = 0.0, v = 0.0, s = 0.0;
88      do {
89        u = (random.NextDouble() * 2) - 1;
90        v = (random.NextDouble() * 2) - 1;
91        s = Math.Sqrt(u * u + v * v);
92      } while (s < Double.Epsilon || s > 1);
93      return u * Math.Sqrt((-2.0 * Math.Log(s)) / s);
94    }
95
96    private static double N(double mu, double sigma, IRandom random) {
97      return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)
98    }
99
100    private static double GetDistance(int start, int end, IVRPProblemInstance problemInstance) {
101      double distance = 0.0;
102
103      double startX = problemInstance.Coordinates[start, 0];
104      double startY = problemInstance.Coordinates[start, 1];
105
106      double endX = problemInstance.Coordinates[end, 0];
107      double endY = problemInstance.Coordinates[end, 1];
108
109      distance =
110          Math.Sqrt(
111            Math.Pow(startX - endX, 2) +
112            Math.Pow(startY - endY, 2));
113
114      return distance;
115    }
116
117    private static int GetNearestDepot(IVRPProblemInstance problemInstance, List<int> depots, int customer,
118      double alpha, double beta, double gamma, out double minCost) {
119      int nearest = -1;
120      minCost = double.MaxValue;
121
122      int depotCount = 1;
123      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
124      if (mdp != null) {
125        depotCount = mdp.Depots.Value;
126      }
127
128      foreach (int depot in depots) {
129        double x0 = problemInstance.Coordinates[depot, 0];
130        double y0 = problemInstance.Coordinates[depot, 1];
131
132        double distance = GetDistance(customer + depotCount - 1, depot, problemInstance);
133
134        double dueTime = 0;
135        if (problemInstance is ITimeWindowedProblemInstance)
136          dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[customer + depotCount - 1];
137        if (dueTime == double.MaxValue)
138          dueTime = 0;
139
140        double x = problemInstance.Coordinates[customer + depotCount - 1, 0];
141        double y = problemInstance.Coordinates[customer + depotCount - 1, 1];
142
143        double cost = alpha * distance + // distance 0 <-> City[i]
144                      -beta * dueTime + // latest arrival time
145                      -gamma * ((Math.Atan2(y - y0, x - x0) + Math.PI) / (2.0 * Math.PI) * distance); // polar angle
146
147        if (cost < minCost) {
148          minCost = cost;
149          nearest = depot;
150        }
151      }
152
153      return nearest;
154    }
155
156    private static List<int> SortCustomers(IVRPProblemInstance problemInstance, List<int> customers, List<int> depots,
157      Dictionary<int, int> depotAssignment,
158      double alpha, double beta, double gamma) {
159      List<int> sortedCustomers = new List<int>();
160      depotAssignment.Clear();
161
162      List<double> costList = new List<double>();
163
164      for (int i = 0; i < customers.Count; i++) {
165        double cost;
166        int depot = GetNearestDepot(problemInstance, depots, customers[i],
167          alpha, beta, gamma,
168          out cost);
169        depotAssignment[customers[i]] = depot;
170
171        int index = 0;
172        while (index < costList.Count && costList[index] < cost) index++;
173        costList.Insert(index, cost);
174        sortedCustomers.Insert(index, customers[i]);
175      }
176
177      return sortedCustomers;
178    }
179
180    private static bool RemoveUnusedDepots(List<int> depots, Dictionary<int, List<int>> vehicles) {
181      List<int> toBeRemoved = new List<int>();
182
183      foreach (int depot in depots) {
184        if (vehicles[depot].Count == 0)
185          toBeRemoved.Add(depot);
186      }
187
188      foreach (int depot in toBeRemoved) {
189        depots.Remove(depot);
190        vehicles.Remove(depot);
191      }
192
193      return toBeRemoved.Count > 0;
194    }
195
196    public static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
197      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
198      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
199      PotvinEncoding result = new PotvinEncoding(problemInstance);
200
201      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
202      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
203
204      double alpha, beta, gamma;
205      alpha = N(alphaValue, Math.Sqrt(alphaVariance), random);
206      beta = N(betaValue, Math.Sqrt(betaVariance), random);
207      gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
208
209      List<int> unroutedCustomers = new List<int>();
210      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
211        if (pdp == null || (problemInstance.GetDemand(i) >= 0))
212          unroutedCustomers.Add(i);
213      }
214
215      List<int> depots = new List<int>();
216      if (mdp != null) {
217        for (int i = 0; i < mdp.Depots.Value; i++) {
218          depots.Add(i);
219        }
220      } else {
221        depots.Add(0);
222      }
223
224      Dictionary<int, List<int>> vehicles = new Dictionary<int, List<int>>();
225      foreach (int depot in depots) {
226        vehicles[depot] = new List<int>();
227
228        int vehicleCount = problemInstance.Vehicles.Value;
229        if (mdp != null) {
230          for (int vehicle = 0; vehicle < mdp.VehicleDepotAssignment.Length; vehicle++) {
231            if (mdp.VehicleDepotAssignment[vehicle] == depot) {
232              vehicles[depot].Add(vehicle);
233            }
234          }
235        } else {
236          for (int vehicle = 0; vehicle < vehicleCount; vehicle++) {
237            vehicles[depot].Add(vehicle);
238          }
239        }
240      }
241
242      RemoveUnusedDepots(depots, vehicles);
243      Dictionary<int, int> depotAssignment = new Dictionary<int, int>();
244
245      unroutedCustomers = SortCustomers(
246        problemInstance, unroutedCustomers, depots, depotAssignment,
247        alpha, beta, gamma);
248
249      /////////
250      Tour tour = new Tour();
251      result.Tours.Add(tour);
252      int currentCustomer = unroutedCustomers[0];
253      unroutedCustomers.RemoveAt(0);
254
255      int currentDepot = depotAssignment[currentCustomer];
256      int currentVehicle = vehicles[currentDepot][0];
257      vehicles[currentDepot].RemoveAt(0);
258      if (RemoveUnusedDepots(depots, vehicles)) {
259        unroutedCustomers = SortCustomers(
260        problemInstance, unroutedCustomers, depots, depotAssignment,
261        alpha, beta, gamma);
262      }
263
264      result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
265
266      tour.Stops.Add(currentCustomer);
267      if (pdp != null) {
268        tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
269      }
270      ////////
271
272      while (unroutedCustomers.Count > 0) {
273        double minimumCost = double.MaxValue;
274        int customer = -1;
275        int indexOfMinimumCost = -1;
276        int indexOfMinimumCost2 = -1;
277
278        foreach (int unrouted in unroutedCustomers) {
279          VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
280          double originalCosts = eval.Quality;
281
282          for (int i = 0; i <= tour.Stops.Count; i++) {
283            tour.Stops.Insert(i, unrouted);
284            eval = problemInstance.EvaluateTour(tour, result);
285            double tourCost = eval.Quality - originalCosts;
286
287            if (pdp != null) {
288              for (int j = i + 1; j <= tour.Stops.Count; j++) {
289                bool feasible;
290                double cost = tourCost +
291                  problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unrouted), 0, j, out feasible);
292                if (cost < minimumCost && feasible) {
293                  customer = unrouted;
294                  minimumCost = cost;
295                  indexOfMinimumCost = i;
296                  indexOfMinimumCost2 = j;
297                }
298              }
299            } else {
300              double cost = tourCost;
301              bool feasible = problemInstance.Feasible(eval);
302              if (cost < minimumCost && feasible) {
303                customer = unrouted;
304                minimumCost = cost;
305                indexOfMinimumCost = i;
306              }
307            }
308
309            tour.Stops.RemoveAt(i);
310          }
311        }
312
313        if (indexOfMinimumCost == -1 && vehicles.Count == 0) {
314          indexOfMinimumCost = tour.Stops.Count;
315          indexOfMinimumCost2 = tour.Stops.Count + 1;
316          customer = unroutedCustomers[0];
317        }
318
319        // insert customer if found
320        if (indexOfMinimumCost != -1) {
321          tour.Stops.Insert(indexOfMinimumCost, customer);
322          if (pdp != null) {
323            tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(customer));
324          }
325
326          unroutedCustomers.Remove(customer);
327        } else { // no feasible customer found
328          tour = new Tour();
329          result.Tours.Add(tour);
330          currentCustomer = unroutedCustomers[0];
331          unroutedCustomers.RemoveAt(0);
332
333          currentDepot = depotAssignment[currentCustomer];
334          currentVehicle = vehicles[currentDepot][0];
335          vehicles[currentDepot].RemoveAt(0);
336          if (RemoveUnusedDepots(depots, vehicles)) {
337            unroutedCustomers = SortCustomers(
338            problemInstance, unroutedCustomers, depots, depotAssignment,
339            alpha, beta, gamma);
340          }
341
342          result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
343
344          tour.Stops.Add(currentCustomer);
345          if (pdp != null) {
346            tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
347          }
348        }
349      }
350
351      if (mdp != null) {
352        List<int> availableVehicles = new List<int>();
353        for (int i = 0; i < mdp.Vehicles.Value; i++)
354          availableVehicles.Add(i);
355
356        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
357          if (result.VehicleAssignment[i] != -1)
358            availableVehicles.Remove(result.VehicleAssignment[i]);
359        }
360
361        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
362          if (result.VehicleAssignment[i] == -1) {
363            result.VehicleAssignment[i] = availableVehicles[0];
364            availableVehicles.RemoveAt(0);
365          }
366        }
367      }
368
369      return result;
370    }
371
372    public override IOperation InstrumentedApply() {
373      VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, RandomParameter.ActualValue,
374        Alpha.Value.Value, Beta.Value.Value, Gamma.Value.Value,
375        AlphaVariance.Value.Value, BetaVariance.Value.Value, GammaVariance.Value.Value);
376
377      return base.InstrumentedApply();
378    }
379  }
380}
Note: See TracBrowser for help on using the repository browser.