Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Async/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs @ 12025

Last change on this file since 12025 was 11428, checked in by pfleck, 10 years ago

#2229

  • The IVRPData now specifies an optional BestKnownTourVehicleAssignment property. This can be used for solutions where a specific assignment for tours to vehicles is necessary.
  • The VRPInterpreter interpret the new BestKnownTourVehicleAssignment directly as VehicleAssignment in the created PotvinEncoding.
  • Minor refactoring in (I)VRPInstanceProvider.
File size: 8.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27using HeuristicLab.Problems.VehicleRouting.Encodings.General;
28using HeuristicLab.Problems.VehicleRouting.Interfaces;
29using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
30
31namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
32  [Item("PotvinEncoding", "Represents a potvin encoding of VRP solutions. It is implemented as described in Potvin, J.-Y. and Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal of Computing, 8:165–172.")]
33  [StorableClass]
34  public class PotvinEncoding : TourEncoding {
35    [Storable]
36    public List<int> Unrouted { get; set; }
37
38    // VehicleAssignment[tour] retreives the assigned vehicle for the given tour
39    [Storable]
40    public Permutation VehicleAssignment { get; private set; }
41
42    public PotvinEncoding(IVRPProblemInstance instance)
43      : base(instance) {
44      Unrouted = new List<int>();
45      VehicleAssignment = new Permutation(PermutationTypes.Absolute, instance.Vehicles.Value);
46    }
47
48    [StorableConstructor]
49    protected PotvinEncoding(bool serializing)
50      : base(serializing) {
51    }
52
53    public override IDeepCloneable Clone(Cloner cloner) {
54      return new PotvinEncoding(this, cloner);
55    }
56
57    protected PotvinEncoding(PotvinEncoding original, Cloner cloner)
58      : base(original, cloner) {
59      this.Unrouted = new List<int>(original.Unrouted);
60      this.VehicleAssignment = cloner.Clone<Permutation>(original.VehicleAssignment);
61    }
62
63    public override void Repair() {
64      List<Tour> toBeRemoved = new List<Tour>();
65      foreach (Tour tour in Tours) {
66        if (tour.Stops.Count == 0)
67          toBeRemoved.Add(tour);
68      }
69
70      foreach (Tour tour in toBeRemoved) {
71        int index = Tours.IndexOf(tour);
72        Tours.Remove(tour);
73        if (index < VehicleAssignment.Length) {
74          int vehicle = VehicleAssignment[index];
75          int max = System.Math.Min(VehicleAssignment.Length - 1, Tours.Count);
76
77          for (int i = index; i < max; i++) {
78            VehicleAssignment[i] = VehicleAssignment[i + 1];
79          }
80          VehicleAssignment[max] = vehicle;
81        }
82      }
83
84      while (Tours.Count > ProblemInstance.Vehicles.Value) {
85        Tour tour = Tours[Tours.Count - 1];
86        Tours[Tours.Count - 2].Stops.AddRange(tour.Stops);
87
88        Tours.Remove(tour);
89      }
90    }
91
92    public override int GetVehicleAssignment(int tour) {
93      return VehicleAssignment[tour];
94    }
95
96    public static PotvinEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) {
97      PotvinEncoding solution = new PotvinEncoding(instance);
98
99      TourEncoding.ConvertFrom(encoding, solution, instance);
100
101      List<int> vehicles = new List<int>();
102      for (int i = 0; i < instance.Vehicles.Value; i++)
103        vehicles.Add(i);
104
105      int[] assignment = new int[instance.Vehicles.Value];
106      for (int i = 0; i < assignment.Length; i++)
107        assignment[i] = -1;
108
109      for (int i = 0; i < solution.Tours.Count; i++) {
110        int vehicle = encoding.GetVehicleAssignment(i);
111        assignment[i] = vehicle;
112        vehicles.Remove(vehicle);
113      }
114
115      for (int i = 0; i < instance.Vehicles.Value; i++) {
116        if (assignment[i] == -1) {
117          int vehicle = vehicles[0];
118          assignment[i] = vehicle;
119          vehicles.RemoveAt(0);
120        }
121      }
122
123      solution.VehicleAssignment = new Permutation(PermutationTypes.Absolute, assignment);
124
125      return solution;
126    }
127
128    public static PotvinEncoding ConvertFrom(List<int> route, IVRPProblemInstance instance) {
129      PotvinEncoding solution = new PotvinEncoding(instance);
130
131      solution.Tours = new ItemList<Tour>();
132
133      Tour tour = new Tour();
134      int routeIdx = 0;
135      for (int i = 0; i < route.Count; i++) {
136        if (route[i] <= 0) {
137          if (tour.Stops.Count > 0) {
138            solution.Tours.Add(tour);
139            tour = new Tour();
140          }
141          int vehicle = -route[i];
142          solution.VehicleAssignment[routeIdx] = vehicle;
143          routeIdx++;
144        } else {
145          tour.Stops.Add(route[i]);
146        }
147      }
148
149      solution.Repair();
150
151      return solution;
152    }
153
154    public double GetTourLength(Tour tour) {
155      return tour.GetTourLength(ProblemInstance, this);
156    }
157
158    public int FindBestInsertionPlace(Tour tour, int city, int positionToAvoid = -1) {
159      if (tour.Stops.Count == 0)
160        return 0;
161
162      int place = -1;
163      double minQuality = -1;
164
165      VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, this);
166
167      for (int i = 0; i <= tour.Stops.Count; i++) {
168        if (positionToAvoid != i) {
169          bool feasible;
170          double quality = ProblemInstance.GetInsertionCosts(eval, this, city, 0, i, out feasible);
171          if (place < 0 || quality < minQuality) {
172            place = i;
173            minQuality = quality;
174          }
175        }
176      }
177
178      if (place == -1)
179        place = 0;
180
181      return place;
182    }
183
184    public void InsertPair(Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
185      int stops = tour.Stops.Count;
186      VRPEvaluation eval = problemInstance.EvaluateTour(tour, this);
187      double minCosts = double.MaxValue;
188      int sourceLocation = -1;
189      int targetLocation = -1;
190
191      for (int i = 0; i <= stops; i++) {
192        tour.Stops.Insert(i, source);
193        VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, this);
194        double sourceCosts = tourEval.Quality - eval.Quality;
195
196        for (int j = i + 1; j <= stops + 1; j++) {
197          if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
198            bool feasible;
199            double targetCosts = problemInstance.GetInsertionCosts(tourEval, this, target, 0, j, out feasible);
200
201            double costs = sourceCosts + targetCosts;
202            if (costs < minCosts) {
203              minCosts = costs;
204              sourceLocation = i;
205              targetLocation = j;
206            }
207          }
208        }
209        tour.Stops.Remove(source);
210      }
211
212      tour.Stops.Insert(sourceLocation, source);
213      tour.Stops.Insert(targetLocation, target);
214    }
215
216    public bool FindInsertionPlace(int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
217      route = -1;
218      place = -1;
219      double minDetour = double.MaxValue;
220
221      VRPEvaluation eval = ProblemInstance.Evaluate(this);
222      bool originalFeasible = ProblemInstance.Feasible(eval);
223
224      for (int tour = 0; tour < Tours.Count; tour++) {
225        if (tour != routeToAvoid) {
226          double length = eval.Quality;
227
228          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
229            bool feasible;
230            double detour = ProblemInstance.GetInsertionCosts(eval, this, city, tour, i, out feasible);
231
232            if (feasible || allowInfeasible) {
233              if (route < 0 || detour < minDetour) {
234                route = tour;
235                place = i;
236                minDetour = detour;
237              }
238            }
239          }
240        }
241      }
242
243      return route >= 0 && place >= 0;
244    }
245  }
246}
Note: See TracBrowser for help on using the repository browser.