source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/PriorityDispatching.cs @ 8782

Last change on this file since 8782 was 8782, checked in by svonolfe, 10 years ago

modified fitness function of dial a ride

File size: 12.0 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using HeuristicLab.Common;
6using HeuristicLab.Core;
7using HeuristicLab.Encodings.RealVectorEncoding;
8using HeuristicLab.Parameters;
9using HeuristicLab.PDPSimulation.DomainModel;
10using HeuristicLab.PDPSimulation.Operators;
11using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
12
13namespace HeuristicLab.PDPSimulation {
14  [Item("PriorityDispatching", "")]
15  [StorableClass]
16  public sealed class PriorityDispatching : DynamicPDPOptimization {
17
18    private bool IsIdle(Vehicle v) {
19      return v.CurrentOrder == Guid.Empty;
20    }
21
22    protected override bool OptimizationRequired(ChangeInformation changeInformation) {
23      // either there are vehicles waiting and there are orders to dispatch
24      // or there are new orders and waiting vehicles
25      return (GetVehicles().Any(x => IsIdle(x))
26        && GetOrders().Any(x => x.AssignedVehicle == Guid.Empty || GetVehicles().Any(y => IsIdle(y) && x.AssignedVehicle == y.Id)));
27    }
28
29    public IValueLookupParameter<RealVector> WeightsParameter {
30      get { return (IValueLookupParameter<RealVector>)Parameters["Weights"]; }
31    }
32
33    [StorableConstructor]
34    private PriorityDispatching(bool deserializing) : base(deserializing) { }
35    private PriorityDispatching(PriorityDispatching original, Cloner cloner) : base(original, cloner) { }
36    public PriorityDispatching() {
37      Parameters.Add(new ValueLookupParameter<RealVector>("Weights", "The weights for the individual priorities."));
38      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, 100.0, 100.0
40      });
41    }
42
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new PriorityDispatching(this, cloner);
45    }
46
47    protected override bool PerformOptimization(DynamicPDProblemInstance instance, ChangeInformation changeInformation) {
48      var waitingVehicles = GetVehicles().Where(x => IsIdle(x)).ToList();
49      var waitingOrders = GetOrders().Where(x => x.AssignedVehicle == Guid.Empty).ToList();
50
51      while (waitingVehicles.Any() && (waitingOrders.Any()
52        || GetOrders().Any(x => x.OrderState == OrderState.PickedUp && waitingVehicles.Any(y => y.Id == x.AssignedVehicle)))) {
53        var tmp = new Dictionary<Vehicle, Tuple<Order, double>>();
54        foreach (var vehicle in waitingVehicles) {
55          var pickedupOrders = GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == vehicle.Id);
56          var orders = waitingOrders.Concat(pickedupOrders);
57          if (orders.Any()) {
58            Order selectedOrder;
59            double priority;
60            GetHighestPriorityOrder((DynPDPProblemInstance)instance.StaticInstance, vehicle, orders, out selectedOrder, out priority);
61            tmp[vehicle] = Tuple.Create(selectedOrder, priority);
62          }
63        }
64        var assignment = tmp.GroupBy(x => x.Value.Item1, x => new { Vehicle = x.Key, Priority = x.Value.Item2 });
65        foreach (var a in assignment) {
66          var bestVehicle = a.MaxItems(x => x.Priority).Select(x => x.Vehicle).First();
67          var order = a.Key;
68
69          bool first = true;
70
71          XY target;
72          MoveVehicleAction action;
73          if (order.OrderState == OrderState.Waiting) {
74            target = new XY(order.PickupXCoord, order.PickupYCoord);
75            action = new MoveVehicleAction(bestVehicle.Id, order.PickupXCoord, order.PickupYCoord, VehicleAction.Pickup, order, scenario.AllowDiversion, scenario.DistanceMeasure);
76          } else {
77            target = new XY(order.DeliveryXCoord, order.DeliveryYCoord);
78            action = new MoveVehicleAction(bestVehicle.Id, order.DeliveryXCoord, order.DeliveryYCoord, VehicleAction.Deliver, order, scenario.AllowDiversion, scenario.DistanceMeasure);
79          }
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          }
101          waitingVehicles.Remove(bestVehicle);
102          waitingOrders.Remove(order);
103
104          foreach (var assignedOrder in GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting))
105            assignedOrder.AssignedVehicle = Guid.Empty;
106
107          order.AssignedVehicle = bestVehicle.Id;
108        }
109      }
110      return true;
111    }
112
113    private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
114      var weights = WeightsParameter.Value;
115      Order best = null;
116      double bestPriority = double.MinValue;
117      var pickupOrdersByLocation = (from o in orders
118                                   where IsPickup(o, instance)
119                                   group o by new { X = o.PickupXCoord, Y = o.PickupYCoord })
120                                   .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
121      var deliveryOrdersByLocation = (from o in orders
122                                      where !IsPickup(o, instance) && o.Vehicle == vehicle.Id
123                                      group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
124                                      .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
125      var destinations = deliveryOrdersByLocation.Keys.ToArray();
126      foreach (var o in orders) {
127        if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
128       
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         }
186
187        if (prio > bestPriority) {
188          bestPriority = prio;
189          best = o;
190        }
191      }
192
193      order = best != null ? best : orders.First();
194      priority = bestPriority;
195    }
196
197    private bool IsPickup(Order o, DynPDPProblemInstance instance) {
198      return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
199    }
200
201    private struct XY {
202      public double X { get; private set; }
203      public double Y { get; private set; }
204
205      public XY(double x, double y) : this() {
206        X = x;
207        Y = y;
208      }
209    }
210
211    private class XYEqComparer : EqualityComparer<XY> {
212
213      public override bool Equals(XY x, XY y) {
214        return x.X == y.X && x.Y == y.Y;
215      }
216
217      public override int GetHashCode(XY obj) {
218        return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
219      }
220    }
221  }
222}
Note: See TracBrowser for help on using the repository browser.