Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.3/Encodings/Prins/PrinsEncoding.cs @ 6449

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

Improved performance of many VRP operators by optimizing the parameter lookup (#1561)

File size: 9.2 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.Encodings.PermutationEncoding;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Problems.VehicleRouting.Encodings.General;
30
31namespace HeuristicLab.Problems.VehicleRouting.Encodings.Prins {
32  [Item("PrinsEncoding", "Represents an Prins encoding of VRP solutions. It is implemented as described in Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 12:1985-2002.")]
33  [StorableClass]
34  public class PrinsEncoding : PermutationEncoding {
35    [Storable]
36    private int cities;
37
38    [Storable]
39    private DoubleMatrix coordinates;
40
41    [Storable]
42    private BoolValue useDistanceMatrix;
43
44    [Storable]
45    DoubleArray dueTimeArray;
46   
47    [Storable]
48    DoubleArray serviceTimeArray;
49
50    [Storable]
51    DoubleArray readyTimeArray;
52   
53    [Storable]
54    DoubleArray demandArray;
55
56    [Storable]
57    DoubleValue capacity;
58
59    [Storable]
60    DoubleValue fleetUsageFactor;
61
62    [Storable]
63    DoubleValue timeFactor;
64
65    [Storable]
66    DoubleValue distanceFactor;
67
68    [Storable]
69    DoubleValue overloadPenalty;
70
71    [Storable]
72    DoubleValue tardinessPenalty;
73
74    #region IVRPEncoding Members
75    public override List<Tour> GetTours(ILookupParameter<DoubleMatrix> distanceMatrix, int maxVehicles = int.MaxValue) {
76      List<Tour> result = new List<Tour>();
77
78      DistanceMatrix distMatrix = VRPUtilities.GetDistanceMatrix(coordinates, distanceMatrix, useDistanceMatrix);
79
80      //Split permutation into vector P
81      int[] P = new int[cities + 1];
82      for (int i = 0; i <= cities; i++)
83        P[i] = -1;
84
85      double[] V = new double[cities + 1];
86      V[0] = 0;
87      for (int i = 1; i <= cities; i++) {
88        V[i] = int.MaxValue;
89      }
90
91      for (int i = 1; i <= cities; i++) {
92        int j = i;
93        Tour tour = new Tour();
94        bool feasible = true;
95
96        do {
97          tour.Cities.Add(this[j-1] + 1);
98
99          TourEvaluation eval = VRPEvaluator.EvaluateTour(tour,
100            dueTimeArray,
101            serviceTimeArray,
102            readyTimeArray,
103            demandArray,
104            capacity,
105            fleetUsageFactor,
106            timeFactor,
107            distanceFactor,
108            overloadPenalty,
109            tardinessPenalty,
110            distMatrix);
111
112          double cost = eval.Quality;
113          feasible = eval.Overload < double.Epsilon && eval.Tardiness < double.Epsilon;
114
115          if (feasible) {
116            if (V[i - 1] + cost < V[j]) {
117              V[j] = V[i - 1] + cost;
118              P[j] = i - 1;
119            }
120            j++;
121          }
122
123        } while (j <= cities && feasible);
124      }
125
126      //extract VRP solution from vector P
127      int index = 0;
128      int index2 = cities;
129      Tour trip = null;
130      do {
131        index = P[index2];
132        trip = new Tour();
133
134        for (int k = index + 1; k <= index2; k++) {
135          trip.Cities.Add(this[k - 1] + 1);
136        }
137
138        if (trip.Cities.Count > 0)
139          result.Add(trip);
140
141        index2 = index;
142      } while (index != 0);
143
144      //if there are too many vehicles - repair
145      while (result.Count > maxVehicles) {
146        Tour tour = result[result.Count - 1];
147
148        //find predecessor / successor in permutation
149        int predecessorIndex = Array.IndexOf(this.array, tour.Cities[0] - 1) - 1;
150        if (predecessorIndex >= 0) {
151          int predecessor = this[predecessorIndex] + 1;
152
153          foreach (Tour t in result) {
154            int insertPosition = t.Cities.IndexOf(predecessor) + 1;
155            if (insertPosition != -1) {
156              t.Cities.InsertRange(insertPosition, tour.Cities);
157              break;
158            }
159          }
160        } else {
161          int successorIndex = Array.IndexOf(this.array,
162            tour.Cities[tour.Cities.Count - 1] - 1) + 1;
163          int successor = this[successorIndex] + 1;
164
165          foreach (Tour t in result) {
166            int insertPosition = t.Cities.IndexOf(successor);
167            if (insertPosition != -1) {
168              t.Cities.InsertRange(insertPosition, tour.Cities);
169              break;
170            }
171          }
172        }
173
174        result.Remove(tour);
175      }
176
177      return result;
178    }
179    #endregion
180   
181    [StorableConstructor]
182    protected PrinsEncoding(bool deserializing) : base(deserializing) { }
183    protected PrinsEncoding(PrinsEncoding original, Cloner cloner)
184      : base(original, cloner) {
185      this.cities = original.cities;
186      this.dueTimeArray = original.dueTimeArray;
187      this.serviceTimeArray = original.serviceTimeArray;
188      this.readyTimeArray = original.readyTimeArray;
189      this.demandArray = original.demandArray;
190      this.capacity = original.capacity;
191      this.fleetUsageFactor = original.fleetUsageFactor;
192      this.timeFactor = original.timeFactor;
193      this.distanceFactor = original.distanceFactor;
194      this.overloadPenalty = original.overloadPenalty;
195      this.tardinessPenalty = original.tardinessPenalty;
196      this.coordinates = original.coordinates;
197      this.useDistanceMatrix = original.useDistanceMatrix;
198    }
199    public override IDeepCloneable Clone(Cloner cloner) {
200      return new PrinsEncoding(this, cloner);
201    }
202    public PrinsEncoding(Permutation permutation, int cities,
203      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
204      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
205      DoubleMatrix coordinates, BoolValue useDistanceMatrix)
206      : base(permutation) {
207        this.cities = cities;
208        this.dueTimeArray = dueTimeArray;
209        this.serviceTimeArray = serviceTimeArray;
210        this.readyTimeArray = readyTimeArray;
211        this.demandArray = demandArray;
212        this.capacity = capacity;
213        this.coordinates = coordinates;
214        this.useDistanceMatrix = useDistanceMatrix;
215        this.fleetUsageFactor = fleetUsageFactor;
216        this.timeFactor = timeFactor;
217        this.distanceFactor = distanceFactor;
218        this.overloadPenalty = overloadPenalty;
219        this.tardinessPenalty = tardinessPenalty;
220    }
221
222    public static PrinsEncoding ConvertFrom(IVRPEncoding encoding, int cities,
223      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
224      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
225      DoubleMatrix coordinates, ILookupParameter<DoubleMatrix> distanceMatrix, BoolValue useDistanceMatrix) {
226      List<Tour> tours = encoding.GetTours(distanceMatrix);
227      List<int> route = new List<int>();
228
229      foreach (Tour tour in tours) {
230        foreach (int city in tour.Cities)
231          route.Add(city - 1);
232      }
233
234      return new PrinsEncoding(
235        new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), cities,
236        dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
237        fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
238        coordinates, useDistanceMatrix);
239    }
240
241    public static PrinsEncoding ConvertFrom(List<int> routeParam, int cities,
242      DoubleArray dueTimeArray, DoubleArray serviceTimeArray, DoubleArray readyTimeArray, DoubleArray demandArray, DoubleValue capacity,
243      DoubleValue fleetUsageFactor, DoubleValue timeFactor, DoubleValue distanceFactor, DoubleValue overloadPenalty, DoubleValue tardinessPenalty,
244      DoubleMatrix coordinates, BoolValue useDistanceMatrix) {
245      List<int> route = new List<int>(routeParam);
246
247      while (route.Remove(0)) { //remove all delimiters (0)
248      }
249
250      for (int i = 0; i < route.Count; i++)
251        route[i]--;
252
253      return new PrinsEncoding(
254        new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), cities,
255        dueTimeArray, serviceTimeArray, readyTimeArray, demandArray, capacity,
256        fleetUsageFactor, timeFactor, distanceFactor, overloadPenalty, tardinessPenalty,
257        coordinates, useDistanceMatrix);
258    }
259  }
260}
Note: See TracBrowser for help on using the repository browser.