[8747] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
[8760] | 3 | using System.Diagnostics;
|
---|
[8747] | 4 | using System.Linq;
|
---|
| 5 | using HeuristicLab.Common;
|
---|
| 6 | using HeuristicLab.Core;
|
---|
[8760] | 7 | using HeuristicLab.Encodings.RealVectorEncoding;
|
---|
| 8 | using HeuristicLab.Parameters;
|
---|
[8747] | 9 | using HeuristicLab.PDPSimulation.DomainModel;
|
---|
[8760] | 10 | using HeuristicLab.PDPSimulation.Operators;
|
---|
[8747] | 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 |
|
---|
[8760] | 29 | public IValueLookupParameter<RealVector> WeightsParameter {
|
---|
| 30 | get { return (IValueLookupParameter<RealVector>)Parameters["Weights"]; }
|
---|
| 31 | }
|
---|
| 32 |
|
---|
[8747] | 33 | [StorableConstructor]
|
---|
| 34 | private PriorityDispatching(bool deserializing) : base(deserializing) { }
|
---|
| 35 | private PriorityDispatching(PriorityDispatching original, Cloner cloner) : base(original, cloner) { }
|
---|
| 36 | public PriorityDispatching() {
|
---|
[8760] | 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 | });
|
---|
[8747] | 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;
|
---|
[8760] | 59 | GetHighestPriorityOrder((DynPDPProblemInstance)instance.StaticInstance, vehicle, orders, out selectedOrder, out priority);
|
---|
[8747] | 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 |
|
---|
[8777] | 78 | foreach (var assignedOrder in GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting))
|
---|
| 79 | assignedOrder.AssignedVehicle = Guid.Empty;
|
---|
[8747] | 80 |
|
---|
| 81 | order.AssignedVehicle = bestVehicle.Id;
|
---|
| 82 | }
|
---|
| 83 | }
|
---|
| 84 | return true;
|
---|
| 85 | }
|
---|
| 86 |
|
---|
[8760] | 87 | private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
|
---|
[8777] | 88 | var weights = WeightsParameter.Value;
|
---|
[8760] | 89 | Order best = null;
|
---|
| 90 | double bestPriority = double.MinValue;
|
---|
| 91 | var pickupOrdersByLocation = (from o in orders
|
---|
| 92 | where IsPickup(o, instance)
|
---|
| 93 | group o by new { X = o.PickupXCoord, Y = o.PickupYCoord })
|
---|
| 94 | .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
|
---|
| 95 | var deliveryOrdersByLocation = (from o in orders
|
---|
| 96 | where !IsPickup(o, instance)
|
---|
| 97 | group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
|
---|
| 98 | .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();
|
---|
| 100 | foreach (var o in orders) {
|
---|
| 101 | if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
|
---|
| 102 |
|
---|
| 103 | var target = new XY(o.PickupXCoord, o.PickupYCoord);
|
---|
| 104 | if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
|
---|
[8747] | 105 |
|
---|
[8760] | 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();
|
---|
[8747] | 109 |
|
---|
[8760] | 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"];
|
---|
| 145 |
|
---|
| 146 | if (prio > bestPriority) {
|
---|
| 147 | bestPriority = prio;
|
---|
| 148 | best = o;
|
---|
[8747] | 149 | }
|
---|
| 150 | }
|
---|
| 151 |
|
---|
[8760] | 152 | order = best != null ? best : orders.First();
|
---|
| 153 | priority = bestPriority;
|
---|
| 154 | }
|
---|
[8747] | 155 |
|
---|
[8760] | 156 | private bool IsPickup(Order o, DynPDPProblemInstance instance) {
|
---|
| 157 | return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
|
---|
| 158 | }
|
---|
[8747] | 159 |
|
---|
[8760] | 160 | private struct XY {
|
---|
| 161 | public double X { get; private set; }
|
---|
| 162 | public double Y { get; private set; }
|
---|
[8747] | 163 |
|
---|
[8760] | 164 | public XY(double x, double y) : this() {
|
---|
| 165 | X = x;
|
---|
| 166 | Y = y;
|
---|
| 167 | }
|
---|
| 168 | }
|
---|
[8747] | 169 |
|
---|
[8760] | 170 | private class XYEqComparer : EqualityComparer<XY> {
|
---|
[8747] | 171 |
|
---|
[8760] | 172 | public override bool Equals(XY x, XY y) {
|
---|
| 173 | return x.X == y.X && x.Y == y.Y;
|
---|
[8747] | 174 | }
|
---|
| 175 |
|
---|
[8760] | 176 | public override int GetHashCode(XY obj) {
|
---|
| 177 | return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
|
---|
[8747] | 178 | }
|
---|
[8760] | 179 | }
|
---|
[8747] | 180 | }
|
---|
| 181 | }
|
---|