1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HEAL.Attic;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Problems.VehicleRouting.Interfaces;


31  using HeuristicLab.Problems.VehicleRouting.Variants;


32 


33  namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {


34  [Item("MultiDepotVRPProblemInstance", "Represents a multi depot VRP instance.")]


35  [StorableType("20788CA48AA04A5781180D7C3FEF1AA4")]


36  public class MultiDepotVRPProblemInstance : VRPProblemInstance, IMultiDepotProblemInstance {


37  protected IValueParameter<IntValue> DepotsParameter {


38  get { return (IValueParameter<IntValue>)Parameters["Depots"]; }


39  }


40 


41  protected IValueParameter<IntArray> VehicleDepotAssignmentParameter {


42  get { return (IValueParameter<IntArray>)Parameters["VehicleDepotAssignment"]; }


43  }


44 


45  public IntValue Depots {


46  get {


47  return DepotsParameter.Value;


48  }


49  }


50 


51  public IntArray VehicleDepotAssignment {


52  get {


53  return VehicleDepotAssignmentParameter.Value;


54  }


55  set {


56  VehicleDepotAssignmentParameter.Value = value;


57  }


58  }


59 


60  public override IEnumerable<IOperator> FilterOperators(IEnumerable<IOperator> operators) {


61  return base.FilterOperators(operators).Where(x => x is IMultiDepotOperator);


62  }


63 


64  public override IntValue Cities => new IntValue(Demand.Length);


65 


66 


67  public override double GetDemand(int city) {


68  return base.GetDemand(city  1);


69  }


70 


71  public override double[] GetCoordinates(int city) {


72  double[] coordinates;


73 


74  if (city == 0) {


75  //calculate centroid


76  coordinates = new double[Coordinates.Columns];


77 


78  for (int i = 0; i < Depots.Value; i++) {


79  for (int j = 0; j < coordinates.Length; j++) {


80  coordinates[j] += Coordinates[i, j];


81  }


82  }


83 


84  for (int j = 0; j < coordinates.Length; j++) {


85  coordinates[j] /= (double)Depots.Value;


86  }


87  } else {


88  city += Depots.Value  1;


89  coordinates = base.GetCoordinates(city);


90  }


91 


92  return coordinates;


93  }


94 


95  public int GetDepot(int customer, IVRPEncodedSolution solution) {


96  int depot = 1;


97 


98  Tour tour =


99  solution.GetTours().FirstOrDefault(t => t.Stops.Contains(customer));


100 


101  if (tour != null) {


102  int tourIndex = solution.GetTourIndex(tour);


103  int vehicle = solution.GetVehicleAssignment(tourIndex);


104  depot = VehicleDepotAssignment[vehicle];


105  }


106 


107  return depot;


108  }


109 


110  public override double GetDistance(int start, int end, IVRPEncodedSolution solution) {


111  if (start == 0 && end == 0)


112  return 0;


113 


114  if (start == 0) {


115  start = GetDepot(end, solution);


116  end += Depots.Value  1;


117  } else if (end == 0) {


118  end = GetDepot(start, solution);


119  start += Depots.Value  1;


120  } else {


121  start += Depots.Value  1;


122  end += Depots.Value  1;


123  }


124 


125  return base.GetDistance(start, end, solution);


126  }


127 


128  public override double GetInsertionDistance(int start, int customer, int end, IVRPEncodedSolution solution,


129  out double startDistance, out double endDistance) {


130  if (start == 0) {


131  start = GetDepot(end, solution);


132  end += Depots.Value  1;


133  } else if (end == 0) {


134  end = GetDepot(start, solution);


135  start += Depots.Value  1;


136  } else {


137  start += Depots.Value  1;


138  end += Depots.Value  1;


139  }


140  customer += Depots.Value  1;


141 


142  double distance = base.GetDistance(start, end, solution);


143 


144  startDistance = base.GetDistance(start, customer, solution);


145  endDistance = base.GetDistance(customer, end, solution);


146 


147  double newDistance = startDistance + endDistance;


148 


149  return newDistance  distance;


150  }


151  protected override void EvaluateTour(VRPEvaluation eval, Tour tour, IVRPEncodedSolution solution) {


152  TourInsertionInfo tourInfo = new TourInsertionInfo(solution.GetVehicleAssignment(solution.GetTourIndex(tour)));


153  eval.InsertionInfo.AddTourInsertionInfo(tourInfo);


154 


155  double distance = 0.0;


156  double quality = 0.0;


157 


158  //simulate a tour, start and end at depot


159  for (int i = 0; i <= tour.Stops.Count; i++) {


160  int start = 0;


161  if (i > 0)


162  start = tour.Stops[i  1];


163  int end = 0;


164  if (i < tour.Stops.Count)


165  end = tour.Stops[i];


166 


167  //drive there


168  double currentDistace = GetDistance(start, end, solution);


169  distance += currentDistace;


170 


171  StopInsertionInfo stopInfo = new StopInsertionInfo(start, end);


172  tourInfo.AddStopInsertionInfo(stopInfo);


173  }


174 


175  //Fleet usage


176  quality += FleetUsageFactor.Value;


177  //Distance


178  quality += DistanceFactor.Value * distance;


179 


180  eval.Distance += distance;


181  eval.VehicleUtilization += 1;


182 


183  eval.Quality += quality;


184  tourInfo.Quality = quality;


185  }


186 


187  protected override double GetTourInsertionCosts(IVRPEncodedSolution solution, TourInsertionInfo tourInsertionInfo, int index, int customer,


188  out bool feasible) {


189  StopInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index);


190 


191  double costs = 0;


192  feasible = true;


193  double startDistance, endDistance;


194 


195  costs += GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution, out startDistance, out endDistance);


196 


197  return costs;


198  }


199 


200  [StorableConstructor]


201  protected MultiDepotVRPProblemInstance(StorableConstructorFlag _) : base(_) { }


202  protected MultiDepotVRPProblemInstance(MultiDepotVRPProblemInstance original, Cloner cloner)


203  : base(original, cloner) {


204  AttachEventHandlers();


205  }


206  public MultiDepotVRPProblemInstance() {


207  Parameters.Add(new ValueParameter<IntValue>("Depots", "The number of depots", new IntValue(0)));


208  Parameters.Add(new ValueParameter<IntArray>("VehicleDepotAssignment", "The assignment of vehicles to depots", new IntArray()));


209  AttachEventHandlers();


210  }


211 


212  public override IDeepCloneable Clone(Cloner cloner) {


213  return new MultiDepotVRPProblemInstance(this, cloner);


214  }


215 


216  [StorableHook(HookType.AfterDeserialization)]


217  private void AfterDeserialization() {


218  AttachEventHandlers();


219  }


220 


221  private void AttachEventHandlers() {


222  DepotsParameter.ValueChanged += DepotsParameter_ValueChanged;


223  Depots.ValueChanged += Depots_ValueChanged;


224  VehicleDepotAssignmentParameter.ValueChanged += VehicleDepotAssignmentParameter_ValueChanged;


225  VehicleDepotAssignment.Reset += VehicleDepotAssignment_Changed;


226  VehicleDepotAssignment.ItemChanged += VehicleDepotAssignment_Changed;


227  }


228 


229  #region Event handlers


230  private void DepotsParameter_ValueChanged(object sender, EventArgs e) {


231  Depots.ValueChanged += Depots_ValueChanged;


232  EvalBestKnownSolution();


233  }


234  private void Depots_ValueChanged(object sender, EventArgs e) {


235  EvalBestKnownSolution();


236  }


237  private void VehicleDepotAssignmentParameter_ValueChanged(object sender, EventArgs e) {


238  VehicleDepotAssignment.Reset += VehicleDepotAssignment_Changed;


239  VehicleDepotAssignment.ItemChanged += VehicleDepotAssignment_Changed;


240  EvalBestKnownSolution();


241  }


242  private void VehicleDepotAssignment_Changed(object sender, EventArgs e) {


243  EvalBestKnownSolution();


244  }


245  #endregion


246  }


247  } 
