1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Diagnostics;
|
---|
4 | using System.Linq;
|
---|
5 | using HeuristicLab.Common;
|
---|
6 | using HeuristicLab.Core;
|
---|
7 | using HeuristicLab.Encodings.RealVectorEncoding;
|
---|
8 | using HeuristicLab.Parameters;
|
---|
9 | using HeuristicLab.PDPSimulation.DomainModel;
|
---|
10 | using HeuristicLab.PDPSimulation.Operators;
|
---|
11 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
12 |
|
---|
13 | namespace 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 | waitingOrders.Remove(pickedupOrder);
|
---|
93 | }
|
---|
94 | }
|
---|
95 |
|
---|
96 | if (first) {
|
---|
97 | SetAction(action);
|
---|
98 | first = false;
|
---|
99 | } else {
|
---|
100 | AppendAction(action);
|
---|
101 | }
|
---|
102 | waitingVehicles.Remove(bestVehicle);
|
---|
103 | waitingOrders.Remove(order);
|
---|
104 |
|
---|
105 | foreach (var assignedOrder in GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting))
|
---|
106 | assignedOrder.AssignedVehicle = Guid.Empty;
|
---|
107 |
|
---|
108 | order.AssignedVehicle = bestVehicle.Id;
|
---|
109 | }
|
---|
110 | }
|
---|
111 | return true;
|
---|
112 | }
|
---|
113 |
|
---|
114 | private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
|
---|
115 | var weights = WeightsParameter.Value;
|
---|
116 | Order best = null;
|
---|
117 | double bestPriority = double.MinValue;
|
---|
118 | var pickupOrdersByLocation = (from o in orders
|
---|
119 | where IsPickup(o, instance)
|
---|
120 | group o by new { X = o.PickupXCoord, Y = o.PickupYCoord })
|
---|
121 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
122 | var deliveryOrdersByLocation = (from o in orders
|
---|
123 | where !IsPickup(o, instance) && o.Vehicle == vehicle.Id
|
---|
124 | group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
|
---|
125 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
126 | var destinations = deliveryOrdersByLocation.Keys.ToArray();
|
---|
127 | foreach (var o in orders) {
|
---|
128 | if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
|
---|
129 |
|
---|
130 | double prio;
|
---|
131 | if (!IsPickup(o, instance) && vehicle.TargetPositionX == o.DeliveryXCoord && vehicle.TargetPositionY == o.DeliveryYCoord) {
|
---|
132 | prio = double.MaxValue;
|
---|
133 | } else {
|
---|
134 | var target = new XY(o.PickupXCoord, o.PickupYCoord);
|
---|
135 | if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
|
---|
136 |
|
---|
137 | var destinationDifference = destinations.Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
|
---|
138 | var courierDifference = GetVehicles().Where(x => x != vehicle).Select(x => new XY(x.TargetPositionX, x.TargetPositionY))
|
---|
139 | .Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
|
---|
140 |
|
---|
141 | var commonDestinations = orders.Where(x => !IsPickup(x, instance) && x.Vehicle == vehicle.Id &&
|
---|
142 | x.DeliveryXCoord == o.PickupXCoord &&
|
---|
143 | x.DeliveryYCoord == o.PickupYCoord);
|
---|
144 |
|
---|
145 | var variables = new Dictionary<string, double>();
|
---|
146 | variables.Add("Distance", scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
|
---|
147 | variables.Add("EarliestTimeOfArrival", vehicle.ReadyTime + variables["Distance"]);
|
---|
148 | variables.Add("DueDate", o.DeliveryDueTime - GetSimulationTime());
|
---|
149 | variables.Add("StartDate", IsPickup(o, instance) ? o.PickupReadyTime - GetSimulationTime() : 0);
|
---|
150 | variables.Add("PickupOrdersAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Count() : 0);
|
---|
151 | variables.Add("PickupOrderItemsAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Sum(x => x.Demand) : 0);
|
---|
152 | variables.Add("DeliveryOrdersAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Count() : 0);
|
---|
153 | variables.Add("DeliveryOrderItemsAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Sum(x => x.Demand) : 0);
|
---|
154 | variables.Add("AverageDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Average() : 0);
|
---|
155 | variables.Add("MinimumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Min() : 0);
|
---|
156 | variables.Add("MaximumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Max() : 0);
|
---|
157 | variables.Add("NumberOfOtherCouriersToTarget", GetVehicles().Count > 2 ? GetVehicles().Where(x => x != vehicle).Count(x => target.X == x.TargetPositionX && target.Y == x.TargetPositionY) : 0);
|
---|
158 | variables.Add("AverageDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Average() : 0);
|
---|
159 | variables.Add("MinimumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Min() : 0);
|
---|
160 | variables.Add("MaximumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Max() : 0);
|
---|
161 | variables.Add("DemandSize", o.Demand);
|
---|
162 | variables.Add("EDD", commonDestinations.Any() ? commonDestinations.Min(d => d.DeliveryDueTime
|
---|
163 | - scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, d.DeliveryXCoord, d.DeliveryYCoord)
|
---|
164 | - GetSimulationTime()) : 0);
|
---|
165 | variables.Add("LeadTime", o.PickupReadyTime - GetSimulationTime());
|
---|
166 |
|
---|
167 | prio =
|
---|
168 | weights[0] * variables["DueDate"]
|
---|
169 | + weights[1] * variables["StartDate"]
|
---|
170 | + weights[2] * variables["PickupOrdersAtTarget"]
|
---|
171 | + weights[3] * variables["Distance"]
|
---|
172 | + weights[4] * variables["AverageDistanceToDestinations"]
|
---|
173 | + weights[5] * variables["MinimumDistanceToDestinations"]
|
---|
174 | + weights[6] * variables["MaximumDistanceToDestinations"]
|
---|
175 | + weights[7] * variables["NumberOfOtherCouriersToTarget"]
|
---|
176 | + weights[8] * variables["AverageDistanceToOtherCouriers"]
|
---|
177 | + weights[9] * variables["EarliestTimeOfArrival"]
|
---|
178 | + weights[10] * variables["DeliveryOrdersAtTarget"]
|
---|
179 | + weights[11] * variables["PickupOrderItemsAtTarget"]
|
---|
180 | + weights[12] * variables["DeliveryOrderItemsAtTarget"]
|
---|
181 | + weights[13] * variables["MinimumDistanceToOtherCouriers"]
|
---|
182 | + weights[14] * variables["MaximumDistanceToOtherCouriers"]
|
---|
183 | + weights[15] * variables["DemandSize"]
|
---|
184 | + weights[16] * variables["EDD"]
|
---|
185 | + weights[17] * variables["LeadTime"];
|
---|
186 | }
|
---|
187 |
|
---|
188 | if (prio > bestPriority) {
|
---|
189 | bestPriority = prio;
|
---|
190 | best = o;
|
---|
191 | }
|
---|
192 | }
|
---|
193 |
|
---|
194 | order = best != null ? best : orders.First();
|
---|
195 | priority = bestPriority;
|
---|
196 | }
|
---|
197 |
|
---|
198 | private bool IsPickup(Order o, DynPDPProblemInstance instance) {
|
---|
199 | return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
|
---|
200 | }
|
---|
201 |
|
---|
202 | private struct XY {
|
---|
203 | public double X { get; private set; }
|
---|
204 | public double Y { get; private set; }
|
---|
205 |
|
---|
206 | public XY(double x, double y) : this() {
|
---|
207 | X = x;
|
---|
208 | Y = y;
|
---|
209 | }
|
---|
210 | }
|
---|
211 |
|
---|
212 | private class XYEqComparer : EqualityComparer<XY> {
|
---|
213 |
|
---|
214 | public override bool Equals(XY x, XY y) {
|
---|
215 | return x.X == y.X && x.Y == y.Y;
|
---|
216 | }
|
---|
217 |
|
---|
218 | public override int GetHashCode(XY obj) {
|
---|
219 | return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
|
---|
220 | }
|
---|
221 | }
|
---|
222 | }
|
---|
223 | }
|
---|