#region License Information /* HeuristicLab * Copyright (C) 2002-2010 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 HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.PermutationEncoding; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using System.Collections.Generic; using HeuristicLab.Problems.VehicleRouting.Encodings.General; using System; using HeuristicLab.Problems.VehicleRouting.Interfaces; namespace HeuristicLab.Problems.VehicleRouting.Encodings.Zhu { [Item("ZhuEncoding", "Represents a Zhu encoding of VRP solutions. It is implemented as described in Zhu, K.Q. (2000). A New Genetic Algorithm For VRPTW. Proceedings of the International Conference on Artificial Intelligence.")] [StorableClass] public class ZhuEncoding : PermutationEncoding { #region IVRPEncoding Members public override List GetTours() { List result = new List(); Tour newTour = new Tour(); for (int i = 0; i < this.Length; i++) { int city = this[i] + 1; newTour.Stops.Add(city); if (!ProblemInstance.Feasible(newTour)) { newTour.Stops.Remove(city); if (newTour.Stops.Count > 0) result.Add(newTour); newTour = new Tour(); newTour.Stops.Add(city); } } if (newTour.Stops.Count > 0) result.Add(newTour); //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 ZhuEncoding(Permutation permutation, IVRPProblemInstance problemInstance) : base(permutation, problemInstance) { } public override IDeepCloneable Clone(Cloner cloner) { return new ZhuEncoding(this, cloner); } protected ZhuEncoding(ZhuEncoding original, Cloner cloner) : base(original, cloner) { } [StorableConstructor] private ZhuEncoding(bool serializing) : base(serializing) { } public static ZhuEncoding 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 ZhuEncoding( new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance); } public static ZhuEncoding 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 ZhuEncoding( new Permutation(PermutationTypes.RelativeUndirected, route.ToArray()), problemInstance); } } }