Changeset 8760 for branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers

Timestamp:

10/08/12 14:24:15 (12 years ago)

Author:

abeham

Message:

#1955: Updated priority rule

File:

• branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/PriorityDispatching.cs (modified) (5 diffs)

branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/PriorityDispatching.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.RealVectorEncoding;
+using HeuristicLab.Parameters;
 using HeuristicLab.PDPSimulation.DomainModel;
+using HeuristicLab.PDPSimulation.Operators;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -23 +27 @@
     }
 
+    public IValueLookupParameter<RealVector> WeightsParameter {
+      get { return (IValueLookupParameter<RealVector>)Parameters["Weights"]; }
+    }
+
     [StorableConstructor]
     private PriorityDispatching(bool deserializing) : base(deserializing) { }
     private PriorityDispatching(PriorityDispatching original, Cloner cloner) : base(original, cloner) { }
     public PriorityDispatching() {
-
+      Parameters.Add(new ValueLookupParameter<RealVector>("Weights", "The weights for the individual priorities."));
+      WeightsParameter.Value = new RealVector(new double[] {
+         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,
+      });
     }
 
@@ -46 +57 @@
             Order selectedOrder;
             double priority;
-            GetHighestPriorityOrder(vehicle, orders, out selectedOrder, out priority);
+            GetHighestPriorityOrder((DynPDPProblemInstance)instance.StaticInstance, vehicle, orders, out selectedOrder, out priority);
             tmp[vehicle] = Tuple.Create(selectedOrder, priority);
           }
@@ -65 +76 @@
           waitingOrders.Remove(order);
 
-          if (GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting).Any()) {
-            throw new InvalidOperationException("An order has already been assigned to the vehicle");
-            //can be removed after debugging
-          }
+          Debug.Assert(!GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting).Any(), "An order has already been assigned to the vehicle");
 
           order.AssignedVehicle = bestVehicle.Id;
@@ -76 +84 @@
     }
 
-    private void GetHighestPriorityOrder(Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
-      var random = new System.Random();
-      var o = orders.ToArray();
-      order = o[random.Next(o.Length)];
-      priority = random.NextDouble();
-    }
+    private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
+      var weights = WeightsParameter.ActualValue;
+      Order best = null;
+      double bestPriority = double.MinValue;
+      var pickupOrdersByLocation = (from o in orders
+                                   where IsPickup(o, instance)
+                                   group o by new { X = o.PickupXCoord, Y = o.PickupYCoord })
+                                   .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
+      var deliveryOrdersByLocation = (from o in orders
+                                      where !IsPickup(o, instance)
+                                      group o by new { X = o.DeliveryXCoord, Y = o.DeliveryYCoord })
+                                      .ToDictionary(x => new XY(x.Key.X, x.Key.Y), y => y.ToArray(), new XYEqComparer());
+      var destinations = deliveryOrdersByLocation.Keys.ToArray();// vehicle.PickedUpOrders.Select(x => GetOrder(x)).Select(x => new XY(x.DeliveryXCoord, x.DeliveryYCoord)).ToArray();
+      foreach (var o in orders) {
+        if (IsPickup(o, instance) && o.Demand > vehicle.Capacity) continue;
+        
+        var target = new XY(o.PickupXCoord, o.PickupYCoord);
+        if (!IsPickup(o, instance)) target = new XY(o.DeliveryXCoord, o.DeliveryYCoord);
 
-    /*private void GetHighestPriorityOrder(Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
-      var pdp = instance as DynPDPProblemInstance;
-      if (pdp == null) throw new ArgumentException("instance is not of type DynPDPProblemInstance", "instance");
+        var destinationDifference = destinations.Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
+        var courierDifference = GetVehicles().Where(x => x != vehicle).Select(x => new XY(x.TargetPositionX, x.TargetPositionY))
+          .Select(x => scenario.DistanceMeasure.GetDistance(target.X, target.Y, x.X, x.Y)).ToArray();
 
-      int vehicles = pdp.Vehicles.Value;
-      while (solution.Unrouted.Count > 0) {
-        var diversion = new Dictionary<int, Dictionary<int, double>>(vehicles);
-        foreach (var v in Enumerable.Range(0, vehicles)) diversion[v] = new Dictionary<int, double>();
-        var estimatedTimeOfArrival = new Dictionary<int, Dictionary<int, double>>(vehicles);
-        var earliestDueDate = new Dictionary<int, double>(solution.Unrouted.Count);
-        var earliestStartTime = new Dictionary<int, double>(solution.Unrouted.Count);
-        var numberOfWaitingOrders = new Dictionary<int, double>(solution.Unrouted.Count);
-        var                                                                                                      
-        foreach (var s in solution.Unrouted) {
-          
+        var variables = new Dictionary<string, double>();
+        variables.Add("Distance", scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
+        variables.Add("EarliestTimeOfArrival", vehicle.ReadyTime + variables["Distance"]); // scenario.DistanceMeasure.GetDistance(vehicle.TargetPositionX, vehicle.TargetPositionY, target.X, target.Y));
+        variables.Add("DueDate", o.DeliveryDueTime - GetSimulationTime());
+        variables.Add("StartDate", IsPickup(o, instance) ? o.PickupReadyTime - GetSimulationTime() : 0);
+        variables.Add("PickupOrdersAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Count() : 0);
+        variables.Add("PickupOrderItemsAtTarget", pickupOrdersByLocation.ContainsKey(target) ? pickupOrdersByLocation[target].Sum(x => x.Demand) : 0);
+        variables.Add("DeliveryOrdersAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Count() : 0);
+        variables.Add("DeliveryOrderItemsAtTarget", deliveryOrdersByLocation.ContainsKey(target) ? deliveryOrdersByLocation[target].Sum(x => x.Demand) : 0);
+        variables.Add("AverageDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Average() : 0);
+        variables.Add("MinimumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Min() : 0);
+        variables.Add("MaximumDistanceToDestinations", destinationDifference.Any() ? destinationDifference.Max() : 0);
+        variables.Add("NumberOfOtherCouriersToTarget", GetVehicles().Count > 2 ? GetVehicles().Where(x => x != vehicle).Count(x => target.X == x.TargetPositionX && target.Y == x.TargetPositionY) : 0);
+        variables.Add("AverageDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Average() : 0);
+        variables.Add("MinimumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Min() : 0);
+        variables.Add("MaximumDistanceToOtherCouriers", courierDifference.Any() ? courierDifference.Max() : 0);
+        variables.Add("DemandSize", o.Demand);
+
+        var prio =
+            weights[0] * variables["DueDate"]
+          + weights[1] * variables["StartDate"]
+          + weights[2] * variables["PickupOrdersAtTarget"]
+          + weights[3] * variables["Distance"]
+          + weights[4] * variables["AverageDistanceToDestinations"]
+          + weights[5] * variables["MinimumDistanceToDestinations"]
+          + weights[6] * variables["MaximumDistanceToDestinations"]
+          + weights[7] * variables["NumberOfOtherCouriersToTarget"]
+          + weights[8] * variables["AverageDistanceToOtherCouriers"]
+          + weights[9] * variables["EarliestTimeOfArrival"]
+          + weights[10] * variables["DeliveryOrdersAtTarget"]
+          + weights[11] * variables["PickupOrderItemsAtTarget"]
+          + weights[12] * variables["DeliveryOrderItemsAtTarget"]
+          + weights[13] * variables["MinimumDistanceToOtherCouriers"]
+          + weights[14] * variables["MaximumDistanceToOtherCouriers"]
+          + weights[15] * variables["DemandSize"];
+
+        if (prio > bestPriority) {
+          bestPriority = prio;
+          best = o;
         }
       }
 
+      order = best != null ? best : orders.First();
+      priority = bestPriority;
+    }
 
-      double FUTURE = 1e07;
-      int locations = myEnvironment.servicePoints.length;
-      // these are the dispatching rules that are calculated for each location to decide on the next destination
-      double[] distance = new double[locations]; // distance from current position to location
-      double[] estimatedTimeOfArrival = new double[locations];
-      double[] earliestDueDate = new double[locations]; // difference to current time that a passenger needs to arrive which is currently carried
-      double[] earliestStartTime = new double[locations]; // difference to current time when a waiting passenger requested pickup
-      int[] numberOfWaitingOrders = new int[locations];
-      int[] numberOfWaitingOrderItems = new int[locations];
-      int[] numberOfDueOrders = new int[locations];
-      int[] numberOfDueOrderItems = new int[locations];
-      double[] averageDistanceToOtherDestinations = new double[locations]; // The average distance of a location to all the destinations that have to be visited
-      double[] minDistanceToOtherDestinations = new double[locations]; // The min distance of a location to all the destinations that have to be visited
-      double[] maxDistanceToOtherDestinations = new double[locations]; // The max distance of a location to all the destinations that have to be visited
-      int[] numberOfCouriersWithThisDestination = new int[locations]; // How many other vehicles already go there
-      double[] averageDistanceToOtherCouriers = new double[locations];
-      double[] minDistanceToOtherCouriers = new double[locations];
-      double[] maxDistanceToOtherCouriers = new double[locations];
+    private bool IsPickup(Order o, DynPDPProblemInstance instance) {
+      return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
+    }
 
-      // calculate each dispatching rule
-      for (int i = 0; i < locations; i++) {
-        if (i != currentDestination) {
-          ServicePoint servicePoint = myEnvironment.servicePoints[i];
+    private struct XY {
+      public double X { get; private set; }
+      public double Y { get; private set; }
 
-          distance[i] = myEnvironment.distances[i][currentDestination];
-          estimatedTimeOfArrival[i] = distance[i] / myEnvironment.averageSpeed;
+      public XY(double x, double y) : this() {
+        X = x;
+        Y = y;
+      }
+    }
 
-          double earliestDue = FUTURE;
-          double minDist = 1e07, maxDist = 0, distSum = 0.0;
-          int ordersDue = 0, itemsDue = 0;
-          for (int x = 0; x < currentOrders.size(); x++) {
-            if (currentOrders.get(x).dropOffAtId == i) {
-              ordersDue++;
-              itemsDue += currentOrders.get(x).demandSize;
-              if ((currentOrders.get(x).dueDate - now) < earliestDue) earliestDue = currentOrders.get(x).dueDate - now;
-            }
-            double d = myEnvironment.distances[i][currentOrders.get(x).dropOffAtId];
-            distSum += d;
-            if (d < minDist) minDist = d;
-            if (d > maxDist) maxDist = d;
-          }
-          earliestDueDate[i] = earliestDue;
-          numberOfDueOrders[i] = ordersDue;
-          numberOfDueOrderItems[i] = itemsDue;
-          minDistanceToOtherDestinations[i] = ((currentOrders.size() == 0) ? (0) : (minDist));
-          maxDistanceToOtherDestinations[i] = ((currentOrders.size() == 0) ? (0) : (maxDist));
-          averageDistanceToOtherDestinations[i] = ((currentOrders.size() == 0) ? (0) : (distSum / (double)currentOrders.size()));
+    private class XYEqComparer : EqualityComparer<XY> {
 
-          numberOfWaitingOrders[i] = servicePoint.orders.size();
-          double earliestStart = FUTURE;
-          int items = 0;
-          for (int k = 0; k < numberOfWaitingOrders[i]; k++) {
-            if ((servicePoint.orders.get(k).startTime - now) < earliestStart) earliestStart = servicePoint.orders.get(k).startTime - now;
-            items += servicePoint.orders.get(k).demandSize;
-          }
-          numberOfWaitingOrderItems[i] = items;
-          earliestStartTime[i] = earliestStart;
-          numberOfCouriersWithThisDestination[i] = 0;
-          minDist = 1e07; maxDist = 0; distSum = 0.0;
-          for (int m = 0; m < myEnvironment.agents.size(); m++) {
-            CourierAgent agent = myEnvironment.agents.get(m);
-            if (agent != this) {
-              if (agent.nextDestination == i) numberOfCouriersWithThisDestination[i]++;
-              double d = myEnvironment.distances[i][agent.nextDestination];
-              distSum += d;
-              if (minDist > d) minDist = d;
-              if (maxDist < d) maxDist = d;
-            }
-          }
-          minDistanceToOtherCouriers[i] = minDist;
-          maxDistanceToOtherCouriers[i] = maxDist;
-          averageDistanceToOtherCouriers[i] = distSum / (double)myEnvironment.agents.size();
-        }
+      public override bool Equals(XY x, XY y) {
+        return x.X == y.X && x.Y == y.Y;
       }
 
-      double[] priorityList = new double[locations];
-      for (int i = 0; i < locations; i++) {
-        if (i != currentDestination) {
-          priorityList[i] = DIST * distance[i]
-                          + ETA * estimatedTimeOfArrival[i]
-                  + EDD * earliestDueDate[i]
-                  + EST * earliestStartTime[i]
-                  + NWO * numberOfWaitingOrders[i]
-                  + NDO * numberOfDueOrders[i]
-                  + NWOI * numberOfWaitingOrderItems[i]
-                  + NDOI * numberOfDueOrderItems[i]
-                  + ADD * averageDistanceToOtherDestinations[i]
-                  + MiDD * minDistanceToOtherDestinations[i]
-                  + MaDD * maxDistanceToOtherDestinations[i]
-                  + NCD * numberOfCouriersWithThisDestination[i]
-                  + ADC * averageDistanceToOtherCouriers[i]
-                  + MiDC * minDistanceToOtherCouriers[i]
-                  + MaDC * maxDistanceToOtherCouriers[i];
-        } else priorityList[i] = Double.MAX_VALUE;
+      public override int GetHashCode(XY obj) {
+        return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
       }
-      double minPrio = priorityList[0];
-      int minPrioIdx = 0;
-      //System.out.print(minPrio);
-      for (int i = 1; i < locations; i++) {
-        //System.out.print(", " + priorityList[i]);
-        if (priorityList[i] < minPrio) {
-          minPrio = priorityList[i];
-          minPrioIdx = i;
-        }
-      }
-      //System.out.println();
-      //System.out.println("Picked " + minPrioIdx);
-
-      nextDestination = minPrioIdx;
-    }*/
+    }
   }
 }