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,
|
---|
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 orders = waitingOrders.Concat(GetOrders().Where(x => x.OrderState == OrderState.PickedUp && x.AssignedVehicle == vehicle.Id));
|
---|
56 | if (orders.Any()) {
|
---|
57 | Order selectedOrder;
|
---|
58 | double priority;
|
---|
59 | GetHighestPriorityOrder((DynPDPProblemInstance)instance.StaticInstance, vehicle, orders, out selectedOrder, out priority);
|
---|
60 | tmp[vehicle] = Tuple.Create(selectedOrder, priority);
|
---|
61 | }
|
---|
62 | }
|
---|
63 | var assignment = tmp.GroupBy(x => x.Value.Item1, x => new { Vehicle = x.Key, Priority = x.Value.Item2 });
|
---|
64 | foreach (var a in assignment) {
|
---|
65 | var bestVehicle = a.MaxItems(x => x.Priority).Select(x => x.Vehicle).First();
|
---|
66 | var order = a.Key;
|
---|
67 |
|
---|
68 | MoveVehicleAction action;
|
---|
69 | if (order.OrderState == OrderState.Waiting) {
|
---|
70 | action = new MoveVehicleAction(bestVehicle.Id, order.PickupXCoord, order.PickupYCoord, VehicleAction.Pickup, order, scenario.AllowDiversion, scenario.DistanceMeasure);
|
---|
71 | } else {
|
---|
72 | action = new MoveVehicleAction(bestVehicle.Id, order.DeliveryXCoord, order.DeliveryYCoord, VehicleAction.Deliver, order, scenario.AllowDiversion, scenario.DistanceMeasure);
|
---|
73 | }
|
---|
74 | SetAction(action);
|
---|
75 | waitingVehicles.Remove(bestVehicle);
|
---|
76 | waitingOrders.Remove(order);
|
---|
77 |
|
---|
78 | Debug.Assert(!GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting).Any(), "An order has already been assigned to the vehicle");
|
---|
79 |
|
---|
80 | order.AssignedVehicle = bestVehicle.Id;
|
---|
81 | }
|
---|
82 | }
|
---|
83 | return true;
|
---|
84 | }
|
---|
85 |
|
---|
86 | private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
|
---|
87 | var weights = WeightsParameter.ActualValue;
|
---|
88 | Order best = null;
|
---|
89 | double bestPriority = double.MinValue;
|
---|
90 | var pickupOrdersByLocation = (from o in orders
|
---|
91 | where IsPickup(o, instance)
|
---|
92 | group o by new { X = o.PickupXCoord, Y = o.PickupYCoord })
|
---|
93 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
94 | var deliveryOrdersByLocation = (from o in orders
|
---|
95 | where !IsPickup(o, instance)
|
---|
96 | group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
|
---|
97 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
98 | var destinations = deliveryOrdersByLocation.Keys.ToArray();// vehicle.PickedUpOrders.Select(x => GetOrder(x)).Select(x => new XY(x.DeliveryXCoord, x.DeliveryYCoord)).ToArray();
|
---|
99 | foreach (var o in orders) {
|
---|
100 | if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
|
---|
101 |
|
---|
102 | var target = new XY(o.PickupXCoord, o.PickupYCoord);
|
---|
103 | if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
|
---|
104 |
|
---|
105 | var destinationDifference = destinations.Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
|
---|
106 | var courierDifference = GetVehicles().Where(x => x != vehicle).Select(x => new XY(x.TargetPositionX, x.TargetPositionY))
|
---|
107 | .Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
|
---|
108 |
|
---|
109 | var variables = new Dictionary<string, double>();
|
---|
110 | variables.Add("Distance", scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
|
---|
111 | variables.Add("EarliestTimeOfArrival", vehicle.ReadyTime + variables["Distance"]); // scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
|
---|
112 | variables.Add("DueDate", o.DeliveryDueTime - GetSimulationTime());
|
---|
113 | variables.Add("StartDate", IsPickup(o, instance) ? o.PickupReadyTime - GetSimulationTime() : 0);
|
---|
114 | variables.Add("PickupOrdersAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Count() : 0);
|
---|
115 | variables.Add("PickupOrderItemsAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Sum(x => x.Demand) : 0);
|
---|
116 | variables.Add("DeliveryOrdersAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Count() : 0);
|
---|
117 | variables.Add("DeliveryOrderItemsAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Sum(x => x.Demand) : 0);
|
---|
118 | variables.Add("AverageDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Average() : 0);
|
---|
119 | variables.Add("MinimumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Min() : 0);
|
---|
120 | variables.Add("MaximumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Max() : 0);
|
---|
121 | variables.Add("NumberOfOtherCouriersToTarget", GetVehicles().Count > 2 ? GetVehicles().Where(x => x != vehicle).Count(x => target.X == x.TargetPositionX && target.Y == x.TargetPositionY) : 0);
|
---|
122 | variables.Add("AverageDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Average() : 0);
|
---|
123 | variables.Add("MinimumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Min() : 0);
|
---|
124 | variables.Add("MaximumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Max() : 0);
|
---|
125 | variables.Add("DemandSize", o.Demand);
|
---|
126 |
|
---|
127 | var prio =
|
---|
128 | weights[0] * variables["DueDate"]
|
---|
129 | + weights[1] * variables["StartDate"]
|
---|
130 | + weights[2] * variables["PickupOrdersAtTarget"]
|
---|
131 | + weights[3] * variables["Distance"]
|
---|
132 | + weights[4] * variables["AverageDistanceToDestinations"]
|
---|
133 | + weights[5] * variables["MinimumDistanceToDestinations"]
|
---|
134 | + weights[6] * variables["MaximumDistanceToDestinations"]
|
---|
135 | + weights[7] * variables["NumberOfOtherCouriersToTarget"]
|
---|
136 | + weights[8] * variables["AverageDistanceToOtherCouriers"]
|
---|
137 | + weights[9] * variables["EarliestTimeOfArrival"]
|
---|
138 | + weights[10] * variables["DeliveryOrdersAtTarget"]
|
---|
139 | + weights[11] * variables["PickupOrderItemsAtTarget"]
|
---|
140 | + weights[12] * variables["DeliveryOrderItemsAtTarget"]
|
---|
141 | + weights[13] * variables["MinimumDistanceToOtherCouriers"]
|
---|
142 | + weights[14] * variables["MaximumDistanceToOtherCouriers"]
|
---|
143 | + weights[15] * variables["DemandSize"];
|
---|
144 |
|
---|
145 | if (prio > bestPriority) {
|
---|
146 | bestPriority = prio;
|
---|
147 | best = o;
|
---|
148 | }
|
---|
149 | }
|
---|
150 |
|
---|
151 | order = best != null ? best : orders.First();
|
---|
152 | priority = bestPriority;
|
---|
153 | }
|
---|
154 |
|
---|
155 | private bool IsPickup(Order o, DynPDPProblemInstance instance) {
|
---|
156 | return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
|
---|
157 | }
|
---|
158 |
|
---|
159 | private struct XY {
|
---|
160 | public double X { get; private set; }
|
---|
161 | public double Y { get; private set; }
|
---|
162 |
|
---|
163 | public XY(double x, double y) : this() {
|
---|
164 | X = x;
|
---|
165 | Y = y;
|
---|
166 | }
|
---|
167 | }
|
---|
168 |
|
---|
169 | private class XYEqComparer : EqualityComparer<XY> {
|
---|
170 |
|
---|
171 | public override bool Equals(XY x, XY y) {
|
---|
172 | return x.X == y.X && x.Y == y.Y;
|
---|
173 | }
|
---|
174 |
|
---|
175 | public override int GetHashCode(XY obj) {
|
---|
176 | return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
|
---|
177 | }
|
---|
178 | }
|
---|
179 | }
|
---|
180 | }
|
---|