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 abstract 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 |
|
---|
30 | [StorableConstructor]
|
---|
31 | protected PriorityDispatching(bool deserializing) : base(deserializing) { }
|
---|
32 | protected PriorityDispatching(PriorityDispatching original, Cloner cloner) : base(original, cloner) { }
|
---|
33 | protected PriorityDispatching() {
|
---|
34 | }
|
---|
35 |
|
---|
36 | protected override bool PerformOptimization(DynamicPDProblemInstance instance, ChangeInformation changeInformation) {
|
---|
37 | var waitingVehicles = GetVehicles().Where(x => IsIdle(x)).ToList();
|
---|
38 | var waitingOrders = GetOrders().Where(x => x.AssignedVehicle == Guid.Empty).ToList();
|
---|
39 |
|
---|
40 | while (waitingVehicles.Any() && (waitingOrders.Any()
|
---|
41 | || GetOrders().Any(x => x.OrderState == OrderState.PickedUp && waitingVehicles.Any(y => y.Id == x.AssignedVehicle)))) {
|
---|
42 | var tmp = new Dictionary<Vehicle, Tuple<Order, double>>();
|
---|
43 | foreach (var vehicle in waitingVehicles) {
|
---|
44 | var pickedupOrders = GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == vehicle.Id);
|
---|
45 | var orders = waitingOrders.Concat(pickedupOrders);
|
---|
46 | if (orders.Any()) {
|
---|
47 | Order selectedOrder;
|
---|
48 | double priority;
|
---|
49 | GetHighestPriorityOrder((DynPDPProblemInstance)instance.StaticInstance, vehicle, orders, out selectedOrder, out priority);
|
---|
50 | tmp[vehicle] = Tuple.Create(selectedOrder, priority);
|
---|
51 | }
|
---|
52 | }
|
---|
53 | var assignment = tmp.GroupBy(x => x.Value.Item1, x => new { Vehicle = x.Key, Priority = x.Value.Item2 });
|
---|
54 | foreach (var a in assignment) {
|
---|
55 | var bestVehicle = a.MaxItems(x => x.Priority).Select(x => x.Vehicle).First();
|
---|
56 | var order = a.Key;
|
---|
57 |
|
---|
58 | bool first = true;
|
---|
59 |
|
---|
60 | XY target;
|
---|
61 | MoveVehicleAction action;
|
---|
62 | if (order.OrderState == OrderState.Waiting) {
|
---|
63 | target = new XY(order.PickupXCoord, order.PickupYCoord);
|
---|
64 | action = new MoveVehicleAction(bestVehicle.Id, order.PickupXCoord, order.PickupYCoord, VehicleAction.Pickup, order, scenario.AllowDiversion, scenario.DistanceMeasure);
|
---|
65 | } else {
|
---|
66 | target = new XY(order.DeliveryXCoord, order.DeliveryYCoord);
|
---|
67 | action = new MoveVehicleAction(bestVehicle.Id, order.DeliveryXCoord, order.DeliveryYCoord, VehicleAction.Deliver, order, scenario.AllowDiversion, scenario.DistanceMeasure);
|
---|
68 | }
|
---|
69 | var pickedupOrders = GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == bestVehicle.Id);
|
---|
70 | var pickedupOrdersAtDestination = pickedupOrders.Where(o => o.DeliveryXCoord == target.X && o.DeliveryYCoord == target.Y);
|
---|
71 | List<MoveVehicleAction> deliveryActions = new List<MoveVehicleAction>();
|
---|
72 | foreach (var pickedupOrder in pickedupOrdersAtDestination) {
|
---|
73 | if (pickedupOrder != order) {
|
---|
74 | MoveVehicleAction deliveryAction = new MoveVehicleAction(bestVehicle.Id, pickedupOrder.DeliveryXCoord, pickedupOrder.DeliveryYCoord, VehicleAction.Deliver, pickedupOrder, scenario.AllowDiversion, scenario.DistanceMeasure);
|
---|
75 | if (first) {
|
---|
76 | SetAction(deliveryAction);
|
---|
77 | first = false;
|
---|
78 | } else {
|
---|
79 | AppendAction(deliveryAction);
|
---|
80 | }
|
---|
81 | waitingOrders.Remove(pickedupOrder);
|
---|
82 | }
|
---|
83 | }
|
---|
84 |
|
---|
85 | if (first) {
|
---|
86 | SetAction(action);
|
---|
87 | first = false;
|
---|
88 | } else {
|
---|
89 | AppendAction(action);
|
---|
90 | }
|
---|
91 | waitingVehicles.Remove(bestVehicle);
|
---|
92 | waitingOrders.Remove(order);
|
---|
93 |
|
---|
94 | foreach (var assignedOrder in GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting))
|
---|
95 | assignedOrder.AssignedVehicle = Guid.Empty;
|
---|
96 |
|
---|
97 | order.AssignedVehicle = bestVehicle.Id;
|
---|
98 | }
|
---|
99 | }
|
---|
100 | return true;
|
---|
101 | }
|
---|
102 |
|
---|
103 | protected abstract double CalculatePriority(IDictionary<string, double> variables);
|
---|
104 |
|
---|
105 | private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
|
---|
106 | Order best = null;
|
---|
107 | double bestPriority = double.MinValue;
|
---|
108 | var pickupOrdersByLocation = (from o in orders
|
---|
109 | where IsPickup(o, instance)
|
---|
110 | group o by new { X = o.PickupXCoord, Y = o.PickupYCoord })
|
---|
111 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
112 | var deliveryOrdersByLocation = (from o in orders
|
---|
113 | where !IsPickup(o, instance) && o.Vehicle == vehicle.Id
|
---|
114 | group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
|
---|
115 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
116 | var destinations = deliveryOrdersByLocation.Keys.ToArray();
|
---|
117 | foreach (var o in orders) {
|
---|
118 | if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
|
---|
119 |
|
---|
120 | double prio;
|
---|
121 | if (!IsPickup(o, instance) && vehicle.TargetPositionX == o.DeliveryXCoord && vehicle.TargetPositionY == o.DeliveryYCoord) {
|
---|
122 | prio = double.MaxValue;
|
---|
123 | } else {
|
---|
124 | var target = new XY(o.PickupXCoord, o.PickupYCoord);
|
---|
125 | if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
|
---|
126 |
|
---|
127 | var destinationDifference = destinations.Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
|
---|
128 | var courierDifference = GetVehicles().Where(x => x != vehicle).Select(x => new XY(x.TargetPositionX, x.TargetPositionY))
|
---|
129 | .Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
|
---|
130 |
|
---|
131 | var commonDestinations = orders.Where(x => !IsPickup(x, instance) && x.Vehicle == vehicle.Id &&
|
---|
132 | x.DeliveryXCoord == o.PickupXCoord &&
|
---|
133 | x.DeliveryYCoord == o.PickupYCoord);
|
---|
134 |
|
---|
135 | var variables = new Dictionary<string, double>();
|
---|
136 | variables.Add("Distance", scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
|
---|
137 | variables.Add("EarliestTimeOfArrival", vehicle.ReadyTime + variables["Distance"]);
|
---|
138 | variables.Add("DueDate", o.DeliveryDueTime - GetSimulationTime());
|
---|
139 | variables.Add("StartDate", IsPickup(o, instance) ? o.PickupReadyTime - GetSimulationTime() : 0);
|
---|
140 | variables.Add("PickupOrdersAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Count() : 0);
|
---|
141 | variables.Add("PickupOrderItemsAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Sum(x => x.Demand) : 0);
|
---|
142 | variables.Add("DeliveryOrdersAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Count() : 0);
|
---|
143 | variables.Add("DeliveryOrderItemsAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Sum(x => x.Demand) : 0);
|
---|
144 | variables.Add("AverageDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Average() : 0);
|
---|
145 | variables.Add("MinimumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Min() : 0);
|
---|
146 | variables.Add("MaximumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Max() : 0);
|
---|
147 | variables.Add("NumberOfOtherCouriersToTarget", GetVehicles().Count > 2 ? GetVehicles().Where(x => x != vehicle).Count(x => target.X == x.TargetPositionX && target.Y == x.TargetPositionY) : 0);
|
---|
148 | variables.Add("AverageDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Average() : 0);
|
---|
149 | variables.Add("MinimumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Min() : 0);
|
---|
150 | variables.Add("MaximumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Max() : 0);
|
---|
151 | variables.Add("DemandSize", o.Demand);
|
---|
152 | variables.Add("EDD", commonDestinations.Any() ? commonDestinations.Min(d => d.DeliveryDueTime
|
---|
153 | - scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, d.DeliveryXCoord, d.DeliveryYCoord)
|
---|
154 | - GetSimulationTime()) : 0);
|
---|
155 | variables.Add("LeadTime", o.PickupReadyTime - GetSimulationTime());
|
---|
156 |
|
---|
157 | prio = CalculatePriority(variables);
|
---|
158 | }
|
---|
159 |
|
---|
160 | if (prio > bestPriority) {
|
---|
161 | bestPriority = prio;
|
---|
162 | best = o;
|
---|
163 | }
|
---|
164 | }
|
---|
165 |
|
---|
166 | order = best != null ? best : orders.First();
|
---|
167 | priority = bestPriority;
|
---|
168 | }
|
---|
169 |
|
---|
170 | private bool IsPickup(Order o, DynPDPProblemInstance instance) {
|
---|
171 | return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
|
---|
172 | }
|
---|
173 |
|
---|
174 | private struct XY {
|
---|
175 | public double X { get; private set; }
|
---|
176 | public double Y { get; private set; }
|
---|
177 |
|
---|
178 | public XY(double x, double y) : this() {
|
---|
179 | X = x;
|
---|
180 | Y = y;
|
---|
181 | }
|
---|
182 | }
|
---|
183 |
|
---|
184 | private class XYEqComparer : EqualityComparer<XY> {
|
---|
185 |
|
---|
186 | public override bool Equals(XY x, XY y) {
|
---|
187 | return x.X == y.X && x.Y == y.Y;
|
---|
188 | }
|
---|
189 |
|
---|
190 | public override int GetHashCode(XY obj) {
|
---|
191 | return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
|
---|
192 | }
|
---|
193 | }
|
---|
194 | }
|
---|
195 | }
|
---|