source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs @ 8653

Last change on this file since 8653 was 8653, checked in by svonolfe, 10 years ago

vehicles were not assigned correctly when a solution includes empty trips (#1953)

File size: 8.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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    [Storable]
39    public Permutation VehicleAssignment { get; private set; }
40
41    public PotvinEncoding(IVRPProblemInstance instance)
42      : base(instance) {
43      Unrouted = new List<int>();
44      VehicleAssignment = new Permutation(PermutationTypes.Absolute, instance.Vehicles.Value);
45    }
46
47    [StorableConstructor]
48    protected PotvinEncoding(bool serializing)
49      : base(serializing) {
50    }
51
52    public override IDeepCloneable Clone(Cloner cloner) {
53      return new PotvinEncoding(this, cloner);
54    }
55
56    protected PotvinEncoding(PotvinEncoding original, Cloner cloner)
57      : base(original, cloner) {
58      this.Unrouted = new List<int>(original.Unrouted);
59      this.VehicleAssignment = cloner.Clone<Permutation>(original.VehicleAssignment);
60    }
61
62    public override void Repair() {
63      List<Tour> toBeRemoved = new List<Tour>();
64      foreach (Tour tour in Tours) {
65        if (tour.Stops.Count == 0)
66          toBeRemoved.Add(tour);
67      }
68
69      foreach (Tour tour in toBeRemoved) {
70        int index = Tours.IndexOf(tour);
71        Tours.Remove(tour);
72        if (index < VehicleAssignment.Length) {
73          int vehicle = VehicleAssignment[index];
74          int max = System.Math.Min(VehicleAssignment.Length - 1, Tours.Count);
75
76          for (int i = index; i < max; i++) {
77            VehicleAssignment[i] = VehicleAssignment[i + 1];
78          }
79          VehicleAssignment[max] = vehicle;
80        }
81      }
82
83      while (Tours.Count > ProblemInstance.Vehicles.Value) {
84        Tour tour = Tours[Tours.Count - 1];
85        Tours[Tours.Count - 2].Stops.AddRange(tour.Stops);
86
87        Tours.Remove(tour);
88      }
89    }
90
91    public override int GetVehicleAssignment(int tour) {
92      return VehicleAssignment[tour];
93    }
94
95    public static PotvinEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance instance) {
96      PotvinEncoding solution = new PotvinEncoding(instance);
97
98      TourEncoding.ConvertFrom(encoding, solution, instance);
99
100      List<int> vehicles = new List<int>();
101      for (int i = 0; i < instance.Vehicles.Value; i++)
102        vehicles.Add(i);
103
104      int[] assignment = new int[instance.Vehicles.Value];
105      for (int i = 0; i < assignment.Length; i++)
106        assignment[i] = -1;
107
108      for (int i = 0; i < solution.Tours.Count; i++) {
109        int vehicle = encoding.GetVehicleAssignment(i);
110        assignment[i] = vehicle;
111        vehicles.Remove(vehicle);
112      }
113
114      for (int i = 0; i < instance.Vehicles.Value; i++) {
115        if (assignment[i] == -1) {
116          int vehicle = vehicles[0];
117          assignment[i] = vehicle;
118          vehicles.RemoveAt(0);
119        }
120      }
121
122      solution.VehicleAssignment = new Permutation(PermutationTypes.Absolute, assignment);
123
124      return solution;
125    }
126
127    public static PotvinEncoding ConvertFrom(List<int> route, IVRPProblemInstance instance) {
128      PotvinEncoding solution = new PotvinEncoding(instance);
129
130      solution.Tours = new ItemList<Tour>();
131
132      Tour tour = new Tour();
133      int routeIdx = 0;
134      for (int i = 0; i < route.Count; i++) {
135        if (route[i] <= 0) {
136          if (tour.Stops.Count > 0) {
137            solution.Tours.Add(tour);
138            tour = new Tour();
139          }
140          int vehicle = -route[i];
141          solution.VehicleAssignment[routeIdx] = vehicle;
142          routeIdx++;
143        } else {
144          tour.Stops.Add(route[i]);
145        }
146      }
147
148      solution.Repair();
149
150      return solution;
151    }
152
153    public double GetTourLength(Tour tour) {
154      return tour.GetTourLength(ProblemInstance, this);
155    }
156
157    public int FindBestInsertionPlace(Tour tour, int city, int positionToAvoid = -1) {
158      if (tour.Stops.Count == 0)
159        return 0;
160
161      int place = -1;
162      double minQuality = -1;
163
164      VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, this);
165
166      for (int i = 0; i <= tour.Stops.Count; i++) {
167        if (positionToAvoid != i) {
168          bool feasible;
169          double quality = ProblemInstance.GetInsertionCosts(eval, this, city, 0, i, out feasible);
170          if (place < 0 || quality < minQuality) {
171            place = i;
172            minQuality = quality;
173          }
174        }
175      }
176
177      if (place == -1)
178        place = 0;
179
180      return place;
181    }
182
183    public void InsertPair(Tour tour, int source, int target, IVRPProblemInstance problemInstance, int positionToAvoid = -1, int positionToAvoid2 = -1) {
184      int stops = tour.Stops.Count;
185      VRPEvaluation eval = problemInstance.EvaluateTour(tour, this);
186      double minCosts = double.MaxValue;
187      int sourceLocation = -1;
188      int targetLocation = -1;
189
190      for (int i = 0; i <= stops; i++) {
191        tour.Stops.Insert(i, source);
192        VRPEvaluation tourEval = problemInstance.EvaluateTour(tour, this);
193        double sourceCosts = tourEval.Quality - eval.Quality;
194
195        for (int j = i + 1; j <= stops + 1; j++) {
196          if (positionToAvoid != i || positionToAvoid2 != j || stops == 0) {
197            bool feasible;
198            double targetCosts = problemInstance.GetInsertionCosts(tourEval, this, target, 0, j, out feasible);
199
200            double costs = sourceCosts + targetCosts;
201            if (costs < minCosts) {
202              minCosts = costs;
203              sourceLocation = i;
204              targetLocation = j;
205            }
206          }
207        }
208        tour.Stops.Remove(source);
209      }
210
211      tour.Stops.Insert(sourceLocation, source);
212      tour.Stops.Insert(targetLocation, target);
213    }
214
215    public bool FindInsertionPlace(int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
216      route = -1;
217      place = -1;
218      double minDetour = double.MaxValue;
219
220      VRPEvaluation eval = ProblemInstance.Evaluate(this);
221      bool originalFeasible = ProblemInstance.Feasible(eval);
222
223      for (int tour = 0; tour < Tours.Count; tour++) {
224        if (tour != routeToAvoid) {
225          double length = eval.Quality;
226
227          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
228            bool feasible;
229            double detour = ProblemInstance.GetInsertionCosts(eval, this, city, tour, i, out feasible);
230
231            if (feasible || allowInfeasible) {
232              if (route < 0 || detour < minDetour) {
233                route = tour;
234                place = i;
235                minDetour = detour;
236              }
237            }
238          }
239        }
240      }
241
242      return route >= 0 && place >= 0;
243    }
244  }
245}
Note: See TracBrowser for help on using the repository browser.