Changeset 6710


Ignore:
Timestamp:
09/06/11 13:00:12 (8 years ago)
Author:
svonolfe
Message:

Added support for pickups and deliveries (#1177)

Location:
branches/VRP
Files:
16 added
3 deleted
15 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/HeuristicLab.Problems.VehicleRouting.Views-3.4.csproj

    r6607 r6710  
    112112  </ItemGroup>
    113113  <ItemGroup>
     114    <Compile Include="CVRPPDTWView.cs">
     115      <SubType>UserControl</SubType>
     116    </Compile>
     117    <Compile Include="CVRPPDTWView.Designer.cs">
     118      <DependentUpon>CVRPPDTWView.cs</DependentUpon>
     119    </Compile>
    114120    <Compile Include="CVRPTWView.cs">
    115121      <SubType>UserControl</SubType>
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/VRPImportDialog.Designer.cs

    r5867 r6710  
    8585      this.openVRPFileDialog.DefaultExt = "vrp";
    8686      this.openVRPFileDialog.FileName = "vrp";
    87       this.openVRPFileDialog.Filter = "TSPLib Format|*.vrp|Solomon Format|*.txt|ORLib Format|*.txt";
     87      this.openVRPFileDialog.Filter = "TSPLib Format|*.vrp|Solomon Format|*.txt|ORLib Format|*.txt|LiLim Format|*.txt";
    8888      this.openVRPFileDialog.Title = "Open TSP File";
    8989      //
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/VRPImportDialog.cs

    r4860 r6710  
    2727
    2828namespace HeuristicLab.Problems.VehicleRouting.Views {
    29   public enum VRPFormat { Empty, TSPLib, Solomon, ORLib }
     29  public enum VRPFormat { Empty, TSPLib, Solomon, ORLib, LiLim }
    3030
    3131  public sealed partial class VRPImportDialog : Form {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting.Views/3.4/VehicleRoutingProblemView.cs

    r4860 r6710  
    8282              Content.ImportFromORLib(vrpImportDialog.VRPFileName);
    8383              break;
     84
     85            case VRPFormat.LiLim:
     86              Content.ImportFromLiLim(vrpImportDialog.VRPFileName);
     87              break;
    8488          }
    8589
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Analyzer/BestSolution/Capacitated/BestCapacitatedVRPSolutionAnalyzer.cs

    r4752 r6710  
    7070        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Overload", "The overloads of the VRP solutions which should be analyzed."));
    7171
    72         Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best TSP solution."));
     72        Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best VRP solution."));
    7373        Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best VRP solution should be stored."));
    7474    }
     
    9191      int i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
    9292
    93       IVRPEncoding best = solutions[i] as IVRPEncoding;
    9493      VRPSolution solution = BestSolutionParameter.ActualValue;
    95       if (!results.ContainsKey("Best VRP Solution Overload")) {
    96         results.Add(new Result("Best VRP Solution Overload", new DoubleValue(overloads[i].Value)));
    97       } else {
    98         if (qualities[i].Value <= solution.Quality.Value) {
    99           (results["Best VRP Solution Overload"].Value as DoubleValue).Value = overloads[i].Value;
     94      if (solution != null) {
     95        if (!results.ContainsKey("Best VRP Solution Overload")) {
     96          results.Add(new Result("Best VRP Solution Overload", new DoubleValue(overloads[i].Value)));
     97        } else {
     98          if (qualities[i].Value <= solution.Quality.Value) {
     99            (results["Best VRP Solution Overload"].Value as DoubleValue).Value = overloads[i].Value;
     100          }
    100101        }
    101102      }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Analyzer/BestSolution/TimeWindowed/BestTimeWindowedVRPSolutionAnalyzer.cs

    r4752 r6710  
    7373        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Tardiness", "The tardiness of the VRP solutions which should be analyzed."));
    7474        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("TravelTime", "The travel times of the VRP solutions which should be analyzed."));
    75  
    76         Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best TSP solution."));
     75
     76        Parameters.Add(new LookupParameter<VRPSolution>("BestSolution", "The best VRP solution."));
    7777        Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best VRP solution should be stored."));
    7878    }
     
    9696      int i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
    9797
    98       IVRPEncoding best = solutions[i] as IVRPEncoding;
    9998      VRPSolution solution = BestSolutionParameter.ActualValue;
    100       if (!results.ContainsKey("Best VRP Solution Tardiness")) {
    101         results.Add(new Result("Best VRP Solution Tardiness", new DoubleValue(tardinesses[i].Value)));
    102         results.Add(new Result("Best VRP Solution TravelTime", new DoubleValue(travelTimes[i].Value)));
    103       } else {
    104         if (qualities[i].Value <= solution.Quality.Value) {
    105           (results["Best VRP Solution Tardiness"].Value as DoubleValue).Value = tardinesses[i].Value;
    106           (results["Best VRP Solution TravelTime"].Value as DoubleValue).Value = travelTimes[i].Value;
     99      if (solution != null) {
     100        if (!results.ContainsKey("Best VRP Solution Tardiness")) {
     101          results.Add(new Result("Best VRP Solution Tardiness", new DoubleValue(tardinesses[i].Value)));
     102          results.Add(new Result("Best VRP Solution TravelTime", new DoubleValue(travelTimes[i].Value)));
     103        } else {
     104          if (qualities[i].Value <= solution.Quality.Value) {
     105            (results["Best VRP Solution Tardiness"].Value as DoubleValue).Value = tardinesses[i].Value;
     106            (results["Best VRP Solution TravelTime"].Value as DoubleValue).Value = travelTimes[i].Value;
     107          }
    107108        }
    108109      }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs

    r5201 r6710  
    3333  [Item("AlbaEncoding", "Represents an Alba encoding of VRP solutions. It is implemented as described in Alba, E. and Dorronsoro, B. (2004). Solving the Vehicle Routing Problem by Using Cellular Genetic Algorithms.")]
    3434  [StorableClass]
    35   public class AlbaEncoding : PermutationEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHeterogenousCapacitatedEncoding  {   
     35  public class AlbaEncoding : PermutationEncoding, IHeterogenousCapacitatedEncoding  {   
    3636    #region IVRPEncoding Members
    3737    public override List<Tour> GetTours() {
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs

    r6608 r6710  
    2727using System;
    2828using HeuristicLab.Parameters;
     29using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
    2930
    3031namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
     
    151152      int city, bool allowInfeasible, out int place) {
    152153      place = -1;
     154
     155      if (tour.Stops.Contains(city))
     156        return false;
     157
    153158      bool bestFeasible = false;
    154159      double minDetour = 0;
    155160
     161      VRPEvaluation eval = ProblemInstance.Evaluate(tour);
     162      double length = eval.Quality;
    156163      for (int i = 0; i <= tour.Stops.Count; i++) {
    157         double length = tour.GetTourLength(ProblemInstance);
    158 
    159164        tour.Stops.Insert(i, city);
    160165
    161         bool feasible = ProblemInstance.Feasible(tour);
     166        eval = ProblemInstance.Evaluate(tour);
     167        bool feasible = ProblemInstance.Feasible(eval);
    162168
    163169        if (feasible || allowInfeasible && !bestFeasible) {
    164           double newLength = tour.GetTourLength(ProblemInstance);
     170          double newLength = eval.Quality;
    165171          double detour = newLength - length;
    166172
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/PotvinEncoding.cs

    r6607 r6710  
    3535  [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.")]
    3636  [StorableClass]
    37   public class PotvinEncoding : TourEncoding, ISingleDepotEncoding, ITimeWindowedEncoding, IHomogenousCapacitatedEncoding {   
     37  public class PotvinEncoding : TourEncoding {   
    3838    [Storable]
    3939    public List<int> Unrouted { get; set; }
     
    115115      for (int tour = 0; tour < Tours.Count; tour++) {
    116116        if (tour != routeToAvoid) {
     117          VRPEvaluation eval = ProblemInstance.Evaluate(Tours[tour]);
     118          double length = eval.Quality;
     119
    117120          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
    118             double length = GetTourLength(Tours[tour]);
    119 
    120121            Tours[tour].Stops.Insert(i, city);
    121122
    122             bool feasible = ProblemInstance.Feasible(Tours[tour]);
     123            eval = ProblemInstance.Evaluate(Tours[tour]);
     124            bool feasible = ProblemInstance.Feasible(eval);
    123125
    124126            if (feasible || allowInfeasible && !bestFeasible) {
    125               double newLength = GetTourLength(Tours[tour]);
     127              double newLength = eval.Quality;
    126128              double detour = newLength - length;
    127129
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/PrinsEncoding.cs

    r6607 r6710  
    6666          feasible = ProblemInstance.Feasible(eval);
    6767
    68           if (feasible) {
     68          if (feasible || j == i) {
    6969            if (V[i - 1] + cost < V[j]) {
    7070              V[j] = V[i - 1] + cost;
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r6607 r6710  
    113113    <Compile Include="Analyzer\BestAverageWorstTours\Capacitated\BestAverageWorstCapacitatedVRPToursCalculator.cs" />
    114114    <Compile Include="Analyzer\BestAverageWorstTours\Capacitated\BestCapacitatedVRPToursMemorizer.cs" />
     115    <Compile Include="Analyzer\BestAverageWorstTours\PickupAndDelivery\BestAverageWorstPickupAndDeliveryVRPToursAnalyzer.cs" />
     116    <Compile Include="Analyzer\BestAverageWorstTours\PickupAndDelivery\BestAverageWorstPickupAndDeliveryVRPToursCalculator.cs" />
     117    <Compile Include="Analyzer\BestAverageWorstTours\PickupAndDelivery\BestPickupAndDeliveryVRPToursMemorizer.cs" />
    115118    <Compile Include="Analyzer\BestAverageWorstTours\TimeWindowed\BestAverageWorstTimeWindowedVRPToursAnalyzer.cs" />
    116119    <Compile Include="Analyzer\BestAverageWorstTours\TimeWindowed\BestAverageWorstTimeWindowedVRPToursCalculator.cs" />
     
    118121    <Compile Include="Analyzer\BestSolution\BestVRPSolutionAnalyzer.cs" />
    119122    <Compile Include="Analyzer\BestSolution\Capacitated\BestCapacitatedVRPSolutionAnalyzer.cs" />
     123    <Compile Include="Analyzer\BestSolution\PickupAndDelivery\BestPickupAndDeliveryVRPSolutionAnalyzer.cs" />
    120124    <Compile Include="Analyzer\BestSolution\TimeWindowed\BestTimeWindowedVRPSolutionAnalyzer.cs" />
    121125    <Compile Include="Analyzer\VRPSolution.cs" />
     
    249253    <Compile Include="Interfaces\IVRPEncoding.cs" />
    250254    <Compile Include="Interfaces\IVRPProblemInstance.cs" />
     255    <Compile Include="Parsers\LiLimParser.cs" />
     256    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPPDTW\CVRPPDTWProblemInstance.cs" />
     257    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPPDTW\CVRPPDTWEvaluation.cs" />
     258    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPPDTW\CVRPPDTWEvaluator.cs" />
    251259    <Compile Include="SolutionParser.cs" />
    252260    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedProblemInstance.cs" />
    253261    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedOperator.cs" />
    254262    <Compile Include="Variants\Capacitated\Heterogenous\IHeterogenousCapacitatedEncoding.cs" />
    255     <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedEncoding.cs" />
    256263    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedOperator.cs" />
    257264    <Compile Include="Variants\Capacitated\Homogenous\IHomogenousCapacitatedProblemInstance.cs" />
     
    259266    <Compile Include="Variants\Capacitated\ICapacitatedOperator.cs" />
    260267    <Compile Include="Variants\General\IGeneralVRPOperator.cs" />
     268    <Compile Include="Variants\PickupAndDelivery\IPickupAndDeliveryOperator.cs" />
     269    <Compile Include="Variants\PickupAndDelivery\IPickupAndDeliveryProblemInstance.cs" />
    261270    <Compile Include="Variants\SingleDepot\ISingleDepotOperator.cs" />
    262     <Compile Include="Variants\SingleDepot\ISingleDepotEncoding.cs" />
    263271    <Compile Include="Variants\SingleDepot\ISingleDepotProblemInstance.cs" />
    264272    <Compile Include="Variants\TimeWindowed\ITimeWindowedProblemInstance.cs" />
    265273    <Compile Include="Variants\TimeWindowed\ITimeWindowedOperator.cs" />
    266     <Compile Include="Variants\TimeWindowed\ITimeWindowedEncoding.cs" />
    267274    <Compile Include="Parsers\ORLIBParser.cs" />
    268275    <Compile Include="ProblemInstances\SingleDepotVRP\CVRP\CVRPTW\CVRPTWProblemInstance.cs" />
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPProblemInstance.cs

    r5127 r6710  
    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(1)));
     78      Parameters.Add(new ValueParameter<DoubleValue>("EvalOverloadPenalty", "The overload penalty considered in the evaluation.", new DoubleValue(100)));
    7979
    8080      AttachEventHandlers();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWProblemInstance.cs

    r5127 r6710  
    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(1)));
     104      Parameters.Add(new ValueParameter<DoubleValue>("EvalTardinessPenalty", "The tardiness penalty considered in the evaluation.", new DoubleValue(100)));
    105105
    106106      AttachEventHandlers();
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Variants/Capacitated/Heterogenous/IHeterogenousCapacitatedEncoding.cs

    r4376 r6710  
    2424using System.Linq;
    2525using System.Text;
     26using HeuristicLab.Problems.VehicleRouting.Interfaces;
    2627
    2728namespace HeuristicLab.Problems.VehicleRouting.Variants {
    28   public interface IHeterogenousCapacitatedEncoding : IHomogenousCapacitatedEncoding {
     29  public interface IHeterogenousCapacitatedEncoding : IVRPEncoding {
    2930    int GetVehicleAssignment(int tour);
    3031  }
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs

    r5867 r6710  
    243243    #endregion
    244244
     245    public void ImportFromLiLim(string liLimFileName) {
     246      LiLimParser parser = new LiLimParser(liLimFileName);
     247      parser.Parse();
     248     
     249      CVRPPDTWProblemInstance problem = new CVRPPDTWProblemInstance();
     250
     251      problem.Coordinates = new DoubleMatrix(parser.Coordinates);
     252      problem.Vehicles.Value = parser.Vehicles;
     253      problem.Capacity.Value = parser.Capacity;
     254      problem.Demand = new DoubleArray(parser.Demands);
     255      problem.ReadyTime = new DoubleArray(parser.Readytimes);
     256      problem.DueTime = new DoubleArray(parser.Duetimes);
     257      problem.ServiceTime = new DoubleArray(parser.Servicetimes);
     258      problem.PickupDeliveryLocation = new IntArray(parser.PickupDeliveryLocations);
     259
     260      this.ProblemInstance = problem;
     261
     262      OnReset();
     263    }
     264
    245265    public void ImportFromSolomon(string solomonFileName) {
    246266      SolomonParser parser = new SolomonParser(solomonFileName);
Note: See TracChangeset for help on using the changeset viewer.