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

Last change on this file since 8053 was 8053, checked in by ascheibe, 10 years ago

#1722 fixed more licensing information and source formatting

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