#region License Information /* HeuristicLab * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Encodings.PermutationEncoding; using HeuristicLab.Persistence; using HeuristicLab.Problems.VehicleRouting.Interfaces; using HeuristicLab.Problems.VehicleRouting.ProblemInstances; namespace HeuristicLab.Problems.VehicleRouting.Encodings.Prins { [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.")] [StorableType("89634df3-7e25-4a6c-861e-903310ad7819")] public class PrinsEncoding : General.PermutationEncoding { #region IVRPEncoding Members public override int GetTourIndex(Tour tour) { return 0; } public override List GetTours() { List result = new List(); int cities = ProblemInstance.Cities.Value; //Split permutation into vector P int[] P = new int[cities + 1]; for (int i = 0; i <= cities; i++) P[i] = -1; double[] V = new double[cities + 1]; V[0] = 0; for (int i = 1; i <= cities; i++) { V[i] = double.MaxValue; } for (int i = 1; i <= cities; i++) { int j = i; Tour tour = new Tour(); bool feasible = true; do { tour.Stops.Add(this[j - 1] + 1); VRPEvaluation eval = ProblemInstance.EvaluateTour(tour, this); double cost = eval.Quality; feasible = ProblemInstance.Feasible(eval); if (feasible || j == i) { if (V[i - 1] + cost < V[j]) { V[j] = V[i - 1] + cost; P[j] = i - 1; } j++; } } while (j <= cities && feasible); } //extract VRP solution from vector P int index = 0; int index2 = cities; Tour trip = null; do { index = P[index2]; trip = new Tour(); for (int k = index + 1; k <= index2; k++) { trip.Stops.Add(this[k - 1] + 1); } if (trip.Stops.Count > 0) result.Add(trip); index2 = index; } while (index != 0); //if there are too many vehicles - repair while (result.Count > ProblemInstance.Vehicles.Value) { Tour tour = result[result.Count - 1]; //find predecessor / successor in permutation int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0] - 1) - 1; if (predecessorIndex >= 0) { int predecessor = this[predecessorIndex] + 1; foreach (Tour t in result) { int insertPosition = t.Stops.IndexOf(predecessor) + 1; if (insertPosition != -1) { t.Stops.InsertRange(insertPosition, tour.Stops); break; } } } else { int successorIndex = Array.IndexOf(this.array, tour.Stops[tour.Stops.Count - 1] - 1) + 1; int successor = this[successorIndex] + 1; foreach (Tour t in result) { int insertPosition = t.Stops.IndexOf(successor); if (insertPosition != -1) { t.Stops.InsertRange(insertPosition, tour.Stops); break; } } } result.Remove(tour); } return result; } #endregion public PrinsEncoding(Permutation permutation, IVRPProblemInstance problemInstance) : base(permutation, problemInstance) { } [StorableConstructor] protected PrinsEncoding(bool serializing) : base(serializing) { } public override IDeepCloneable Clone(Cloner cloner) { return new PrinsEncoding(this, cloner); } protected PrinsEncoding(PrinsEncoding original, Cloner cloner) : base(original, cloner) { } public static PrinsEncoding ConvertFrom(IVRPEncoding encoding, IVRPProblemInstance problemInstance) { List tours = encoding.GetTours(); List route = new List(); foreach (Tour tour in tours) { foreach (int city in tour.Stops) route.Add(city - 1); } return new PrinsEncoding( new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance); } public static PrinsEncoding ConvertFrom(List routeParam, IVRPProblemInstance problemInstance) { List route = new List(routeParam); while (route.Remove(0)) { //remove all delimiters (0) } for (int i = 0; i < route.Count; i++) route[i]--; return new PrinsEncoding( new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance); } } }