Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs @ 10355

Last change on this file since 10355 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)
File size: 14.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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", "Creates a randomly initialized VRP solution.")]
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 dist;
141        if (problemInstance.Coordinates[customer + depotCount - 1, 0] < x0)
142          dist = -distance;
143        else
144          dist = distance;
145
146        double cost = alpha * distance + // distance 0 <-> City[i]
147                   -beta * dueTime + // latest arrival time
148                   -gamma * (Math.Asin((problemInstance.Coordinates[customer + depotCount - 1, 1] - y0) / dist) / 360 * dist); // polar angle
149
150        if (cost < minCost) {
151          minCost = cost;
152          nearest = depot;
153        }
154      }
155
156      return nearest;
157    }
158
159    private static List<int> SortCustomers(IVRPProblemInstance problemInstance, List<int> customers, List<int> depots,
160      Dictionary<int, int> depotAssignment,
161      double alpha, double beta, double gamma) {
162      List<int> sortedCustomers = new List<int>();
163      depotAssignment.Clear();
164
165      List<double> costList = new List<double>();
166
167      for (int i = 0; i < customers.Count; i++) {
168        double cost;
169        int depot = GetNearestDepot(problemInstance, depots, customers[i],
170          alpha, beta, gamma,
171          out cost);
172        depotAssignment[customers[i]] = depot;
173
174        int index = 0;
175        while (index < costList.Count && costList[index] < cost) index++;
176        costList.Insert(index, cost);
177        sortedCustomers.Insert(index, customers[i]);
178      }
179
180      return sortedCustomers;
181    }
182
183    private static bool RemoveUnusedDepots(List<int> depots, Dictionary<int, List<int>> vehicles) {
184      List<int> toBeRemoved = new List<int>();
185
186      foreach (int depot in depots) {
187        if (vehicles[depot].Count == 0)
188          toBeRemoved.Add(depot);
189      }
190
191      foreach (int depot in toBeRemoved) {
192        depots.Remove(depot);
193        vehicles.Remove(depot);
194      }
195
196      return toBeRemoved.Count > 0;
197    }
198
199    public static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
200      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
201      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
202      PotvinEncoding result = new PotvinEncoding(problemInstance);
203
204      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
205      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
206
207      double alpha, beta, gamma;
208      alpha = N(alphaValue, Math.Sqrt(alphaVariance), random);
209      beta = N(betaValue, Math.Sqrt(betaVariance), random);
210      gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
211
212      List<int> unroutedCustomers = new List<int>();
213      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
214        if (pdp == null || (problemInstance.GetDemand(i) >= 0))
215          unroutedCustomers.Add(i);
216      }
217
218      List<int> depots = new List<int>();
219      if (mdp != null) {
220        for (int i = 0; i < mdp.Depots.Value; i++) {
221          depots.Add(i);
222        }
223      } else {
224        depots.Add(0);
225      }
226
227      Dictionary<int, List<int>> vehicles = new Dictionary<int, List<int>>();
228      foreach (int depot in depots) {
229        vehicles[depot] = new List<int>();
230
231        int vehicleCount = problemInstance.Vehicles.Value;
232        if (mdp != null) {
233          for (int vehicle = 0; vehicle < mdp.VehicleDepotAssignment.Length; vehicle++) {
234            if (mdp.VehicleDepotAssignment[vehicle] == depot) {
235              vehicles[depot].Add(vehicle);
236            }
237          }
238        } else {
239          for (int vehicle = 0; vehicle < vehicleCount; vehicle++) {
240            vehicles[depot].Add(vehicle);
241          }
242        }
243      }
244
245      RemoveUnusedDepots(depots, vehicles);
246      Dictionary<int, int> depotAssignment = new Dictionary<int, int>();
247
248      unroutedCustomers = SortCustomers(
249        problemInstance, unroutedCustomers, depots, depotAssignment,
250        alpha, beta, gamma);
251
252      /////////
253      Tour tour = new Tour();
254      result.Tours.Add(tour);
255      int currentCustomer = unroutedCustomers[0];
256      unroutedCustomers.RemoveAt(0);
257
258      int currentDepot = depotAssignment[currentCustomer];
259      int currentVehicle = vehicles[currentDepot][0];
260      vehicles[currentDepot].RemoveAt(0);
261      if (RemoveUnusedDepots(depots, vehicles)) {
262        unroutedCustomers = SortCustomers(
263        problemInstance, unroutedCustomers, depots, depotAssignment,
264        alpha, beta, gamma);
265      }
266
267      result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
268
269      tour.Stops.Add(currentCustomer);
270      if (pdp != null) {
271        tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
272      }
273      ////////
274
275      while (unroutedCustomers.Count > 0) {
276        double minimumCost = double.MaxValue;
277        int customer = -1;
278        int indexOfMinimumCost = -1;
279        int indexOfMinimumCost2 = -1;
280
281        foreach (int unrouted in unroutedCustomers) {
282          VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
283          double originalCosts = eval.Quality;
284
285          for (int i = 0; i <= tour.Stops.Count; i++) {
286            tour.Stops.Insert(i, unrouted);
287            eval = problemInstance.EvaluateTour(tour, result);
288            double tourCost = eval.Quality - originalCosts;
289
290            if (pdp != null) {
291              for (int j = i + 1; j <= tour.Stops.Count; j++) {
292                bool feasible;
293                double cost = tourCost +
294                  problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unrouted), 0, j, out feasible);
295                if (cost < minimumCost && feasible) {
296                  customer = unrouted;
297                  minimumCost = cost;
298                  indexOfMinimumCost = i;
299                  indexOfMinimumCost2 = j;
300                }
301              }
302            } else {
303              double cost = tourCost;
304              bool feasible = problemInstance.Feasible(eval);
305              if (cost < minimumCost && feasible) {
306                customer = unrouted;
307                minimumCost = cost;
308                indexOfMinimumCost = i;
309              }
310            }
311
312            tour.Stops.RemoveAt(i);
313          }
314        }
315
316        if (indexOfMinimumCost == -1 && vehicles.Count == 0) {
317          indexOfMinimumCost = tour.Stops.Count;
318          indexOfMinimumCost2 = tour.Stops.Count + 1;
319          customer = unroutedCustomers[0];
320        }
321
322        // insert customer if found
323        if (indexOfMinimumCost != -1) {
324          tour.Stops.Insert(indexOfMinimumCost, customer);
325          if (pdp != null) {
326            tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(customer));
327          }
328
329          unroutedCustomers.Remove(customer);
330        } else { // no feasible customer found
331          tour = new Tour();
332          result.Tours.Add(tour);
333          currentCustomer = unroutedCustomers[0];
334          unroutedCustomers.RemoveAt(0);
335
336          currentDepot = depotAssignment[currentCustomer];
337          currentVehicle = vehicles[currentDepot][0];
338          vehicles[currentDepot].RemoveAt(0);
339          if (RemoveUnusedDepots(depots, vehicles)) {
340            unroutedCustomers = SortCustomers(
341            problemInstance, unroutedCustomers, depots, depotAssignment,
342            alpha, beta, gamma);
343          }
344
345          result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
346
347          tour.Stops.Add(currentCustomer);
348          if (pdp != null) {
349            tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
350          }
351        }
352      }
353
354      if (mdp != null) {
355        List<int> availableVehicles = new List<int>();
356        for (int i = 0; i < mdp.Vehicles.Value; i++)
357          availableVehicles.Add(i);
358
359        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
360          if (result.VehicleAssignment[i] != -1)
361            availableVehicles.Remove(result.VehicleAssignment[i]);
362        }
363
364        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
365          if (result.VehicleAssignment[i] == -1) {
366            result.VehicleAssignment[i] = availableVehicles[0];
367            availableVehicles.RemoveAt(0);
368          }
369        }
370      }
371
372      return result;
373    }
374
375    public override IOperation Apply() {
376      VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, RandomParameter.ActualValue,
377        Alpha.Value.Value, Beta.Value.Value, Gamma.Value.Value,
378        AlphaVariance.Value.Value, BetaVariance.Value.Value, GammaVariance.Value.Value);
379
380      return base.Apply();
381    }
382  }
383}
Note: See TracBrowser for help on using the repository browser.