Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/General/Creators/PushForwardInsertionCreator.cs @ 5445

Last change on this file since 5445 was 5445, checked in by swagner, 13 years ago

Updated year of copyrights (#1406)

File size: 11.5 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) {
94      double distance = 0.0;
95      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
96
97      distance =
98          Math.Sqrt(
99            Math.Pow(coordinates[start, 0] - coordinates[end, 0], 2) +
100            Math.Pow(coordinates[start, 1] - coordinates[end, 1], 2));
101
102      return distance;
103    }
104
105    private DoubleMatrix CreateDistanceMatrix() {
106      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
107      DoubleMatrix distanceMatrix = new DoubleMatrix(coordinates.Rows, coordinates.Rows);
108
109      for (int i = 0; i < distanceMatrix.Rows; i++) {
110        for (int j = i; j < distanceMatrix.Columns; j++) {
111          double distance = CalculateDistance(i, j);
112
113          distanceMatrix[i, j] = distance;
114          distanceMatrix[j, i] = distance;
115        }
116      }
117
118      return distanceMatrix;
119    }
120
121    private double Distance(int start, int end) {
122      double distance = 0.0;
123
124      if (UseDistanceMatrixParameter.ActualValue.Value) {
125        if (DistanceMatrixParameter.ActualValue == null) {
126          DistanceMatrixParameter.ActualValue = CreateDistanceMatrix();
127        }
128
129        distance = DistanceMatrixParameter.ActualValue[start, end];
130      } else {
131        distance = CalculateDistance(start, end);
132      }
133
134      return distance;
135    }
136
137    private double TravelDistance(List<int> route, int begin) {
138      double distance = 0;
139      for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
140        distance += Distance(route[i], route[i + 1]);
141      }
142      return distance;
143    }
144
145    private bool SubrouteConstraintsOK(List<int> route, int begin) {
146      double t = 0.0, o = 0.0;
147      for (int i = begin + 1; i < route.Count; i++) {
148        t += Distance(route[i - 1], route[i]);
149        if (route[i] == 0) return (t < DueTimeParameter.ActualValue[0]); // violation on capacity constraint is handled below
150        else {
151          if (t > DueTimeParameter.ActualValue[route[i]]) return false;
152          t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
153          t += ServiceTimeParameter.ActualValue[route[i]];
154          o += DemandParameter.ActualValue[route[i]];
155          if (o > CapacityParameter.ActualValue.Value) return false; // premature exit on capacity constraint violation
156        }
157      }
158      return true;
159    }
160
161    private bool SubrouteTardinessOK(List<int> route, int begin) {
162      double t = 0.0;
163      for (int i = begin + 1; i < route.Count; i++) {
164        t += Distance(route[i - 1], route[i]);
165        if (route[i] == 0) {
166          if (t < DueTimeParameter.ActualValue[0]) return true;
167          else return false;
168        } else {
169          if (t > DueTimeParameter.ActualValue[route[i]]) return false;
170          t = Math.Max(ReadyTimeParameter.ActualValue[route[i]], t);
171          t += ServiceTimeParameter.ActualValue[route[i]];
172        }
173      }
174      return true;
175    }
176
177    private bool SubrouteLoadOK(List<int> route, int begin) {
178      double o = 0.0;
179      for (int i = begin + 1; i < route.Count; i++) {
180        if (route[i] == 0) return (o < CapacityParameter.ActualValue.Value);
181        else {
182          o += DemandParameter.ActualValue[route[i]];
183        }
184      }
185      return (o < CapacityParameter.ActualValue.Value);
186    }
187
188    protected override List<int> CreateSolution() {
189      double alpha, beta, gamma;
190      alpha = N(Alpha.Value.Value, Math.Sqrt(AlphaVariance.Value.Value), RandomParameter.ActualValue);
191      beta = N(Beta.Value.Value, Math.Sqrt(BetaVariance.Value.Value), RandomParameter.ActualValue);
192      gamma = N(Gamma.Value.Value, Math.Sqrt(GammaVariance.Value.Value), RandomParameter.ActualValue);
193
194      double x0 = CoordinatesParameter.ActualValue[0, 0];
195      double y0 = CoordinatesParameter.ActualValue[0, 1];
196      double distance = 0;
197      double cost = 0;
198      double minimumCost = double.MaxValue;
199      List<int> unroutedList = new List<int>();
200      List<double> costList = new List<double>();
201      int index;
202      int indexOfMinimumCost = -1;
203      int indexOfCustomer = -1;
204
205      /*-----------------------------------------------------------------------------
206       * generate cost list
207       *-----------------------------------------------------------------------------
208       */
209      for (int i = 1; i <= Cities; i++) {
210        distance = Distance(i, 0);
211        if (CoordinatesParameter.ActualValue[i, 0] < x0) distance = -distance;
212        cost = -alpha * distance + // distance 0 <-> City[i]
213                 beta * (DueTimeParameter.ActualValue[i]) + // latest arrival time
214                 gamma * (Math.Asin((CoordinatesParameter.ActualValue[i, 1] - y0) / distance) / 360 * distance); // polar angle
215
216        index = 0;
217        while (index < costList.Count && costList[index] < cost) index++;
218        costList.Insert(index, cost);
219        unroutedList.Insert(index, i);
220      }
221
222      /*------------------------------------------------------------------------------
223       * route customers according to cost list
224       *------------------------------------------------------------------------------
225       */
226      int routeIndex = 0;
227      int currentRoute = 0;
228      int c;
229      int customer = -1;
230      int subTourCount = 1;
231      List<int> route = new List<int>(Cities + VehiclesParameter.ActualValue.Value - 1);
232      minimumCost = double.MaxValue;
233      indexOfMinimumCost = -1;
234      route.Add(0);
235      route.Add(0);
236      route.Insert(1, unroutedList[0]);
237      unroutedList.RemoveAt(0);
238      currentRoute = routeIndex;
239      routeIndex++;
240
241      do {
242        for (c = 0; c < unroutedList.Count; c++) {
243          for (int i = currentRoute + 1; i < route.Count; i++) {
244            route.Insert(i, (int)unroutedList[c]);
245            if (route[currentRoute] != 0) { throw new Exception("currentRoute not depot"); }
246            cost = TravelDistance(route, currentRoute);
247            if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute)) {
248              minimumCost = cost;
249              indexOfMinimumCost = i;
250              customer = (int)unroutedList[c];
251              indexOfCustomer = c;
252            }
253            route.RemoveAt(i);
254          }
255        }
256        // insert customer if found
257        if (indexOfMinimumCost != -1) {
258          route.Insert(indexOfMinimumCost, customer);
259          routeIndex++;
260          unroutedList.RemoveAt(indexOfCustomer);
261          costList.RemoveAt(indexOfCustomer);
262        } else { // no feasible customer found
263          routeIndex++;
264          route.Insert(routeIndex, 0);
265          currentRoute = routeIndex;
266          route.Insert(route.Count - 1, (int)unroutedList[0]);
267          unroutedList.RemoveAt(0);
268          routeIndex++;
269          subTourCount++;
270        }
271        // reset minimum   
272        minimumCost = double.MaxValue;
273        indexOfMinimumCost = -1;
274        indexOfCustomer = -1;
275        customer = -1;
276      } while (unroutedList.Count > 0);
277      while (route.Count < Cities + VehiclesParameter.ActualValue.Value - 1)
278        route.Add(0);
279
280      return route;
281    }
282  }
283}
Note: See TracBrowser for help on using the repository browser.