Free cookie consent management tool by TermsFeed Policy Generator

Changeset 6752 for branches/VRP


Ignore:
Timestamp:
09/13/11 16:00:19 (13 years ago)
Author:
svonolfe
Message:

Added support for incremental evaluation to improve performance (#1177)

Location:
branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/TourEncoding.cs

    r6713 r6752  
    3838   
    3939    #region IVRPEncoding Members
    40     public virtual List<Tour> GetTours() {
    41       List<Tour> result = new List<Tour>();
    42 
    43       foreach(Tour tour in Tours) {
    44         if (tour.Stops.Count > 0)
    45           result.Add(tour.Clone() as Tour);
     40    public void Repair() {
     41      List<Tour> toBeRemoved = new List<Tour>();
     42      foreach (Tour tour in Tours) {
     43        if (tour.Stops.Count == 0)
     44          toBeRemoved.Add(tour);
    4645      }
    4746
    48      while (result.Count > ProblemInstance.Vehicles.Value) {
    49         Tour tour = result[result.Count - 1];
    50         result[result.Count - 2].Stops.AddRange(tour.Stops);
     47      foreach (Tour tour in toBeRemoved)
     48        Tours.Remove(tour);
    5149
    52         result.Remove(tour);
    53       }   
     50      while (Tours.Count > ProblemInstance.Vehicles.Value) {
     51        Tour tour = Tours[Tours.Count - 1];
     52        Tours[Tours.Count - 2].Stops.AddRange(tour.Stops);
    5453
    55       return result;
     54        Tours.Remove(tour);
     55      }
     56    }
     57
     58    public virtual List<Tour> GetTours() {
     59     Repair();
     60     
     61     List<Tour> result = new List<Tour>();
     62     foreach (Tour tour in Tours)
     63       result.Add(tour.Clone() as Tour);
     64
     65     return result;
    5666    }
    5767

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinInsertionBasedCrossover.cs

    r6710 r6752  
    156156        return false;
    157157
    158       bool bestFeasible = false;
     158      if (tour.Stops.Count == 0) {
     159        place = 0;
     160        return true;
     161      }
     162
    159163      double minDetour = 0;
    160 
    161164      VRPEvaluation eval = ProblemInstance.Evaluate(tour);
    162       double length = eval.Quality;
     165      bool originalFeasible = ProblemInstance.Feasible(eval);
     166
    163167      for (int i = 0; i <= tour.Stops.Count; i++) {
    164         tour.Stops.Insert(i, city);
    165 
    166         eval = ProblemInstance.Evaluate(tour);
    167         bool feasible = ProblemInstance.Feasible(eval);
    168 
    169         if (feasible || allowInfeasible && !bestFeasible) {
    170           double newLength = eval.Quality;
    171           double detour = newLength - length;
    172 
    173           if (place < 0 || detour < minDetour || feasible && !bestFeasible) {
     168        bool feasible;
     169        double detour = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
     170        if (feasible || allowInfeasible) {
     171          if (place < 0 || detour < minDetour) {
    174172            place = i;
    175173            minDetour = detour;
    176 
    177             if (feasible)
    178               bestFeasible = true;
    179174          }
    180175        }
    181 
    182         tour.Stops.RemoveAt(i);
    183176      }
    184177
    … …  
    248241
    249242          int place = -1;
    250           if (FindRouteInsertionPlace(childTour, city, allowInfeasible, out place)) {
     243          bool found = FindRouteInsertionPlace(childTour, city, allowInfeasible, out place);
     244          if (found) {
    251245            childTour.Stops.Insert(place, city);
    252246

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

    r6710 r6752  
    3939    public List<int> Unrouted { get; set; }
    4040
    41     [Storable]
    42     public double PenaltyFactor { get; set; }
    43 
    4441    public PotvinEncoding(IVRPProblemInstance instance)
    4542      : base(instance) {
    4643      Unrouted = new List<int>();
    47       PenaltyFactor = 1;
    4844    }
    4945
    … …  
    6056      : base(original, cloner) {
    6157        this.Unrouted = new List<int>(original.Unrouted);
    62         this.PenaltyFactor = original.PenaltyFactor;
    6358    }
    6459
    … …  
    8782      double minQuality = -1;
    8883
     84      VRPEvaluation eval = ProblemInstance.Evaluate(tour);
     85
    8986      for (int i = 0; i <= tour.Stops.Count; i++) {
    90         tour.Stops.Insert(i, city);
    91 
    92         VRPEvaluation eval = ProblemInstance.Evaluate(tour);
    93         double quality = eval.Quality + eval.Penalty * (PenaltyFactor - 1.0);
    94 
     87        bool feasible;
     88        double quality = ProblemInstance.GetInsertionCosts(eval, city, 0, i, out feasible);
    9589        if (place < 0 || quality < minQuality) {
    9690          place = i;
    9791          minQuality = quality;
    9892        }
    99 
    100         tour.Stops.RemoveAt(i);
    10193      }
    10294
    … …  
    110102      route = -1;
    111103      place = -1;
    112       bool bestFeasible = false;
    113104      double minDetour = double.MaxValue;
     105
     106      VRPEvaluation eval = ProblemInstance.Evaluate(this);
     107      bool originalFeasible = ProblemInstance.Feasible(eval);
    114108
    115109      for (int tour = 0; tour < Tours.Count; tour++) {
    116110        if (tour != routeToAvoid) {
    117           VRPEvaluation eval = ProblemInstance.Evaluate(Tours[tour]);
    118111          double length = eval.Quality;
    119112
    120113          for (int i = 0; i <= Tours[tour].Stops.Count; i++) {
    121             Tours[tour].Stops.Insert(i, city);
    122 
    123             eval = ProblemInstance.Evaluate(Tours[tour]);
    124             bool feasible = ProblemInstance.Feasible(eval);
    125 
    126             if (feasible || allowInfeasible && !bestFeasible) {
    127               double newLength = eval.Quality;
    128               double detour = newLength - length;
    129 
    130               if (route < 0 || detour < minDetour || feasible && !bestFeasible) {
     114            bool feasible;
     115            double detour = ProblemInstance.GetInsertionCosts(eval, city, tour, i, out feasible);
     116           
     117            if (feasible || allowInfeasible) {
     118              if (route < 0 || detour < minDetour) {
    131119                route = tour;
    132120                place = i;
    133121                minDetour = detour;
    134 
    135                 if (feasible)
    136                   bestFeasible = true;
    137122              }
    138123            }
    139 
    140             Tours[tour].Stops.RemoveAt(i);
    141124          }
    142125        }

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

    r4378 r6752  
    3535    VRPEvaluation Evaluate(IVRPProblemInstance instance, Tour tour);
    3636    bool Feasible(VRPEvaluation evaluation);
     37    double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
    3738  }
    3839}

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

    r6607 r6752  
    5454    VRPEvaluation Evaluate(Tour tour);
    5555    bool Feasible(VRPEvaluation eval);
     56    double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible);
    5657  }
    5758}

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluation.cs

    r4454 r6752  
    2424using System.Linq;
    2525using System.Text;
     26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using HeuristicLab.Core;
     28using HeuristicLab.Common;
    2629
    2730namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
     31  public class CVRPInsertionInfo : StopInsertionInfo {
     32    private double spareCapacity;
     33
     34    public double SpareCapacity {
     35      get { return spareCapacity; }
     36    }
     37
     38    public CVRPInsertionInfo(int start, int end, double spareCapacity)
     39      : base(start, end) {
     40      this.spareCapacity = spareCapacity;
     41    }
     42  }
     43 
    2844  public class CVRPEvaluation: VRPEvaluation {
    2945    public double Overload { get; set; }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPEvaluator.cs

    r4752 r6752  
    4848
    4949    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
     50      TourInsertionInfo tourInfo = new TourInsertionInfo();
     51      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
     52     
    5053      IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
    5154      DoubleArray demand = instance.Demand;
    … …  
    5457      double overweight = 0.0;
    5558      double distance = 0.0;
     59
     60      double capacity = cvrpInstance.Capacity.Value;
     61      for (int i = 0; i <= tour.Stops.Count; i++) {
     62        int end = 0;
     63        if (i < tour.Stops.Count)
     64          end = tour.Stops[i];
     65
     66        delivered += demand[end];
     67      }
     68
     69      double spareCapacity = capacity - delivered;
    5670
    5771      //simulate a tour, start and end at depot
    … …  
    6882        distance += currentDistace;
    6983
    70         delivered += demand[end];
     84        CVRPInsertionInfo stopInfo = new CVRPInsertionInfo(start, end, spareCapacity);
     85        tourInfo.AddStopInsertionInfo(stopInfo);
    7186      }
    7287
    … …  
    7792      eval.VehicleUtilization += 1;
    7893
    79       double capacity = cvrpInstance.Capacity.Value;
    8094      if (delivered > capacity) {
    8195        overweight = delivered - capacity;
    … …  
    86100      eval.Penalty += penalty;
    87101      eval.Quality += penalty;
     102      tourInfo.Penalty = penalty;
     103    }
     104
     105    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     106      out bool feasible) {
     107      CVRPInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPInsertionInfo;
     108     
     109      double costs = 0;
     110      feasible = tourInsertionInfo.Penalty < double.Epsilon;
     111
     112      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
     113      double overloadPenalty = cvrp.OverloadPenalty.Value;
     114
     115      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     116      double newDistance =
     117        instance.GetDistance(insertionInfo.Start, customer) +
     118        instance.GetDistance(customer, insertionInfo.End);
     119      costs += instance.DistanceFactor.Value * (newDistance - distance);
     120
     121      double demand = instance.Demand[customer];
     122      if (demand > insertionInfo.SpareCapacity) {
     123        feasible = false;
     124
     125        if(insertionInfo.SpareCapacity >= 0)
     126          costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
     127        else
     128          costs += demand * overloadPenalty;
     129      }
     130     
     131      return costs;
    88132    }
    89133

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluation.cs

    r6710 r6752  
    2424using System.Linq;
    2525using System.Text;
     26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using HeuristicLab.Common;
    2628
    2729namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
     30  public class CVRPPDTWInsertionInfo : CVRPTWInsertionInfo {
     31    private List<int> visited;
     32
     33    public List<int> Visited {
     34      get { return visited; }
     35    }
     36
     37    private double arrivalSpareCapacity;
     38
     39    public double ArrivalSpareCapacity {
     40      get { return arrivalSpareCapacity;  }
     41    }
     42
     43    public CVRPPDTWInsertionInfo(int start, int end, double spareCapacity, double arrivalTime, double leaveTime, double spareTime, double waitingTime, List<int> visited, double arrivalSpareCapacity)
     44      : base(start, end, spareCapacity, arrivalTime, leaveTime, spareTime, waitingTime) {
     45        this.visited = visited;
     46        this.arrivalSpareCapacity = arrivalSpareCapacity;
     47    }
     48  }
     49 
    2850  public class CVRPPDTWEvaluation: CVRPTWEvaluation {
    2951    public int PickupViolations { get; set; }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPPDTW/CVRPPDTWEvaluator.cs

    r6710 r6752  
    4848
    4949    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
     50      TourInsertionInfo tourInfo = new TourInsertionInfo();
     51      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
     52
    5053      IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
    5154      DoubleArray demand = instance.Demand;
    … …  
    8689        distance += currentDistace;
    8790
     91        double arrivalTime = time;
     92
    8893        //check if it was serviced on time
    8994        if (time > dueTime[end])
    … …  
    9499        if (time < readyTime[end])
    95100          currentWaitingTime = readyTime[end] - time;
     101
     102        double waitTime = readyTime[end] - time;
     103
    96104        waitingTime += currentWaitingTime;
    97105        time += currentWaitingTime;
     106
     107        double spareTime = dueTime[end] - time;
    98108
    99109        //service
    … …  
    103113
    104114        //Pickup / deliver
     115        double arrivalSpareCapacity = capacity - currentLoad;
     116
    105117        bool validPickupDelivery =
    106118          validPickupDelivery =
    … …  
    110122        if (validPickupDelivery) {
    111123          currentLoad += demand[end];
    112 
    113           if (currentLoad > capacity)
    114             overweight += currentLoad - capacity;
    115124        } else {
    116125          pickupViolations++;
    117126        }
     127
     128        if (currentLoad > capacity)
     129          overweight += currentLoad - capacity;
     130
     131        double spareCapacity = capacity - currentLoad;
     132        CVRPPDTWInsertionInfo stopInfo = new CVRPPDTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime, new List<int>(stops.Keys), arrivalSpareCapacity);
     133        tourInfo.AddStopInsertionInfo(stopInfo);
    118134
    119135        stops.Add(end, true);
    … …  
    126142
    127143      (eval as CVRPEvaluation).Overload += overweight;
     144      double tourPenalty = 0;
    128145      double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
    129146      eval.Penalty += penalty;
    130147      eval.Quality += penalty;
     148      tourPenalty += penalty;
    131149
    132150      (eval as CVRPTWEvaluation).Tardiness += tardiness;
    … …  
    136154      eval.Penalty += penalty;
    137155      eval.Quality += penalty;
     156      tourPenalty += penalty;
    138157
    139158      (eval as CVRPPDTWEvaluation).PickupViolations += pickupViolations;
    140159      penalty = pickupViolations * pdp.PickupViolationPenalty.Value;
    141160      eval.Penalty += penalty;
     161      tourPenalty += penalty;
    142162
    143163      eval.Quality += penalty;
    144164      eval.Quality += time * vrptw.TimeFactor.Value;
     165      tourInfo.Penalty = tourPenalty;
     166    }
     167
     168    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     169      out bool feasible) {
     170      CVRPPDTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPPDTWInsertionInfo;
     171
     172      double costs = 0;
     173      feasible = tourInsertionInfo.Penalty < double.Epsilon;
     174      bool tourFeasible = true;
     175
     176      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
     177      double overloadPenalty = cvrp.OverloadPenalty.Value;
     178
     179      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
     180      DoubleArray dueTime = vrptw.DueTime;
     181      DoubleArray readyTime = vrptw.ReadyTime;
     182      DoubleArray serviceTimes = vrptw.ServiceTime;
     183      double tardinessPenalty = vrptw.TardinessPenalty.Value;
     184
     185      IPickupAndDeliveryProblemInstance pdp = instance as IPickupAndDeliveryProblemInstance;
     186      IntArray pickupDeliveryLocation = pdp.PickupDeliveryLocation;
     187      double pickupPenalty = pdp.PickupViolationPenalty.Value;
     188
     189      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     190      double newDistance =
     191        instance.GetDistance(insertionInfo.Start, customer) +
     192        instance.GetDistance(customer, insertionInfo.End);
     193      costs += instance.DistanceFactor.Value * (newDistance - distance);
     194
     195      double demand = instance.Demand[customer];
     196      if (demand > insertionInfo.ArrivalSpareCapacity) {
     197        tourFeasible = feasible = false;
     198        if (insertionInfo.ArrivalSpareCapacity >= 0)
     199          costs += (demand - insertionInfo.ArrivalSpareCapacity) * overloadPenalty;
     200        else
     201          costs += demand * overloadPenalty;
     202      }
     203      int destination = pickupDeliveryLocation[customer];
     204
     205      bool validPickup = true;
     206      if (demand < 0 && !insertionInfo.Visited.Contains(destination)) {
     207        tourFeasible = feasible = false;
     208        validPickup = false;
     209        costs += pickupPenalty;
     210      }
     211
     212      double time = 0;
     213      double tardiness = 0;
     214
     215      if (index > 0)
     216        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
     217      time += instance.GetDistance(insertionInfo.Start, customer);
     218      if (time > dueTime[customer]) {
     219        tardiness += time - dueTime[customer];
     220      }
     221      if (time < readyTime[customer])
     222        time += readyTime[customer] - time;
     223      time += serviceTimes[customer];
     224      time += instance.GetDistance(customer, insertionInfo.End);
     225
     226      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
     227      for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) {
     228        CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo;
     229
     230        if (demand >= 0) {
     231          if (nextStop.End == destination) {
     232            demand = 0;
     233            costs -= pickupPenalty;
     234            if (tourInsertionInfo.Penalty == pickupPenalty && tourFeasible)
     235              feasible = true;
     236          } else if (nextStop.SpareCapacity < 0) {
     237            costs += demand * overloadPenalty;
     238          } else if (nextStop.SpareCapacity < demand) {
     239            tourFeasible = feasible = false;
     240            costs += (demand - nextStop.SpareCapacity) * overloadPenalty;
     241          }
     242        } else if (validPickup) {
     243          if (nextStop.SpareCapacity < 0) {
     244            costs += Math.Max(demand, nextStop.SpareCapacity) * overloadPenalty;
     245          }
     246        }
     247
     248        if (additionalTime < 0) {
     249          //arrive earlier than before
     250          //wait probably
     251          if (nextStop.WaitingTime < 0) {
     252            double wait = nextStop.WaitingTime - additionalTime;
     253            if (wait > 0)
     254              additionalTime += wait;
     255          } else {
     256            additionalTime = 0;
     257          }
     258
     259          //check due date, decrease tardiness
     260          if (nextStop.SpareTime < 0) {
     261            costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty;
     262          }
     263        } else {
     264          //arrive later than before, probably don't have to wait
     265          if (nextStop.WaitingTime > 0) {
     266            additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime);
     267          }
     268
     269          //check due date
     270          if (nextStop.SpareTime > 0) {
     271            double spare = nextStop.SpareTime - additionalTime;
     272            if (spare < 0)
     273              tardiness += -spare;
     274          } else {
     275            tardiness += additionalTime;
     276          }
     277        }
     278      }
     279
     280      costs += additionalTime * vrptw.TimeFactor.Value;
     281
     282      if (tardiness > 0) {
     283        tourFeasible = feasible = false;
     284      }
     285
     286      costs += tardiness * tardinessPenalty;
     287
     288      return costs;
    145289    }
    146290

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluation.cs

    r4454 r6752  
    2424using System.Linq;
    2525using System.Text;
     26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using HeuristicLab.Common;
    2628
    2729namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
     30  public class CVRPTWInsertionInfo : CVRPInsertionInfo {
     31    private double arrivalTime;
     32
     33    public double ArrivalTime {
     34      get { return arrivalTime; }
     35    }
     36
     37    private double leaveTime;
     38
     39    public double LeaveTime {
     40      get { return leaveTime; }
     41    }
     42
     43    private double spareTime;
     44
     45    public double SpareTime {
     46      get { return spareTime; }
     47    }
     48
     49    private double waitingTime;
     50
     51    public double WaitingTime {
     52      get { return waitingTime; }
     53    }
     54
     55    public CVRPTWInsertionInfo(int start, int end, double spareCapacity, double arrivalTime, double leaveTime, double spareTime, double waitingTime)
     56      : base(start, end, spareCapacity) {
     57        this.arrivalTime = arrivalTime;
     58        this.leaveTime = leaveTime;
     59        this.spareTime = spareTime;
     60        this.waitingTime = waitingTime;
     61    }
     62  }
     63 
    2864  public class CVRPTWEvaluation: CVRPEvaluation {
    2965    public double Tardiness { get; set; }

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/CVRP/CVRPTW/CVRPTWEvaluator.cs

    r4752 r6752  
    5252
    5353    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
     54      TourInsertionInfo tourInfo = new TourInsertionInfo();
     55      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
     56     
    5457      IHomogenousCapacitatedProblemInstance cvrpInstance = instance as IHomogenousCapacitatedProblemInstance;
    5558      DoubleArray demand = instance.Demand;
    … …  
    6770      double overweight = 0.0;
    6871      double distance = 0.0;
     72
     73      double capacity = cvrpInstance.Capacity.Value;
     74      for (int i = 0; i <= tour.Stops.Count; i++) {
     75        int end = 0;
     76        if (i < tour.Stops.Count)
     77          end = tour.Stops[i];
     78
     79        delivered += demand[end];
     80      }
     81
     82      double spareCapacity = capacity - delivered;
    6983
    7084      //simulate a tour, start and end at depot
    … …  
    8296        distance += currentDistace;
    8397
     98        double arrivalTime = time;
     99
    84100        //check if it was serviced on time
    85101        if (time > dueTime[end])
    … …  
    90106        if (time < readyTime[end])
    91107          currentWaitingTime = readyTime[end] - time;
     108
     109        double waitTime = readyTime[end]-time;
     110
    92111        waitingTime += currentWaitingTime;
    93112        time += currentWaitingTime;
     113
     114        double spareTime = dueTime[end] - time;
    94115
    95116        //service
    … …  
    97118        serviceTime += currentServiceTime;
    98119        time += currentServiceTime;
    99         delivered += demand[end];
     120
     121        CVRPTWInsertionInfo stopInfo = new CVRPTWInsertionInfo(start, end, spareCapacity, arrivalTime, time, spareTime, waitTime);
     122        tourInfo.AddStopInsertionInfo(stopInfo);
    100123      }
    101124
    … …  
    105128      eval.VehicleUtilization += 1;
    106129
    107       double capacity = cvrpInstance.Capacity.Value;
    108130      if (delivered > capacity) {
    109131        overweight = delivered - capacity;
    … …  
    111133
    112134      (eval as CVRPEvaluation).Overload += overweight;
     135      double tourPenalty = 0;
    113136      double penalty = overweight * cvrpInstance.OverloadPenalty.Value;
    114137      eval.Penalty += penalty;
    115138      eval.Quality += penalty;
     139      tourPenalty += penalty;
    116140
    117141      (eval as CVRPTWEvaluation).Tardiness += tardiness;
    … …  
    121145      eval.Penalty += penalty;
    122146      eval.Quality += penalty;
     147      tourPenalty += penalty;
    123148      eval.Quality += time * vrptw.TimeFactor.Value;
     149      tourInfo.Penalty = tourPenalty;
     150    }
     151
     152    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     153      out bool feasible) {
     154      CVRPTWInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo;
     155
     156      double costs = 0;
     157      feasible = tourInsertionInfo.Penalty < double.Epsilon;
     158
     159      ICapacitatedProblemInstance cvrp = instance as ICapacitatedProblemInstance;
     160      double overloadPenalty = cvrp.OverloadPenalty.Value;
     161
     162      ITimeWindowedProblemInstance vrptw = instance as ITimeWindowedProblemInstance;
     163      DoubleArray dueTime = vrptw.DueTime;
     164      DoubleArray readyTime = vrptw.ReadyTime;
     165      DoubleArray serviceTimes = vrptw.ServiceTime;
     166      double tardinessPenalty = vrptw.TardinessPenalty.Value;
     167
     168      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     169      double newDistance =
     170        instance.GetDistance(insertionInfo.Start, customer) +
     171        instance.GetDistance(customer, insertionInfo.End);
     172      costs += instance.DistanceFactor.Value * (newDistance - distance);
     173
     174      double demand = instance.Demand[customer];
     175      if (demand > insertionInfo.SpareCapacity) {
     176        feasible = false;
     177        if (insertionInfo.SpareCapacity >= 0)
     178          costs += (demand - insertionInfo.SpareCapacity) * overloadPenalty;
     179        else
     180          costs += demand * overloadPenalty;
     181      }
     182
     183      double time = 0;
     184      double tardiness = 0;
     185
     186      if (index > 0)
     187        time = (tourInsertionInfo.GetStopInsertionInfo(index - 1) as CVRPTWInsertionInfo).LeaveTime;
     188      time += instance.GetDistance(insertionInfo.Start, customer);
     189      if (time > dueTime[customer]) {
     190        tardiness += time - dueTime[customer];
     191      }
     192      if (time < readyTime[customer])
     193        time += readyTime[customer] - time;
     194      time += serviceTimes[customer];
     195      time += instance.GetDistance(customer, insertionInfo.End);
     196
     197      double additionalTime = time - (tourInsertionInfo.GetStopInsertionInfo(index) as CVRPTWInsertionInfo).ArrivalTime;
     198      for (int i = index; i < tourInsertionInfo.GetStopCount(); i++) {
     199        CVRPTWInsertionInfo nextStop = tourInsertionInfo.GetStopInsertionInfo(i) as CVRPTWInsertionInfo;
     200
     201        if (additionalTime < 0) {
     202          //arrive earlier than before
     203          //wait probably
     204          if (nextStop.WaitingTime < 0) {
     205            double wait = nextStop.WaitingTime - additionalTime;
     206            if (wait > 0)
     207              additionalTime += wait;
     208          } else {
     209            additionalTime = 0;
     210          }
     211
     212          //check due date, decrease tardiness
     213          if (nextStop.SpareTime < 0) {
     214            costs += Math.Max(nextStop.SpareTime, additionalTime) * tardinessPenalty;
     215          }
     216        } else {
     217          //arrive later than before, probably don't have to wait
     218          if (nextStop.WaitingTime > 0) {
     219            additionalTime -= Math.Min(additionalTime, nextStop.WaitingTime);           
     220          }
     221
     222          //check due date
     223          if (nextStop.SpareTime > 0) {
     224            double spare = nextStop.SpareTime - additionalTime;
     225            if (spare < 0)
     226              tardiness += -spare;
     227          } else {
     228            tardiness += additionalTime;
     229          }
     230        }
     231      }
     232
     233      costs += additionalTime * vrptw.TimeFactor.Value;
     234
     235      if (tardiness > 0) {
     236        feasible = false;
     237      }
     238
     239      costs += tardiness * tardinessPenalty;
     240
     241      return costs;
    124242    }
    125243

  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/ProblemInstances/SingleDepotVRP/SingleDepotVRPEvaluator.cs

    r4752 r6752  
    4141  public class SingleDepotVRPEvaluator: VRPEvaluator {
    4242    protected override void EvaluateTour(VRPEvaluation eval, IVRPProblemInstance instance, Tour tour) {
     43      TourInsertionInfo tourInfo = new TourInsertionInfo();
     44      eval.InsertionInfo.AddTourInsertionInfo(tourInfo);
     45     
    4346      double distance = 0.0;
    4447      double quality = 0.0;
    … …  
    5659        double currentDistace = instance.GetDistance(start, end);
    5760        distance += currentDistace;
     61
     62        StopInsertionInfo stopInfo = new StopInsertionInfo(start, end);
     63        tourInfo.AddStopInsertionInfo(stopInfo);
    5864      }
    5965
    … …  
    6773
    6874      eval.Quality += quality;
     75    }
     76
     77    protected override double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer,
     78      out bool feasible) {
     79      StopInsertionInfo insertionInfo = tourInsertionInfo.GetStopInsertionInfo(index);
     80     
     81      double costs = 0;
     82      feasible = true;
     83
     84      double distance = instance.GetDistance(insertionInfo.Start, insertionInfo.End);
     85      double newDistance =
     86        instance.GetDistance(insertionInfo.Start, customer) +
     87        instance.GetDistance(customer, insertionInfo.End);
     88
     89      costs += instance.DistanceFactor.Value * (newDistance - distance);
     90
     91      return costs;
    6992    }
    7093   

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

    r4454 r6752  
    2424using System.Linq;
    2525using System.Text;
     26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     27using HeuristicLab.Core;
     28using HeuristicLab.Common;
    2629
    2730namespace HeuristicLab.Problems.VehicleRouting.ProblemInstances {
     31  public class StopInsertionInfo {   
     32    private int start;
     33
     34    public int Start {
     35      get { return start; }
     36    }
     37
     38    private int end;
     39
     40    public int End {
     41      get { return end; }
     42    }
     43       
     44    public StopInsertionInfo(int start, int end)
     45      : base() {
     46        this.start = start;
     47        this.end = end;
     48    }
     49  }
     50
     51  public class TourInsertionInfo {
     52    public double Penalty { get; set; }
     53
     54    private List<StopInsertionInfo> stopInsertionInfos;
     55
     56    public TourInsertionInfo()
     57      : base() {
     58      stopInsertionInfos = new List<StopInsertionInfo>();
     59    }
     60
     61    public void AddStopInsertionInfo(StopInsertionInfo info) {
     62      stopInsertionInfos.Add(info);
     63    }
     64
     65   public StopInsertionInfo GetStopInsertionInfo(int stop) {
     66      return stopInsertionInfos[stop];
     67    }
     68
     69    public int GetStopCount() {
     70      return stopInsertionInfos.Count;
     71    }
     72  }
     73
     74  public class InsertionInfo {
     75    private List<TourInsertionInfo> tourInsertionInfos;
     76   
     77    public InsertionInfo()
     78      : base() {
     79        tourInsertionInfos = new List<TourInsertionInfo>();
     80    }
     81
     82    public void AddTourInsertionInfo(TourInsertionInfo info) {     
     83      tourInsertionInfos.Add(info);
     84    }
     85
     86    public TourInsertionInfo GetTourInsertionInfo(int tour) {
     87      return tourInsertionInfos[tour];
     88    }
     89  }
     90 
    2891  public class VRPEvaluation {
    2992    public double Quality { get; set; }
    3093    public double Distance { get; set; }
    3194    public int VehicleUtilization { get; set; }
     95    public InsertionInfo InsertionInfo { get; set; }
    3296
    3397    public double Penalty { get; set; }
     98
     99    public VRPEvaluation() {
     100      InsertionInfo = new InsertionInfo();
     101    }
    34102  }
    35103}

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

    r5127 r6752  
    109109    }
    110110
     111    protected abstract double GetTourInsertionCosts(IVRPProblemInstance instance, TourInsertionInfo tourInsertionInfo, int index, int customer, out bool feasible);
     112
     113    public double GetInsertionCosts(IVRPProblemInstance instance, VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
     114      bool tourFeasible;
     115      double costs = GetTourInsertionCosts(
     116        instance,
     117        eval.InsertionInfo.GetTourInsertionInfo(tour), index,
     118        customer, out tourFeasible);
     119
     120      feasible = tourFeasible;
     121
     122      return costs;
     123    }
     124
    111125    public VRPEvaluation Evaluate(IVRPProblemInstance instance, IVRPEncoding solution) {
    112126      VRPEvaluation evaluation = CreateTourEvaluation();

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

    r6711 r6752  
    230230    }
    231231
     232    public double GetInsertionCosts(VRPEvaluation eval, int customer, int tour, int index, out bool feasible) {
     233      return evaluator.GetInsertionCosts(this, eval, customer, tour, index, out feasible);
     234    }
     235
    232236    protected void EvalBestKnownSolution() {
    233237      if (BestKnownSolution != null) {
Note: See TracChangeset for help on using the changeset viewer.