[4150] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[5445] | 3 | * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[4150] | 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 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
[4722] | 24 | using HeuristicLab.Common;
|
---|
[4150] | 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Data;
|
---|
| 27 | using HeuristicLab.Optimization;
|
---|
| 28 | using HeuristicLab.Parameters;
|
---|
| 29 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 30 |
|
---|
[4154] | 31 | namespace HeuristicLab.Problems.VehicleRouting.Encodings.General {
|
---|
[4179] | 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.")]
|
---|
[4150] | 33 | [StorableClass]
|
---|
[4179] | 34 | public sealed class PushForwardCreator : DefaultRepresentationCreator, IStochasticOperator {
|
---|
[4150] | 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 |
|
---|
[4179] | 60 | [StorableConstructor]
|
---|
| 61 | private PushForwardCreator(bool deserializing) : base(deserializing) { }
|
---|
[4722] | 62 | private PushForwardCreator(PushForwardCreator original, Cloner cloner) : base(original, cloner) { }
|
---|
| 63 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 64 | return new PushForwardCreator(this, cloner);
|
---|
| 65 | }
|
---|
[4179] | 66 |
|
---|
[4150] | 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 |
|
---|
[6618] | 93 | private double CalculateDistance(int start, int end, DoubleMatrix coordinates) {
|
---|
[4150] | 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 |
|
---|
[6618] | 104 | private DoubleMatrix CreateDistanceMatrix(DoubleMatrix coordinates) {
|
---|
[4150] | 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++) {
|
---|
[6618] | 109 | double distance = CalculateDistance(i, j, coordinates);
|
---|
[4150] | 110 |
|
---|
| 111 | distanceMatrix[i, j] = distance;
|
---|
| 112 | distanceMatrix[j, i] = distance;
|
---|
| 113 | }
|
---|
| 114 | }
|
---|
| 115 |
|
---|
| 116 | return distanceMatrix;
|
---|
| 117 | }
|
---|
| 118 |
|
---|
[6618] | 119 | private double Distance(int start, int end, DoubleMatrix coordinates, bool useDistanceMatrix) {
|
---|
[4150] | 120 | double distance = 0.0;
|
---|
| 121 |
|
---|
[6618] | 122 | if (useDistanceMatrix) {
|
---|
| 123 | distance = coordinates[start, end];
|
---|
| 124 | } else {
|
---|
| 125 | distance = CalculateDistance(start, end, coordinates);
|
---|
[4150] | 126 | }
|
---|
| 127 |
|
---|
| 128 | return distance;
|
---|
| 129 | }
|
---|
| 130 |
|
---|
[6618] | 131 | private double TravelDistance(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix) {
|
---|
[4150] | 132 | double distance = 0;
|
---|
| 133 | for (int i = begin; i < route.Count - 1 && (i == begin || route[i] != 0); i++) {
|
---|
[6618] | 134 | distance += Distance(route[i], route[i + 1], coordinates, useDistanceMatrix);
|
---|
[4150] | 135 | }
|
---|
| 136 | return distance;
|
---|
| 137 | }
|
---|
| 138 |
|
---|
[6618] | 139 | private bool SubrouteConstraintsOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
|
---|
| 140 | DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime, DoubleArray demand, DoubleValue capacity) {
|
---|
[4150] | 141 | double t = 0.0, o = 0.0;
|
---|
| 142 | for (int i = begin + 1; i < route.Count; i++) {
|
---|
[6618] | 143 | t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
|
---|
[4150] | 144 | if (route[i] == 0) return (t < DueTimeParameter.ActualValue[0]); // violation on capacity constraint is handled below
|
---|
| 145 | else {
|
---|
[6618] | 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
|
---|
[4150] | 151 | }
|
---|
| 152 | }
|
---|
| 153 | return true;
|
---|
| 154 | }
|
---|
| 155 |
|
---|
[6618] | 156 | private bool SubrouteTardinessOK(List<int> route, int begin, DoubleMatrix coordinates, bool useDistanceMatrix,
|
---|
| 157 | DoubleArray dueTime, DoubleArray readyTime, DoubleArray serviceTime) {
|
---|
[4150] | 158 | double t = 0.0;
|
---|
| 159 | for (int i = begin + 1; i < route.Count; i++) {
|
---|
[6618] | 160 | t += Distance(route[i - 1], route[i], coordinates, useDistanceMatrix);
|
---|
[4150] | 161 | if (route[i] == 0) {
|
---|
[6618] | 162 | if (t < dueTime[0]) return true;
|
---|
[4150] | 163 | else return false;
|
---|
| 164 | } else {
|
---|
[6618] | 165 | if (t > dueTime[route[i]]) return false;
|
---|
| 166 | t = Math.Max(readyTime[route[i]], t);
|
---|
| 167 | t += serviceTime[route[i]];
|
---|
[4150] | 168 | }
|
---|
| 169 | }
|
---|
| 170 | return true;
|
---|
| 171 | }
|
---|
| 172 |
|
---|
[6618] | 173 | private bool SubrouteLoadOK(List<int> route, int begin, DoubleValue capacity, DoubleArray demand) {
|
---|
[4150] | 174 | double o = 0.0;
|
---|
| 175 | for (int i = begin + 1; i < route.Count; i++) {
|
---|
[6618] | 176 | if (route[i] == 0) return (o < capacity.Value);
|
---|
[4150] | 177 | else {
|
---|
[6618] | 178 | o += demand[route[i]];
|
---|
[4150] | 179 | }
|
---|
| 180 | }
|
---|
[6618] | 181 | return (o < capacity.Value);
|
---|
[4150] | 182 | }
|
---|
| 183 |
|
---|
| 184 | protected override List<int> CreateSolution() {
|
---|
[6618] | 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);
|
---|
[4150] | 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 |
|
---|
[6618] | 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 |
|
---|
[4150] | 218 | /*-----------------------------------------------------------------------------
|
---|
| 219 | * generate cost list
|
---|
| 220 | *-----------------------------------------------------------------------------
|
---|
| 221 | */
|
---|
[4154] | 222 | for (int i = 1; i <= Cities; i++) {
|
---|
[6618] | 223 | distance = Distance(i, 0, coordinates, useDistanceMatrix);
|
---|
| 224 | if (coordinates[i, 0] < x0) distance = -distance;
|
---|
[4150] | 225 | cost = -alpha * distance + // distance 0 <-> City[i]
|
---|
| 226 | beta * (DueTimeParameter.ActualValue[i]) + // latest arrival time
|
---|
[6618] | 227 | gamma * (Math.Asin((coordinates[i, 1] - y0) / distance) / 360 * distance); // polar angle
|
---|
[4150] | 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;
|
---|
[6618] | 244 |
|
---|
| 245 | List<int> route = new List<int>(Cities + vehicles - 1);
|
---|
[4150] | 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"); }
|
---|
[6618] | 260 | cost = TravelDistance(route, currentRoute, coordinates, useDistanceMatrix);
|
---|
| 261 | if (cost < minimumCost && SubrouteConstraintsOK(route, currentRoute, coordinates, useDistanceMatrix, dueTime, readyTime, serviceTime, demand, capacity)) {
|
---|
[4150] | 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);
|
---|
[6618] | 291 | while (route.Count < Cities + vehicles)
|
---|
[4150] | 292 | route.Add(0);
|
---|
| 293 |
|
---|
| 294 | return route;
|
---|
| 295 | }
|
---|
| 296 | }
|
---|
| 297 | }
|
---|