Changeset 5127


Ignore:
Timestamp:
12/17/10 13:42:53 (10 years ago)
Author:
svonolfe
Message:

Implemented unified tabu search (WIP) (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4
Files:
20 added
10 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Analyzer/VRPSolution.cs

    r4752 r5127  
    106106    private VRPSolution(VRPSolution original, Cloner cloner)
    107107      : base(original, cloner) {
    108       this.problemInstance = (IVRPProblemInstance)cloner.Clone(original.problemInstance);
     108      this.problemInstance = original.problemInstance;
    109109      this.solution = (IVRPEncoding)cloner.Clone(original.solution);
    110110      this.quality = (DoubleValue)cloner.Clone(original.quality);
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Moves/VRPMoveEvaluator.cs

    r4752 r5127  
    4444      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    4545    }
     46    public ILookupParameter<DoubleValue> MovePenaltyParameter {
     47      get { return (ILookupParameter<DoubleValue>)Parameters["MovePenalty"]; }
     48    }
    4649
    4750    [StorableConstructor]
     
    5255      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the solution."));
    5356      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The relative quality of the move."));
     57      Parameters.Add(new LookupParameter<DoubleValue>("MovePenalty", "The penalty applied to the move."));
    5458    }
    5559
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/Moves/VRPMoveMaker.cs

    r4752 r5127  
    4242      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    4343    }
     44    public ILookupParameter<DoubleValue> MovePenaltyParameter {
     45      get { return (ILookupParameter<DoubleValue>)Parameters["MovePenalty"]; }
     46    }
    4447
    4548    [StorableConstructor]
     
    5053      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the solution."));
    5154      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The relative quality of the move."));
     55      Parameters.Add(new LookupParameter<DoubleValue>("MovePenalty", "The penalty applied to the move."));
    5256    }
    5357
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs

    r4899 r5127  
    3939    #region IVRPEncoding Members
    4040    public virtual List<Tour> GetTours() {
    41       List<Tour> result = new List<Tour>(Tours);
     41      List<Tour> result = new List<Tour>();
     42
     43      foreach(Tour tour in Tours) {
     44        if (tour.Stops.Count > 0)
     45          result.Add(tour);
     46      }
    4247
    4348     while (result.Count > ProblemInstance.Vehicles.Value) {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

    r4752 r5127  
    3939    public List<int> Unrouted { get; set; }
    4040
     41    [Storable]
     42    public double PenaltyFactor { get; set; }
     43
    4144    public PotvinEncoding(IVRPProblemInstance instance)
    4245      : base(instance) {
    4346      Unrouted = new List<int>();
     47      PenaltyFactor = 1;
    4448    }
    4549
     
    5660      : base(original, cloner) {
    5761        this.Unrouted = new List<int>(original.Unrouted);
     62        this.PenaltyFactor = original.PenaltyFactor;
    5863    }
    5964
     
    7277
    7378      return solution;
     79    }
     80
     81    public double EvaluateTour(Tour tour) {
     82      return ProblemInstance.Evaluate(tour);
    7483    }
    7584
     
    91100
    92101      return length;
     102    }
     103
     104    public int FindBestInsertionPlace(Tour tour, int city) {
     105      int place = -1;
     106      double minQuality = -1;
     107
     108      for (int i = 0; i <= tour.Stops.Count; i++) {
     109        tour.Stops.Insert(i, city);
     110
     111        double quality = EvaluateTour(tour);
     112
     113        if (place < 0 || quality < minQuality) {
     114          place = i;
     115          minQuality = quality;
     116        }
     117
     118        tour.Stops.RemoveAt(i);
     119      }
     120
     121      if (place == -1)
     122        place = 0;
     123
     124      return place;
    93125    }
    94126
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r4860 r5127  
    189189    <Compile Include="Encodings\GVR\Manipulators\GVRManipulator.cs" />
    190190    <Compile Include="Encodings\GVR\Manipulators\GVRSwapManipulator.cs" />
     191    <Compile Include="Encodings\Potvin\Creators\PotvinCreator.cs" />
     192    <Compile Include="Encodings\Potvin\Creators\IterativeInsertionCreator.cs" />
    191193    <Compile Include="Encodings\Potvin\Crossovers\PotvinCrossover.cs" />
    192194    <Compile Include="Encodings\Potvin\Crossovers\PotvinRouteBasedCrossover.cs" />
     
    197199    <Compile Include="Encodings\Potvin\Manipulators\PotvinOneLevelExchangeManipulator.cs" />
    198200    <Compile Include="Encodings\Potvin\Manipulators\PotvinTwoLevelExchangeManipulator.cs" />
     201    <Compile Include="Encodings\General\Moves\VRPMoveAttribute.cs" />
     202    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMoveTabuMaker.cs" />
     203    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationSingleMoveGenerator.cs" />
     204    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMultiMoveGenerator.cs" />
     205    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationExhaustiveMoveGenerator.cs" />
     206    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMoveEvaluator.cs" />
     207    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMoveMaker.cs" />
     208    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\IPotvinCustomerRelocationMoveOperator.cs" />
     209    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMoveAttribute.cs" />
     210    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMoveTabuCriterion.cs" />
     211    <Compile Include="Encodings\Potvin\Moves\PotvinMoveEvaluator.cs" />
     212    <Compile Include="Encodings\Potvin\Moves\PotvinMoveGenerator.cs" />
     213    <Compile Include="Encodings\Potvin\Moves\PotvinMoveMaker.cs" />
     214    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMoveGenerator.cs" />
     215    <Compile Include="Encodings\Potvin\Moves\CustomerRelocation\PotvinCustomerRelocationMove.cs" />
    199216    <Compile Include="Encodings\Potvin\PotvinEncoding.cs" />
    200217    <Compile Include="Encodings\Prins\Crossovers\PrinsCrossover.cs" />
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPProblemInstance.cs

    r4860 r5127  
    7676    public CVRPProblemInstance() {
    7777      Parameters.Add(new ValueParameter<DoubleValue>("Capacity", "The capacity of each vehicle.", new DoubleValue(0)));
    78       Parameters.Add(new ValueParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation.", new DoubleValue(100)));
     78      Parameters.Add(new ValueParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation.", new DoubleValue(1)));
    7979
    8080      AttachEventHandlers();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWProblemInstance.cs

    r4860 r5127  
    102102
    103103      Parameters.Add(new ValueParameter<DoubleValue>("EvalTimeFactor", "The time factor considered in the evaluation.", new DoubleValue(0)));
    104       Parameters.Add(new ValueParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation.", new DoubleValue(100)));
     104      Parameters.Add(new ValueParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation.", new DoubleValue(1)));
    105105
    106106      AttachEventHandlers();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPEvaluator.cs

    r4752 r5127  
    5555      get { return (ILookupParameter<DoubleValue>)Parameters["VehiclesUtilized"]; }
    5656    }
     57
     58    public ILookupParameter<DoubleValue> PenaltyParameter {
     59      get { return (ILookupParameter<DoubleValue>)Parameters["Penalty"]; }
     60    }
    5761   
    5862    [StorableConstructor]
     
    6569      Parameters.Add(new LookupParameter<DoubleValue>("Distance", "The distance."));
    6670      Parameters.Add(new LookupParameter<DoubleValue>("VehiclesUtilized", "The number of vehicles utilized."));
     71
     72      Parameters.Add(new LookupParameter<DoubleValue>("Penalty", "The applied penalty."));
    6773    }
    6874
     
    8187      VehcilesUtilizedParameter.ActualValue = new DoubleValue(0);
    8288      DistanceParameter.ActualValue = new DoubleValue(0);
     89      PenaltyParameter.ActualValue = new DoubleValue(0);
    8390    }
    8491
     
    8794      VehcilesUtilizedParameter.ActualValue.Value = tourEvaluation.VehicleUtilization;
    8895      DistanceParameter.ActualValue.Value = tourEvaluation.Distance;
     96      PenaltyParameter.ActualValue.Value = tourEvaluation.Penalty;
    8997    }
    9098
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs

    r4895 r5127  
    221221      Parameters.Add(new ValueParameter<DoubleArray>("Demand", "The demand of each customer.", new DoubleArray()));
    222222
    223       Parameters.Add(new ValueParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(100)));
     223      Parameters.Add(new ValueParameter<DoubleValue>("EvalFleetUsageFactor", "The fleet usage factor considered in the evaluation.", new DoubleValue(0)));
    224224      Parameters.Add(new ValueParameter<DoubleValue>("EvalDistanceFactor", "The distance factor considered in the evaluation.", new DoubleValue(1)));
    225225
Note: See TracChangeset for help on using the changeset viewer.