Free cookie consent management tool by TermsFeed Policy Generator

Changeset 6854


Ignore:
Timestamp:
09/30/11 11:36:05 (13 years ago)
Author:
svonolfe
Message:

Added support for the multi depot CVRP with time windows (#1177)

Location:
branches/VRP
Files:
5 added
11 edited

Legend:

Unmodified
Added
Removed

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

    r6851 r6854  
    112112  </ItemGroup>
    113113  <ItemGroup>
     114    <Compile Include="MDCVRPTWView.cs">
     115      <SubType>UserControl</SubType>
     116    </Compile>
     117    <Compile Include="MDCVRPTWView.Designer.cs">
     118      <DependentUpon>MDCVRPTWView.cs</DependentUpon>
     119    </Compile>
    114120    <Compile Include="MultiDepotVRPView.cs">
    115121      <SubType>UserControl</SubType>

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/ExtendedPotvin/Creators/PushForwardInsertionCreator.cs

    r6851 r6854  
    182182            double dueTime = 0;
    183183            if (problemInstance is ITimeWindowedProblemInstance)
    184               dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i];
     184              dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i + depots - 1];
    185185
    186186            cost = -alpha * distance + // distance 0 <-> City[i]

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinCustomerRelocationManipulator.cs

    r6851 r6854  
    146146          DoubleArray serviceTimes = vrptw.ServiceTime;
    147147
     148          int depot = 0;
     149          int depots = 1;
     150
     151          int tourIndex = individual.GetTourIndex(route1);
     152          int vehicle = individual.GetVehicleAssignment(tourIndex);
     153
     154          if (ProblemInstance is IMultiDepotProblemInstance) {
     155            depots = (ProblemInstance as IMultiDepotProblemInstance).Depots.Value;
     156            depot = (ProblemInstance as IMultiDepotProblemInstance).VehicleDepotAssignment[vehicle];
     157          }
     158
    148159          List<int> timeWindowViolations = new List<int>();
    149160          double time = 0;
    150161
    151162          for (int i = 0; i < route1.Stops.Count; i++) {
    152             int start = 0;
    153             if (i > 0)
    154               start = route1.Stops[i - 1];
    155             int end = 0;
    156             if (i < route1.Stops.Count)
    157               end = route1.Stops[i];
     163            int start = route1.Stops[i - 1];
     164            int end = route1.Stops[i];
    158165
    159166            //drive there
    … …  
    161168            time += currentDistace;
    162169
     170            int endIndex = end + depots - 1;
     171
    163172            //check if it was serviced on time
    164             if (time > dueTime[end]) {
     173            if (time > dueTime[endIndex]) {
    165174              timeWindowViolations.Add(end);
    166175            }
    … …  
    168177            //wait
    169178            double currentWaitingTime = 0.0;
    170             if (time < readyTime[end])
    171               currentWaitingTime = readyTime[end] - time;
     179            if (time < readyTime[endIndex])
     180              currentWaitingTime = readyTime[endIndex] - time;
    172181            time += currentWaitingTime;
    173182
    174183            //service
    175             double currentServiceTime = serviceTimes[end];
     184            double currentServiceTime = serviceTimes[end - 1];
    176185            time += currentServiceTime;
    177186          }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/HeuristicLab.Problems.VehicleRouting-3.4.csproj

    r6851 r6854  
    301301    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPEvaluator.cs" />
    302302    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPProblemInstance.cs" />
     303    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPTW\MDCVRPTWEvaluator.cs" />
     304    <Compile Include="ProblemInstances\MultiDepotVRP\MDCVRP\MDCVRPTW\MDCVRPTWProblemInstance.cs" />
    303305    <Compile Include="ProblemInstances\MultiDepotVRP\MultiDepotVRPProblemInstance.cs" />
    304306    <Compile Include="ProblemInstances\MultiDepotVRP\MultiDepotVRPEvaluator.cs" />

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Interfaces/IVRPProblemInstance.cs

    r6851 r6854  
    5151    double GetDemand(int city);
    5252    double GetDistance(int start, int end, IVRPEncoding solution);
    53     double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution);
     53    double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution, out double startDistance, out double endDistance);
    5454    bool Feasible(IVRPEncoding solution);
    5555    bool TourFeasible(Tour tour, IVRPEncoding solution);

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Parsers/CordeauParser.cs

    r6851 r6854  
    132132        throw new InvalidDataException("File has wrong format!");
    133133
     134      bool timeWindows = int.Parse(m[0].Value) == 6;
    134135      vehicles = int.Parse(m[3].Value);
    135136      line = reader.ReadLine();
    … …  
    146147      List<double> depotXcoord = new List<double>();
    147148      List<double> depotYcoord = new List<double>();
     149      List<double> depotReadyTime = new List<double>();
     150      List<double> depotDueTime = new List<double>();
     151
    148152      while ((line != null)) {
    149153        m = reg.Matches(line);
    150154
    151         if (m.Count == 11) {
     155        if (m.Count >= 11) {
    152156          xCoord.Add(double.Parse(m[1].Value, System.Globalization.CultureInfo.InvariantCulture));
    153157          yCoord.Add(double.Parse(m[2].Value, System.Globalization.CultureInfo.InvariantCulture));
    154158          demand.Add((double)int.Parse(m[4].Value, System.Globalization.CultureInfo.InvariantCulture));
    155         } else if (m.Count == 7) {
     159
     160          if (timeWindows) {
     161            serviceTime.Add(int.Parse(m[3].Value));
     162            readyTime.Add(int.Parse(m[m.Count - 2].Value));
     163            dueTime.Add(int.Parse(m[m.Count - 1].Value));
     164          } else {
     165            serviceTime.Add(0);
     166            readyTime.Add(0);
     167            dueTime.Add(double.MaxValue);
     168          }
     169        } else if (m.Count >= 7) {
    156170          depotXcoord.Add(double.Parse(m[1].Value, System.Globalization.CultureInfo.InvariantCulture));
    157171          depotYcoord.Add(double.Parse(m[2].Value, System.Globalization.CultureInfo.InvariantCulture));
     172
     173          if (timeWindows) {
     174            depotReadyTime.Add(int.Parse(m[m.Count - 2].Value));
     175            depotDueTime.Add(int.Parse(m[m.Count - 1].Value));
     176          } else {
     177            depotReadyTime.Add(0);
     178            depotDueTime.Add(double.MaxValue);
     179          }
    158180        }
    159181               
    … …  
    163185      xCoord.InsertRange(0, depotXcoord);
    164186      yCoord.InsertRange(0, depotYcoord);
     187      readyTime.InsertRange(0, depotReadyTime);
     188      dueTime.InsertRange(0, depotDueTime);
    165189
    166190      cities = demand.Count;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MDCVRP/MDCVRPEvaluator.cs

    r6851 r6854  
    111111      double overloadPenalty = cvrp.OverloadPenalty.Value;
    112112
    113       costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution);
     113      double startDistance, endDistance;
     114      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution, out startDistance, out endDistance);
    114115
    115116      double demand = instance.GetDemand(customer);

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MultiDepotVRPEvaluator.cs

    r6851 r6854  
    8181      double costs = 0;
    8282      feasible = true;
     83      double startDistance, endDistance;
    8384
    84       costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution);
     85      costs += instance.GetInsertionDistance(insertionInfo.Start, customer, insertionInfo.End, solution, out startDistance, out endDistance);
    8586
    8687      return costs;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/MultiDepotVRP/MultiDepotVRPProblemInstance.cs

    r6851 r6854  
    150150    }
    151151
    152     public override double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution) {
     152    public override double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution,
     153      out double startDistance, out double endDistance) {
    153154      if (start == 0) {
    154155        start = GetDepot(end, solution);
    … …  
    164165     
    165166      double distance = base.GetDistance(start, end, solution);
    166       double newDistance =
    167         base.GetDistance(start, customer, solution) +
    168         base.GetDistance(customer, end, solution);
     167
     168      startDistance = base.GetDistance(start, customer, solution);
     169      endDistance = base.GetDistance(customer, end, solution);
     170
     171      double newDistance = startDistance + endDistance;
    169172
    170173      return newDistance - distance;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/VRPProblemInstance.cs

    r6851 r6854  
    220220    }
    221221
    222     public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution) {
     222    public virtual double GetInsertionDistance(int start, int customer, int end, IVRPEncoding solution,
     223      out double startDistance, out double endDistance) {
    223224      double distance = GetDistance(start, end, solution);
    224       double newDistance =
    225         GetDistance(start, customer, solution) +
    226         GetDistance(customer, end, solution);
     225
     226      startDistance = GetDistance(start, customer, solution);
     227      endDistance = GetDistance(customer, end, solution);
     228     
     229      double newDistance = startDistance + endDistance;
    227230
    228231      return newDistance - distance;

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/VehicleRoutingProblem.cs

    r6851 r6854  
    247247      parser.Parse();
    248248
    249       MDCVRPProblemInstance problem = new MDCVRPProblemInstance();
     249      MDCVRPTWProblemInstance problem = new MDCVRPTWProblemInstance();
    250250
    251251      problem.Coordinates = new DoubleMatrix(parser.Coordinates);
    … …  
    255255      problem.Depots.Value = parser.Depots;
    256256      problem.VehicleDepotAssignment = new IntArray(parser.Vehicles);
     257      problem.ReadyTime = new DoubleArray(parser.Readytimes);
     258      problem.ServiceTime = new DoubleArray(parser.Servicetimes);
     259      problem.DueTime = new DoubleArray(parser.Duetimes);
     260
    257261      int depot = 0;
    258262      int i = 0;
Note: See TracChangeset for help on using the changeset viewer.