Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceSpeedUp/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/PushForwardInsertionCreator.cs @ 6760

Last change on this file since 6760 was 6760, checked in by epitzer, 13 years ago

#1530 integrate changes from trunk

File size: 12.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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;
30
31namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
32  [Item("PushForwardCreator", "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.")]
33  [StorableClass]
34  public sealed class PushForwardCreator : DefaultRepresentationCreator, IStochasticOperator {
35    #region IStochasticOperator Members
36    public ILookupParameter<IRandom> RandomParameter {
37      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
38    }
39    #endregion
40
41    public IValueParameter<DoubleValue> Alpha {
42      get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
43    }
44    public IValueParameter<DoubleValue> AlphaVariance {
45      get { return (IValueParameter<DoubleValue>)Parameters["AlphaVariance"]; }
46    }
47    public IValueParameter<DoubleValue> Beta {
48      get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
49    }
50    public IValueParameter<DoubleValue> BetaVariance {
51      get { return (IValueParameter<DoubleValue>)Parameters["BetaVariance"]; }
52    }
53    public IValueParameter<DoubleValue> Gamma {
54      get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
55    }
56    public IValueParameter<DoubleValue> GammaVariance {
57      get { return (IValueParameter<DoubleValue>)Parameters["GammaVariance"]; }
58    }
59
60    [StorableConstructor]
61    private PushForwardCreator(bool deserializing) : base(deserializing) { }
62    private PushForwardCreator(PushForwardCreator original, Cloner cloner) : base(original, cloner) { }
63    public override IDeepCloneable Clone(Cloner cloner) {
64      return new PushForwardCreator(this, cloner);
65    }
66
67    public PushForwardCreator()
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    // use the Box-Mueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables
79    private double Gauss(IRandom random) {
80      double u = 0.0, v = 0.0, s = 0.0;
81      do {
82        u = (random.NextDouble() * 2) - 1;
83        v = (random.NextDouble() * 2) - 1;
84        s = Math.Sqrt(u * u + v * v);
85      } while (s < Double.Epsilon || s > 1);
86      return u * Math.Sqrt((-2.0 * Math.Log(s)) / s);
87    }
88
89    private double N(double mu, double sigma, IRandom random) {
90      return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)
91    }
92
93    private double CalculateDistance(int start, int end, DoubleMatrix coordinates) {
94      double distance = 0.0;
95
96      distance =
97          Math.Sqrt(
98            Math.Pow(coordinates[start, 0] - coordinates[end, 0], 2) +
99            Math.Pow(coordinates[start, 1] - coordinates[end, 1], 2));
100
101      return distance;
102    }
103
104    private DoubleMatrix CreateDistanceMatrix(DoubleMatrix coordinates) {
105      DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
106
107      for (int i = 0; i < distanceMatrix.Rows; i++) {
108        for (int j = i; j < distanceMatrix.Columns; j++) {
109          double distance = CalculateDistance(i, j, coordinates);
110
111          distanceMatrix[i, j] = distance;
112          distanceMatrix[j, i] = distance;
113        }
114      }
115
116      return distanceMatrix;
117    }
118
119    private double Distance(int start, int end, DoubleMatrix coordinates, bool useDistanceMatrix) {
120      double distance = 0.0;
121
122      if (useDistanceMatrix) {
123        distance = coordinates[start, end];
124      } else { 
125        distance = CalculateDistance(start, end, coordinates);
126      }
127
128      return distance;
129    }
130
131    private double TravelDistance(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix) {
132      double distance = 0;
133      for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
134        distance += Distance(route[i], route[i + 1], coordinates, useDistanceMatrix);
135      }
136      return distance;
137    }
138
139    private bool SubrouteConstraintsOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
140      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
141      double t = 0.0, o = 0.0;
142      for (int i = begin + 1; i < route.Count; i++) {
143        t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
144        if (route[i] == 0) return (t < DueTimeParameter.ActualValue[0]); // violation on capacity constraint is handled below
145        else {
146          if (t > dueTime[route[i]]) return false;
147          t = Math.Max(readyTime[route[i]], t);
148          t += serviceTime[route[i]];
149          o += demand[route[i]];
150          if (o > capacity.Value) return false; // premature exit on capacity constraint violation
151        }
152      }
153      return true;
154    }
155
156    private bool SubrouteTardinessOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
157      DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime) {
158      double t = 0.0;
159      for (int i = begin + 1; i < route.Count; i++) {
160        t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
161        if (route[i] == 0) {
162          if (t < dueTime[0]) return true;
163          else return false;
164        } else {
165          if (t > dueTime[route[i]]) return false;
166          t = Math.Max(readyTime[route[i]], t);
167          t += serviceTime[route[i]];
168        }
169      }
170      return true;
171    }
172
173    private bool SubrouteLoadOK(List<int> route, int begin, DoubleValue capacity, DoubleArray demand) {
174      double o = 0.0;
175      for (int i = begin + 1; i < route.Count; i++) {
176        if (route[i] == 0) return (o < capacity.Value);
177        else {
178          o += demand[route[i]];
179        }
180      }
181      return (o < capacity.Value);
182    }
183
184    protected override List<int> CreateSolution() {
185      //double alpha, beta, gamma;
186      double alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
187      double beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
188      double gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
189
190      double x0 = CoordinatesParameter.ActualValue[0, 0];
191      double y0 = CoordinatesParameter.ActualValue[0, 1];
192      double distance = 0;
193      double cost = 0;
194      double minimumCost = double.MaxValue;
195      List<int> unroutedList = new List<int>();
196      List<double> costList = new List<double>();
197      int index;
198      int indexOfMinimumCost = -1;
199      int indexOfCustomer = -1;
200
201      int vehicles = VehiclesParameter.ActualValue.Value;
202      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
203      DoubleArray dueTime = DueTimeParameter.ActualValue;
204      DoubleArray serviceTime = ServiceTimeParameter.ActualValue;
205      DoubleArray readyTime = ReadyTimeParameter.ActualValue;
206      DoubleArray demand = DemandParameter.ActualValue;
207      DoubleValue capacity = CapacityParameter.ActualValue;
208
209      bool useDistanceMatrix = UseDistanceMatrixParameter.ActualValue.Value;
210      if (useDistanceMatrix) {
211        if (DistanceMatrixParameter.ActualValue == null) {
212          DistanceMatrixParameter.ActualValue = CreateDistanceMatrix(coordinates);
213        }
214
215        coordinates = DistanceMatrixParameter.ActualValue;
216      }
217
218      /*-----------------------------------------------------------------------------
219       * generate cost list
220       *-----------------------------------------------------------------------------
221       */
222      for (int i = 1; i <= Cities; i++) {
223        distance = Distance(i, 0, coordinates, useDistanceMatrix);
224        if (coordinates[i, 0] < x0) distance = -distance;
225        cost = -alpha * distance + // distance 0 <-> City[i]
226                 beta * (DueTimeParameter.ActualValue[i]) + // latest arrival time
227                 gamma * (Math.Asin((coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
228
229        index = 0;
230        while (index < costList.Count && costList[index] < cost) index++;
231        costList.Insert(index, cost);
232        unroutedList.Insert(index, i);
233      }
234
235      /*------------------------------------------------------------------------------
236       * route customers according to cost list
237       *------------------------------------------------------------------------------
238       */
239      int routeIndex = 0;
240      int currentRoute = 0;
241      int c;
242      int customer = -1;
243      int subTourCount = 1;
244
245      List<int> route = new List<int>(Cities + vehicles - 1);
246      minimumCost = double.MaxValue;
247      indexOfMinimumCost = -1;
248      route.Add(0);
249      route.Add(0);
250      route.Insert(1, unroutedList[0]);
251      unroutedList.RemoveAt(0);
252      currentRoute = routeIndex;
253      routeIndex++;
254
255      do {
256        for (c = 0; c < unroutedList.Count; c++) {
257          for (int i = currentRoute + 1; i < route.Count; i++) {
258            route.Insert(i, (int)unroutedList[c]);
259            if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
260            cost = TravelDistance(route, currentRoute, coordinates, useDistanceMatrix);
261            if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute, coordinates, useDistanceMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
262              minimumCost = cost;
263              indexOfMinimumCost = i;
264              customer = (int)unroutedList[c];
265              indexOfCustomer = c;
266            }
267            route.RemoveAt(i);
268          }
269        }
270        // insert customer if found
271        if (indexOfMinimumCost != -1) {
272          route.Insert(indexOfMinimumCost, customer);
273          routeIndex++;
274          unroutedList.RemoveAt(indexOfCustomer);
275          costList.RemoveAt(indexOfCustomer);
276        } else { // no feasible customer found
277          routeIndex++;
278          route.Insert(routeIndex, 0);
279          currentRoute = routeIndex;
280          route.Insert(route.Count - 1, (int)unroutedList[0]);
281          unroutedList.RemoveAt(0);
282          routeIndex++;
283          subTourCount++;
284        }
285        // reset minimum   
286        minimumCost = double.MaxValue;
287        indexOfMinimumCost = -1;
288        indexOfCustomer = -1;
289        customer = -1;
290      } while (unroutedList.Count > 0);
291      while (route.Count < Cities + vehicles)
292        route.Add(0);
293
294      return route;
295    }
296  }
297}
Note: See TracBrowser for help on using the repository browser.