Free cookie consent management tool by TermsFeed Policy Generator

source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs @ 6857

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

Added vehicle assignment manipulator and move for multi depot instances (#1177)
File size: 12.6 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 HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Common;
31using HeuristicLab.Problems.VehicleRouting.Interfaces;
32using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
33using HeuristicLab.Problems.VehicleRouting.Variants;
34
35namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
36  [Item("PushForwardInsertionCreator", "Creates a randomly initialized VRP solution.")]
37  [StorableClass]
38  public sealed class PushForwardInsertionCreator : PotvinCreator, IStochasticOperator {
39    #region IStochasticOperator Members
40    public ILookupParameter<IRandom> RandomParameter {
41      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
42    }
43    #endregion
44
45    public IValueParameter<DoubleValue> Alpha {
46      get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
47    }
48    public IValueParameter<DoubleValue> AlphaVariance {
49      get { return (IValueParameter<DoubleValue>)Parameters["AlphaVariance"]; }
50    }
51    public IValueParameter<DoubleValue> Beta {
52      get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
53    }
54    public IValueParameter<DoubleValue> BetaVariance {
55      get { return (IValueParameter<DoubleValue>)Parameters["BetaVariance"]; }
56    }
57    public IValueParameter<DoubleValue> Gamma {
58      get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
59    }
60    public IValueParameter<DoubleValue> GammaVariance {
61      get { return (IValueParameter<DoubleValue>)Parameters["GammaVariance"]; }
62    }
63
64    [StorableConstructor]
65    private PushForwardInsertionCreator(bool deserializing) : base(deserializing) { }
66
67    public PushForwardInsertionCreator()
68      : base() {
69      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
70      Parameters.Add(new ValueParameter<DoubleValue>("Alpha", "The alpha value.", new DoubleValue(0.7)));
71      Parameters.Add(new ValueParameter<DoubleValue>("AlphaVariance", "The alpha variance.", new DoubleValue(0.5)));
72      Parameters.Add(new ValueParameter<DoubleValue>("Beta", "The beta value.", new DoubleValue(0.1)));
73      Parameters.Add(new ValueParameter<DoubleValue>("BetaVariance", "The beta variance.", new DoubleValue(0.07)));
74      Parameters.Add(new ValueParameter<DoubleValue>("Gamma", "The gamma value.", new DoubleValue(0.2)));
75      Parameters.Add(new ValueParameter<DoubleValue>("GammaVariance", "The gamma variance.", new DoubleValue(0.14)));
76    }
77
78    public override IDeepCloneable Clone(Cloner cloner) {
79      return new PushForwardInsertionCreator(this, cloner);
80    }
81
82    private PushForwardInsertionCreator(PushForwardInsertionCreator original, Cloner cloner)
83      : base(original, cloner) {
84    }
85
86    // use the Box-Mueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables
87    private static double Gauss(IRandom random) {
88      double u = 0.0, v = 0.0, s = 0.0;
89      do {
90        u = (random.NextDouble() * 2) - 1;
91        v = (random.NextDouble() * 2) - 1;
92        s = Math.Sqrt(u * u + v * v);
93      } while (s < Double.Epsilon || s > 1);
94      return u * Math.Sqrt((-2.0 * Math.Log(s)) / s);
95    }
96
97    private static double N(double mu, double sigma, IRandom random) {
98      return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)
99    }
100
101    private static double GetDistance(int start, int end, IVRPProblemInstance problemInstance) {
102      double distance = 0.0;
103
104      double startX = problemInstance.Coordinates[start, 0];
105      double startY = problemInstance.Coordinates[start, 1];
106
107      double endX = problemInstance.Coordinates[end, 0];
108      double endY = problemInstance.Coordinates[end, 1];
109
110      distance =
111          Math.Sqrt(
112            Math.Pow(startX - endX, 2) +
113            Math.Pow(startY - endY, 2));
114
115      return distance;
116    }
117
118    private static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
119      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
120      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
121      PotvinEncoding result = new PotvinEncoding(problemInstance);
122
123      double alpha, beta, gamma;
124      alpha = N(alphaValue, Math.Sqrt(alphaVariance), random);
125      beta = N(betaValue, Math.Sqrt(betaVariance), random);
126      gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
127
128      int totalTours = 0;
129
130      double distance = 0;
131      double cost = 0;
132      List<int> unroutedList = new List<int>();
133      List<double> costList = new List<double>();
134
135      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
136      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
137
138      int depots = 1;
139      if (mdp != null) {
140        depots = mdp.Depots.Value;
141        for (int i = 0; i < result.VehicleAssignment.Length; i++)
142          result.VehicleAssignment[i] = -1;
143      }
144
145      List<int> unrouted = new List<int>();
146      for (int i = 1; i <= problemInstance.Cities.Value; i++)
147        if (pdp == null || problemInstance.GetDemand(i) >= 0)
148          unrouted.Add(i);
149
150      for (int depot = 0; depot < depots; depot++) {
151        int vehicleCount = problemInstance.Vehicles.Value;
152        List<int> vehicles = new List<int>();
153        if (mdp != null) {
154          vehicleCount = 0;
155          for (int i = 0; i < mdp.VehicleDepotAssignment.Length; i++) {
156            if (mdp.VehicleDepotAssignment[i] == depot) {
157              vehicleCount++;
158              vehicles.Add(i);
159            }
160          }
161        } else {
162          for (int i = 0; i < problemInstance.Vehicles.Value; i++)
163            vehicles.Add(i);
164        }
165
166        costList.Clear();
167        unroutedList.Clear();
168
169        double x0 = problemInstance.Coordinates[depot, 0];
170        double y0 = problemInstance.Coordinates[depot, 1];
171
172        /*-----------------------------------------------------------------------------
173        * generate cost list
174        *-----------------------------------------------------------------------------
175        */
176        for (int i = 1; i <= problemInstance.Cities.Value; i++) {
177          //only insert sources
178          if (unrouted.Contains(i) && (pdp == null || problemInstance.GetDemand(i) >= 0)) {
179            distance = GetDistance(i + depots - 1, depot, problemInstance);
180            if (problemInstance.Coordinates[i + depots - 1, 0] < x0) distance = -distance;
181
182            double dueTime = 0;
183            if (problemInstance is ITimeWindowedProblemInstance)
184              dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i + depots - 1];
185
186            cost = -alpha * distance + // distance 0 <-> City[i]
187                   beta * dueTime + // latest arrival time
188                   gamma * (Math.Asin((problemInstance.Coordinates[i + depots - 1, 0] - y0) / distance) / 360 * distance); // polar angle
189
190            int index = 0;
191            while (index < costList.Count && costList[index] < cost) index++;
192
193            costList.Insert(index, cost);
194
195            unroutedList.Insert(index, i);
196          }
197        }
198
199        int tours = 0;
200        double minimumCost = double.MaxValue;
201        int indexOfMinimumCost = -1;
202        int indexOfMinimumCost2 = -1;
203        int indexOfCustomer = -1;
204
205        Tour tour = new Tour();
206        result.Tours.Add(tour);
207        result.VehicleAssignment[totalTours] = vehicles[0];
208        vehicles.RemoveAt(0);
209        tours++;
210        totalTours++;
211
212        tour.Stops.Add(unroutedList[0]);
213
214        if (pdp != null) {
215          tour.Stops.Add(pdp.GetPickupDeliveryLocation(unroutedList[0]));
216        }
217
218        unrouted.Remove(unroutedList[0]);
219        unroutedList.RemoveAt(0);
220
221        while (unroutedList.Count > 0 && (tours < vehicleCount || depot == depots - 1)) {
222          for (int c = 0; c < unroutedList.Count; c++) {
223            VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
224            double originalCosts = eval.Quality;
225            int customer = unroutedList[c];
226
227            for (int i = 0; i <= tour.Stops.Count; i++) {
228              tour.Stops.Insert(i, customer);
229              eval = problemInstance.EvaluateTour(tour, result);
230              double tourCost = eval.Quality - originalCosts;
231
232              if (pdp != null) {
233                for (int j = i + 1; j <= tour.Stops.Count; j++) {
234                  bool feasible;
235                  cost = tourCost +
236                    problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unroutedList[c]), 0, j, out feasible);
237                  if (cost < minimumCost && feasible) {
238                    minimumCost = cost;
239                    indexOfMinimumCost = i;
240                    indexOfMinimumCost2 = j;
241                    indexOfCustomer = c;
242                  }
243                }
244              } else {
245                cost = tourCost;
246                bool feasible = problemInstance.Feasible(eval);
247                if (cost < minimumCost && feasible) {
248                  minimumCost = cost;
249                  indexOfMinimumCost = i;
250                  indexOfCustomer = c;
251                }
252              }
253
254              tour.Stops.RemoveAt(i);
255            }
256          }
257
258          // insert customer if found
259          if (indexOfMinimumCost != -1) {
260            tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
261            if (pdp != null) {
262              tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(unroutedList[indexOfCustomer]));
263            }
264
265            unrouted.Remove(unroutedList[indexOfCustomer]);
266            unroutedList.RemoveAt(indexOfCustomer);
267          } else if (tours < vehicleCount || depot == depots - 1) { // no feasible customer found
268            tour = new Tour();
269            result.Tours.Add(tour);
270            result.VehicleAssignment[totalTours] = vehicles[0];
271            vehicles.RemoveAt(0);
272            tours++;
273            totalTours++;
274
275            tour.Stops.Add(unroutedList[0]);
276            if (pdp != null) {
277              tour.Stops.Add(pdp.GetPickupDeliveryLocation(unroutedList[0]));
278            }
279
280            unrouted.Remove(unroutedList[0]);
281            unroutedList.RemoveAt(0);
282          }
283          // reset minimum   
284          minimumCost = double.MaxValue;
285          indexOfMinimumCost = -1;
286          indexOfMinimumCost2 = -1;
287          indexOfCustomer = -1;
288        }
289      }
290
291      if (mdp != null) {
292        List<int> availableVehicles = new List<int>();
293        for (int i = 0; i < mdp.Vehicles.Value; i++)
294          availableVehicles.Add(i);
295
296        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
297          if (result.VehicleAssignment[i] != -1)
298            availableVehicles.Remove(result.VehicleAssignment[i]);
299        }
300
301        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
302          if (result.VehicleAssignment[i] == -1) {
303            result.VehicleAssignment[i] = availableVehicles[0];
304            availableVehicles.RemoveAt(0);
305          }
306        }
307      }
308
309      return result;
310    }
311
312    public override IOperation Apply() {
313      VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, RandomParameter.ActualValue,
314        Alpha.Value.Value, Beta.Value.Value, Gamma.Value.Value,
315        AlphaVariance.Value.Value, BetaVariance.Value.Value, GammaVariance.Value.Value);
316
317      return base.Apply();
318    }
319  }
320}
Note: See TracBrowser for help on using the repository browser.