Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8813


Ignore:
Timestamp:
10/16/12 14:56:46 (12 years ago)
Author:
svonolfe
Message:

Added earliest due time and nearest destination dispatching (#1955)

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

Legend:

Unmodified
Added
Removed
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/HeuristicLab.PDPSimulation-3.3.csproj

    r8809 r8813  
    136136    </Reference>
    137137    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4">
    138     <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
     138      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
    139139      <Private>False</Private>
    140140    </Reference>
     
    207207    <Compile Include="Optimizers\DynamicPDPOptimization.cs" />
    208208    <Compile Include="Optimizers\LocalUpdate\BestInsertion.cs" />
     209    <Compile Include="Optimizers\LocalUpdate\Dispatching.cs" />
     210    <Compile Include="Optimizers\LocalUpdate\EarliestDueTimeDispatching.cs" />
     211    <Compile Include="Optimizers\LocalUpdate\NearestDestinationDispatching.cs" />
    209212    <Compile Include="Optimizers\LocalUpdate\TreePriorityDispatching.cs" />
    210213    <Compile Include="Optimizers\LocalUpdate\LinearPriorityDispatching.cs" />
  • branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/LocalUpdate/PriorityDispatching.cs

    r8808 r8813  
    1414  [Item("PriorityDispatching", "")]
    1515  [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 
     16  public abstract class PriorityDispatching : Dispatching {
    3017    [StorableConstructor]
    3118    protected PriorityDispatching(bool deserializing) : base(deserializing) { }
     
    3421    }
    3522
    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 
    10323    protected abstract double CalculatePriority(IDictionary<string, double> variables);
    10424
    105     private void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
     25    protected override void GetHighestPriorityOrder(DynPDPProblemInstance instance, Vehicle vehicle, IEnumerable<Order> orders, out Order order, out double priority) {
    10626      Order best = null;
    10727      double bestPriority = double.MinValue;
     
    16787      priority = bestPriority;
    16888    }
    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     }
    19489  }
    19590}
Note: See TracChangeset for help on using the changeset viewer.