Changeset 8760


Ignore:
Timestamp:
10/08/12 14:24:15 (10 years ago)
Author:
abeham
Message:

#1955: Updated priority rule

Location:
branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/PriorityDispatching.cs

    r8747 r8760  
    11using System;
    22using System.Collections.Generic;
     3using System.Diagnostics;
    34using System.Linq;
    45using HeuristicLab.Common;
    56using HeuristicLab.Core;
     7using HeuristicLab.Encodings.RealVectorEncoding;
     8using HeuristicLab.Parameters;
    69using HeuristicLab.PDPSimulation.DomainModel;
     10using HeuristicLab.PDPSimulation.Operators;
    711using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    812
     
    2327    }
    2428
     29    public IValueLookupParameter<RealVector> WeightsParameter {
     30      get { return (IValueLookupParameter<RealVector>)Parameters["Weights"]; }
     31    }
     32
    2533    [StorableConstructor]
    2634    private PriorityDispatching(bool deserializing) : base(deserializing) { }
    2735    private PriorityDispatching(PriorityDispatching original, Cloner cloner) : base(original, cloner) { }
    2836    public PriorityDispatching() {
    29 
     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      });
    3041    }
    3142
     
    4657            Order selectedOrder;
    4758            double priority;
    48             GetHighestPriorityOrder(vehicle, orders, out selectedOrder, out priority);
     59            GetHighestPriorityOrder((DynPDPProblemInstance)instance.StaticInstance, vehicle, orders, out selectedOrder, out priority);
    4960            tmp[vehicle] = Tuple.Create(selectedOrder, priority);
    5061          }
     
    6576          waitingOrders.Remove(order);
    6677
    67           if (GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting).Any()) {
    68             throw new InvalidOperationException("An order has already been assigned to the vehicle");
    69             //can be removed after debugging
    70           }
     78          Debug.Assert(!GetOrders().Where(o => o.AssignedVehicle == bestVehicle.Id && o.OrderState == OrderState.Waiting).Any(), "An order has already been assigned to the vehicle");
    7179
    7280          order.AssignedVehicle = bestVehicle.Id;
     
    7684    }
    7785
    78     private void GetHighestPriorityOrder(Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
    79       var random = new System.Random();
    80       var o = orders.ToArray();
    81       order = o[random.Next(o.Length)];
    82       priority = random.NextDouble();
    83     }
     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);
    84104
    85     /*private void GetHighestPriorityOrder(Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
    86       var pdp = instance as DynPDPProblemInstance;
    87       if (pdp == null) throw new ArgumentException("instance is not of type DynPDPProblemInstance", "instance");
     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();
    88108
    89       int vehicles = pdp.Vehicles.Value;
    90       while (solution.Unrouted.Count > 0) {
    91         var diversion = new Dictionary<int, Dictionary<int, double>>(vehicles);
    92         foreach (var v in Enumerable.Range(0, vehicles)) diversion[v] = new Dictionary<int, double>();
    93         var estimatedTimeOfArrival = new Dictionary<int, Dictionary<int, double>>(vehicles);
    94         var earliestDueDate = new Dictionary<int, double>(solution.Unrouted.Count);
    95         var earliestStartTime = new Dictionary<int, double>(solution.Unrouted.Count);
    96         var numberOfWaitingOrders = new Dictionary<int, double>(solution.Unrouted.Count);
    97         var                                                                                                     
    98         foreach (var s in solution.Unrouted) {
    99          
     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;
    100148        }
    101149      }
    102150
     151      order = best != null ? best : orders.First();
     152      priority = bestPriority;
     153    }
    103154
    104       double FUTURE = 1e07;
    105       int locations = myEnvironment.servicePoints.length;
    106       // these are the dispatching rules that are calculated for each location to decide on the next destination
    107       double[] distance = new double[locations]; // distance from current position to location
    108       double[] estimatedTimeOfArrival = new double[locations];
    109       double[] earliestDueDate = new double[locations]; // difference to current time that a passenger needs to arrive which is currently carried
    110       double[] earliestStartTime = new double[locations]; // difference to current time when a waiting passenger requested pickup
    111       int[] numberOfWaitingOrders = new int[locations];
    112       int[] numberOfWaitingOrderItems = new int[locations];
    113       int[] numberOfDueOrders = new int[locations];
    114       int[] numberOfDueOrderItems = new int[locations];
    115       double[] averageDistanceToOtherDestinations = new double[locations]; // The average distance of a location to all the destinations that have to be visited
    116       double[] minDistanceToOtherDestinations = new double[locations]; // The min distance of a location to all the destinations that have to be visited
    117       double[] maxDistanceToOtherDestinations = new double[locations]; // The max distance of a location to all the destinations that have to be visited
    118       int[] numberOfCouriersWithThisDestination = new int[locations]; // How many other vehicles already go there
    119       double[] averageDistanceToOtherCouriers = new double[locations];
    120       double[] minDistanceToOtherCouriers = new double[locations];
    121       double[] maxDistanceToOtherCouriers = new double[locations];
     155    private bool IsPickup(Order o, DynPDPProblemInstance instance) {
     156      return instance.Demand[Instance.GetStops(o.Id).First()] > 0;
     157    }
    122158
    123       // calculate each dispatching rule
    124       for (int i = 0; i < locations; i++) {
    125         if (i != currentDestination) {
    126           ServicePoint servicePoint = myEnvironment.servicePoints[i];
     159    private struct XY {
     160      public double X { get; private set; }
     161      public double Y { get; private set; }
    127162
    128           distance[i] = myEnvironment.distances[i][currentDestination];
    129           estimatedTimeOfArrival[i] = distance[i] / myEnvironment.averageSpeed;
     163      public XY(double x, double y) : this() {
     164        X = x;
     165        Y = y;
     166      }
     167    }
    130168
    131           double earliestDue = FUTURE;
    132           double minDist = 1e07, maxDist = 0, distSum = 0.0;
    133           int ordersDue = 0, itemsDue = 0;
    134           for (int x = 0; x < currentOrders.size(); x++) {
    135             if (currentOrders.get(x).dropOffAtId == i) {
    136               ordersDue++;
    137               itemsDue += currentOrders.get(x).demandSize;
    138               if ((currentOrders.get(x).dueDate - now) < earliestDue) earliestDue = currentOrders.get(x).dueDate - now;
    139             }
    140             double d = myEnvironment.distances[i][currentOrders.get(x).dropOffAtId];
    141             distSum += d;
    142             if (d < minDist) minDist = d;
    143             if (d > maxDist) maxDist = d;
    144           }
    145           earliestDueDate[i] = earliestDue;
    146           numberOfDueOrders[i] = ordersDue;
    147           numberOfDueOrderItems[i] = itemsDue;
    148           minDistanceToOtherDestinations[i] = ((currentOrders.size() == 0) ? (0) : (minDist));
    149           maxDistanceToOtherDestinations[i] = ((currentOrders.size() == 0) ? (0) : (maxDist));
    150           averageDistanceToOtherDestinations[i] = ((currentOrders.size() == 0) ? (0) : (distSum / (double)currentOrders.size()));
     169    private class XYEqComparer : EqualityComparer<XY> {
    151170
    152           numberOfWaitingOrders[i] = servicePoint.orders.size();
    153           double earliestStart = FUTURE;
    154           int items = 0;
    155           for (int k = 0; k < numberOfWaitingOrders[i]; k++) {
    156             if ((servicePoint.orders.get(k).startTime - now) < earliestStart) earliestStart = servicePoint.orders.get(k).startTime - now;
    157             items += servicePoint.orders.get(k).demandSize;
    158           }
    159           numberOfWaitingOrderItems[i] = items;
    160           earliestStartTime[i] = earliestStart;
    161           numberOfCouriersWithThisDestination[i] = 0;
    162           minDist = 1e07; maxDist = 0; distSum = 0.0;
    163           for (int m = 0; m < myEnvironment.agents.size(); m++) {
    164             CourierAgent agent = myEnvironment.agents.get(m);
    165             if (agent != this) {
    166               if (agent.nextDestination == i) numberOfCouriersWithThisDestination[i]++;
    167               double d = myEnvironment.distances[i][agent.nextDestination];
    168               distSum += d;
    169               if (minDist > d) minDist = d;
    170               if (maxDist < d) maxDist = d;
    171             }
    172           }
    173           minDistanceToOtherCouriers[i] = minDist;
    174           maxDistanceToOtherCouriers[i] = maxDist;
    175           averageDistanceToOtherCouriers[i] = distSum / (double)myEnvironment.agents.size();
    176         }
     171      public override bool Equals(XY x, XY y) {
     172        return x.X == y.X && x.Y == y.Y;
    177173      }
    178174
    179       double[] priorityList = new double[locations];
    180       for (int i = 0; i < locations; i++) {
    181         if (i != currentDestination) {
    182           priorityList[i] = DIST * distance[i]
    183                           + ETA * estimatedTimeOfArrival[i]
    184                   + EDD * earliestDueDate[i]
    185                   + EST * earliestStartTime[i]
    186                   + NWO * numberOfWaitingOrders[i]
    187                   + NDO * numberOfDueOrders[i]
    188                   + NWOI * numberOfWaitingOrderItems[i]
    189                   + NDOI * numberOfDueOrderItems[i]
    190                   + ADD * averageDistanceToOtherDestinations[i]
    191                   + MiDD * minDistanceToOtherDestinations[i]
    192                   + MaDD * maxDistanceToOtherDestinations[i]
    193                   + NCD * numberOfCouriersWithThisDestination[i]
    194                   + ADC * averageDistanceToOtherCouriers[i]
    195                   + MiDC * minDistanceToOtherCouriers[i]
    196                   + MaDC * maxDistanceToOtherCouriers[i];
    197         } else priorityList[i] = Double.MAX_VALUE;
     175      public override int GetHashCode(XY obj) {
     176        return obj.X.GetHashCode() ^ obj.Y.GetHashCode();
    198177      }
    199       double minPrio = priorityList[0];
    200       int minPrioIdx = 0;
    201       //System.out.print(minPrio);
    202       for (int i = 1; i < locations; i++) {
    203         //System.out.print(", " + priorityList[i]);
    204         if (priorityList[i] < minPrio) {
    205           minPrio = priorityList[i];
    206           minPrioIdx = i;
    207         }
    208       }
    209       //System.out.println();
    210       //System.out.println("Picked " + minPrioIdx);
    211 
    212       nextDestination = minPrioIdx;
    213     }*/
     178    }
    214179  }
    215180}
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Plugin.cs.frame

    r8670 r8760  
    3838  [PluginDependency("HeuristicLab.Data", "3.3")]
    3939  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
     40  [PluginDependency("HeuristicLab.Encodings.RealVectorEncoding", "3.3")]
    4041  [PluginDependency("HeuristicLab.Operators", "3.3")]
    4142  [PluginDependency("HeuristicLab.Optimization", "3.3")]
Note: See TracChangeset for help on using the changeset viewer.