Changeset 8782


Ignore:
Timestamp:
10/10/12 16:30:19 (10 years ago)
Author:
svonolfe
Message:

modified fitness function of dial a ride

Location:
branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Operators/DialARideEvaluator.cs

    r8714 r8782  
    143143        //check if it was serviced on time
    144144        if (time > dueTime[endIndex])
    145           tardiness += time - dueTime[endIndex];
     145          tardiness += Math.Min(1000000, Math.Pow((vrptw.TardinessPenalty.Value * Math.E), (time - dueTime[endIndex])) - 1.0);
    146146
    147147        //wait
     
    220220      (eval as CVRPTWEvaluation).TravelTime += time;
    221221
    222       penalty = tardiness * vrptw.TardinessPenalty.Value;
     222      penalty = tardiness;
    223223      eval.Penalty += penalty;
    224224      eval.Quality += penalty;
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/PriorityDispatching.cs

    r8777 r8782  
    3737      Parameters.Add(new ValueLookupParameter<RealVector>("Weights", "The weights for the individual priorities."));
    3838      WeightsParameter.Value = new RealVector(new double[] {
    39          100.000, 100.000,  22.349,  74.573,  18.424,  28.913,   0.331,  91.323,  36.969,  44.992,  64.892,  30.736,  23.113,  36.458,   6.178,  99.065,
     39         100.000, 100.000,  22.349,  74.573,  18.424,  28.913,   0.331,  91.323,  36.969,  44.992,  64.892,  30.736,  23.113,  36.458,   6.178,  99.065, 100.0, 100.0
    4040      });
    4141    }
     
    5353        var tmp = new Dictionary<Vehicle, Tuple<Order, double>>();
    5454        foreach (var vehicle in waitingVehicles) {
    55           var orders = waitingOrders.Concat(GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == vehicle.Id));
     55          var pickedupOrders = GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == vehicle.Id);
     56          var orders = waitingOrders.Concat(pickedupOrders);
    5657          if (orders.Any()) {
    5758            Order selectedOrder;
     
    6667          var order = a.Key;
    6768
     69          bool first = true;
     70
     71          XY target;
    6872          MoveVehicleAction action;
    6973          if (order.OrderState == OrderState.Waiting) {
     74            target = new XY(order.PickupXCoord, order.PickupYCoord);
    7075            action = new MoveVehicleAction(bestVehicle.Id, order.PickupXCoord, order.PickupYCoord, VehicleAction.Pickup, order, scenario.AllowDiversion, scenario.DistanceMeasure);
    7176          } else {
     77            target = new XY(order.DeliveryXCoord, order.DeliveryYCoord);
    7278            action = new MoveVehicleAction(bestVehicle.Id, order.DeliveryXCoord, order.DeliveryYCoord, VehicleAction.Deliver, order, scenario.AllowDiversion, scenario.DistanceMeasure);
    7379          }
    74           SetAction(action);
     80          var pickedupOrders = GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == bestVehicle.Id);
     81          var pickedupOrdersAtDestination = pickedupOrders.Where(o => o.DeliveryXCoord == target.X && o.DeliveryYCoord == target.Y);
     82          List<MoveVehicleAction> deliveryActions = new List<MoveVehicleAction>();
     83          foreach (var pickedupOrder in pickedupOrdersAtDestination) {
     84            if (pickedupOrder != order) {
     85              MoveVehicleAction deliveryAction = new MoveVehicleAction(bestVehicle.Id, pickedupOrder.DeliveryXCoord, pickedupOrder.DeliveryYCoord, VehicleAction.Deliver, pickedupOrder, scenario.AllowDiversion, scenario.DistanceMeasure);
     86              if (first) {
     87                SetAction(deliveryAction);
     88                first = false;
     89              } else {
     90                AppendAction(deliveryAction);
     91              }
     92            }
     93          }
     94
     95          if (first) {
     96            SetAction(action);
     97            first = false;
     98          } else {
     99            AppendAction(action);
     100          }
    75101          waitingVehicles.Remove(bestVehicle);
    76102          waitingOrders.Remove(order);
     
    94120                                   .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
    95121      var deliveryOrdersByLocation = (from o in orders
    96                                       where !IsPickup(o, instance)
     122                                      where !IsPickup(o, instance) && o.Vehicle == vehicle.Id
    97123                                      group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
    98124                                      .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
    99       var destinations = deliveryOrdersByLocation.Keys.ToArray();// vehicle.PickedUpOrders.Select(x => GetOrder(x)).Select(x => new XY(x.DeliveryXCoord, x.DeliveryYCoord)).ToArray();
     125      var destinations = deliveryOrdersByLocation.Keys.ToArray();
    100126      foreach (var o in orders) {
    101127        if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
    102128       
    103         var target = new XY(o.PickupXCoord, o.PickupYCoord);
    104         if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
    105 
    106         var destinationDifference = destinations.Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
    107         var courierDifference = GetVehicles().Where(x => x != vehicle).Select(x => new XY(x.TargetPositionX, x.TargetPositionY))
    108           .Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
    109 
    110         var variables = new Dictionary<string, double>();
    111         variables.Add("Distance", scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
    112         variables.Add("EarliestTimeOfArrival", vehicle.ReadyTime + variables["Distance"]); // scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
    113         variables.Add("DueDate", o.DeliveryDueTime - GetSimulationTime());
    114         variables.Add("StartDate", IsPickup(o, instance) ? o.PickupReadyTime - GetSimulationTime() : 0);
    115         variables.Add("PickupOrdersAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Count() : 0);
    116         variables.Add("PickupOrderItemsAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Sum(x => x.Demand) : 0);
    117         variables.Add("DeliveryOrdersAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Count() : 0);
    118         variables.Add("DeliveryOrderItemsAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Sum(x => x.Demand) : 0);
    119         variables.Add("AverageDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Average() : 0);
    120         variables.Add("MinimumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Min() : 0);
    121         variables.Add("MaximumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Max() : 0);
    122         variables.Add("NumberOfOtherCouriersToTarget", GetVehicles().Count > 2 ? GetVehicles().Where(x => x != vehicle).Count(x => target.X == x.TargetPositionX && target.Y == x.TargetPositionY) : 0);
    123         variables.Add("AverageDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Average() : 0);
    124         variables.Add("MinimumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Min() : 0);
    125         variables.Add("MaximumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Max() : 0);
    126         variables.Add("DemandSize", o.Demand);
    127 
    128         var prio =
    129             weights[0] * variables["DueDate"]
    130           + weights[1] * variables["StartDate"]
    131           + weights[2] * variables["PickupOrdersAtTarget"]
    132           + weights[3] * variables["Distance"]
    133           + weights[4] * variables["AverageDistanceToDestinations"]
    134           + weights[5] * variables["MinimumDistanceToDestinations"]
    135           + weights[6] * variables["MaximumDistanceToDestinations"]
    136           + weights[7] * variables["NumberOfOtherCouriersToTarget"]
    137           + weights[8] * variables["AverageDistanceToOtherCouriers"]
    138           + weights[9] * variables["EarliestTimeOfArrival"]
    139           + weights[10] * variables["DeliveryOrdersAtTarget"]
    140           + weights[11] * variables["PickupOrderItemsAtTarget"]
    141           + weights[12] * variables["DeliveryOrderItemsAtTarget"]
    142           + weights[13] * variables["MinimumDistanceToOtherCouriers"]
    143           + weights[14] * variables["MaximumDistanceToOtherCouriers"]
    144           + weights[15] * variables["DemandSize"];
     129         double prio;
     130         if (!IsPickup(o, instance) && vehicle.TargetPositionX == o.DeliveryXCoord && vehicle.TargetPositionY == o.DeliveryYCoord) {
     131           prio = double.MaxValue;
     132         } else {
     133           var target = new XY(o.PickupXCoord, o.PickupYCoord);
     134           if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
     135
     136           var destinationDifference = destinations.Select(x => scenario.DistanceMeasure.GetDistance(o.DeliveryXCoord, o.DeliveryYCoord, x.X, x.Y)).ToArray();
     137           var courierDifference = GetVehicles().Where(x => x != vehicle).Select(x => new XY(x.TargetPositionX, x.TargetPositionY))
     138             .Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
     139
     140           var commonDestinations = orders.Where(x => !IsPickup(x, instance) && x.Vehicle == vehicle.Id &&
     141                                    x.DeliveryXCoord == o.PickupXCoord &&
     142                                    x.DeliveryYCoord == o.PickupYCoord);
     143
     144           var variables = new Dictionary<string, double>();
     145           variables.Add("Distance", scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
     146           variables.Add("EarliestTimeOfArrival", vehicle.ReadyTime + variables["Distance"]);
     147           variables.Add("DueDate", o.DeliveryDueTime - GetSimulationTime());
     148           variables.Add("StartDate", IsPickup(o, instance) ? o.PickupReadyTime - GetSimulationTime() : 0);
     149           variables.Add("PickupOrdersAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Count() : 0);
     150           variables.Add("PickupOrderItemsAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Sum(x => x.Demand) : 0);
     151           variables.Add("DeliveryOrdersAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Count() : 0);
     152           variables.Add("DeliveryOrderItemsAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Sum(x => x.Demand) : 0);
     153           variables.Add("AverageDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Average() : 0);
     154           variables.Add("MinimumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Min() : 0);
     155           variables.Add("MaximumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Max() : 0);
     156           variables.Add("NumberOfOtherCouriersToTarget", GetVehicles().Count > 2 ? GetVehicles().Where(x => x != vehicle).Count(x => target.X == x.TargetPositionX && target.Y == x.TargetPositionY) : 0);
     157           variables.Add("AverageDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Average() : 0);
     158           variables.Add("MinimumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Min() : 0);
     159           variables.Add("MaximumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Max() : 0);
     160           variables.Add("DemandSize", o.Demand);
     161           variables.Add("Slack", o.DeliveryDueTime - GetSimulationTime()
     162             - (vehicle.ReadyTime + variables["Distance"] +
     163                (IsPickup(o, instance) ? (o.PickupServiceTime + scenario.DistanceMeasure.GetDistance(o.PickupXCoord, o.PickupYCoord, o.DeliveryXCoord, o.DeliveryYCoord)) : 0)));
     164           variables.Add("EDD", commonDestinations.Any() ? commonDestinations.Min(d => d.DeliveryDueTime - GetSimulationTime()) : 0);
     165
     166           prio =
     167               weights[0] * variables["DueDate"]
     168             + weights[1] * variables["StartDate"]
     169             + weights[2] * variables["PickupOrdersAtTarget"]
     170             + weights[3] * variables["Distance"]
     171             + weights[4] * variables["AverageDistanceToDestinations"]
     172             + weights[5] * variables["MinimumDistanceToDestinations"]
     173             + weights[6] * variables["MaximumDistanceToDestinations"]
     174             + weights[7] * variables["NumberOfOtherCouriersToTarget"]
     175             + weights[8] * variables["AverageDistanceToOtherCouriers"]
     176             + weights[9] * variables["EarliestTimeOfArrival"]
     177             + weights[10] * variables["DeliveryOrdersAtTarget"]
     178             + weights[11] * variables["PickupOrderItemsAtTarget"]
     179             + weights[12] * variables["DeliveryOrderItemsAtTarget"]
     180             + weights[13] * variables["MinimumDistanceToOtherCouriers"]
     181             + weights[14] * variables["MaximumDistanceToOtherCouriers"]
     182             + weights[15] * variables["DemandSize"]
     183             + weights[16] * variables["Slack"]
     184             + weights[17] * variables["EDD"];
     185         }
    145186
    146187        if (prio > bestPriority) {
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/PickupDeliveryAnalyzer.cs

    r8777 r8782  
    211211
    212212        results.Add(new Result("LeadTime", new DoubleValue()));
     213
     214        results.Add(new Result("TardinessPenalty", new DoubleValue()));
    213215      }
    214216
     
    250252
    251253      results["TimeHistogram"].Value = timeHistogram;
     254
     255      double tardiness = 0;
     256      foreach(Order o in simulation.Orders) {
     257        if(o.Tardiness > 0) {
     258          tardiness += Math.Min(1000000, Math.Pow((scenario.TardinessPenaltyParameter.Value.Value * Math.E), o.Tardiness) - 1.0);
     259        }
     260      }
     261      (results["TardinessPenalty"].Value as DoubleValue).Value = tardiness;
    252262    }
    253263
Note: See TracChangeset for help on using the changeset viewer.