Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Optimizers/DynamicPDProblemInstance.cs @ 8671

Last change on this file since 8671 was 8671, checked in by svonolfe, 12 years ago

Removed operators that will not be included in the first version of the addon (#1955)

File size: 19.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Core;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Common;
29using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
30using HeuristicLab.Problems.VehicleRouting.Interfaces;
31using HeuristicLab.PDPSimulation.DomainModel;
32using HeuristicLab.Data;
33using HeuristicLab.PDPSimulation.Operators;
34using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
35using HeuristicLab.Problems.VehicleRouting;
36using HeuristicLab.PDPSimulation.DistanceMeasures;
37using HeuristicLab.Optimization;
38
39namespace HeuristicLab.PDPSimulation {
40  [Item("DynamicPDProblemInstance", "A dynamic PD instance.")]
41  [StorableClass]
42  public class DynamicPDProblemInstance: Item {
43    [Storable]
44    private List<DynPDPProblemInstance> instances;
45
46    [Storable]
47    private HashSet<PotvinEncoding> solutions;
48
49    [Storable]
50    private List<Item> tabuAttributes;
51
52    [Storable]
53    private Dictionary<int, Guid> vehicleAssignment;
54
55    [Storable]
56    private Dictionary<int, Guid> orderAssignment;
57
58    [Storable]
59    private double timeDelta;
60
61    [Storable]
62    private bool initialized;
63
64    public bool Initialized {
65      get { return initialized; }
66    }
67
68    public List<IVRPProblemInstance> StaticInstances {
69      get {
70        List<IVRPProblemInstance> result = new List<IVRPProblemInstance>();
71
72        foreach (DynPDPProblemInstance instance in instances)
73          result.Add(instance);
74
75        return result;
76      }
77    }
78
79    public IVRPProblemInstance StaticInstance {
80      get {
81        return instances[0];
82      }
83    }
84
85    public HashSet<PotvinEncoding> Solutions {
86      get { return solutions;  }
87    }
88
89    public List<Item> TabuAttributes {
90      get { return tabuAttributes; }
91    }
92
93    public void SetInstanceCount(int count) {
94      if (count > 0) {
95        if (instances.Count > count)
96          instances.RemoveRange(0, instances.Count - count);
97        else
98          while(instances.Count < count)
99            instances.Add(instances[0].ShallowClone());
100      }
101    }
102
103    public DynamicPDProblemInstance(PickupDeliveryScenario scenario, ResultCollection results): base() {
104      vehicleAssignment = new Dictionary<int, Guid>();
105      orderAssignment = new Dictionary<int, Guid>();
106      solutions = new HashSet<PotvinEncoding>();
107      tabuAttributes = new List<Item>();
108      timeDelta = 0;
109      initialized = false;
110
111      instances = new List<DynPDPProblemInstance>();
112      instances.Add(new DynPDPProblemInstance(scenario, results));
113    }
114
115    [StorableConstructor]
116    private DynamicPDProblemInstance(bool deserializing) : base(deserializing) {
117    }
118    private DynamicPDProblemInstance(DynamicPDProblemInstance original, Cloner cloner)
119      : base(original, cloner) {
120      instances = new List<DynPDPProblemInstance>();
121      foreach (DynPDPProblemInstance instance in original.instances)
122        instances.Add(cloner.Clone<DynPDPProblemInstance>(instance));
123
124      vehicleAssignment = new Dictionary<int, Guid>();
125      foreach (int key in original.vehicleAssignment.Keys)
126        vehicleAssignment.Add(key, original.vehicleAssignment[key]);
127
128      orderAssignment = new Dictionary<int, Guid>();
129      foreach (int key in original.orderAssignment.Keys)
130        orderAssignment.Add(key, original.orderAssignment[key]);
131
132      solutions = new HashSet<PotvinEncoding>();
133      foreach (PotvinEncoding solution in original.solutions)
134        solutions.Add(cloner.Clone<PotvinEncoding>(solution));
135     
136      tabuAttributes = new List<Item>();
137      foreach (Item tabuAttribute in original.tabuAttributes)
138        tabuAttributes.Add(cloner.Clone<Item>(tabuAttribute));
139
140      timeDelta = original.timeDelta;
141      initialized = original.initialized;
142    }
143    public override IDeepCloneable Clone(Cloner cloner) {
144      return new DynamicPDProblemInstance(this, cloner);
145    }
146
147    public void SetCurrentPlan(PotvinEncoding plan) {
148      foreach (DynPDPProblemInstance instance in instances) {
149        if (instance.CurrentPlan != null)
150          solutions.Remove(instance.CurrentPlan);
151
152        instance.CurrentPlan = PotvinEncoding.ConvertFrom(plan, instance);
153        solutions.Add(instance.CurrentPlan);
154      }
155    }
156
157    public Guid GetOrder(int stop) {
158      return orderAssignment[stop - 1];
159    }
160
161    public List<int> GetStops(Guid order) {
162      return (from a in orderAssignment where a.Value == order select a.Key).OrderBy(s => s).ToList();
163    }
164
165    public Guid GetVehicle(int index) {
166      return vehicleAssignment[index];
167    }
168
169    public void UpdateTime(double delta) {
170      foreach (DynPDPProblemInstance instance in instances) {
171        for (int i = 0; i < instance.DueTime.Length; i++) {
172          instance.DueTime[i] = Math.Max(0, instance.DueTime[i] - delta);
173          instance.ReadyTime[i] = Math.Max(0, instance.ReadyTime[i] - delta);
174        }
175      }
176
177      timeDelta += delta;
178    }
179
180    public void AddVehicle(Vehicle vehicle) {
181      throw new NotImplementedException();
182    }
183
184    private void AddOrder(DynPDPProblemInstance instance, Order order, ref int customerIdx, ref int depotIdx) {
185      orderAssignment[customerIdx] = order.Id;
186
187      instance.Demand[customerIdx] = order.Demand;
188      instance.PickupDeliveryLocation[customerIdx] = customerIdx + (order.ServiceRequest ? 1 : 2);
189      instance.ServiceTime[customerIdx] = order.PickupServiceTime;
190      instance.ReadyTime[customerIdx + depotIdx] = Math.Max(0, order.PickupReadyTime - timeDelta);
191      instance.DueTime[customerIdx + depotIdx] = Math.Max(0, order.PickupDueTime - timeDelta);
192      instance.Coordinates[customerIdx + depotIdx, 0] = order.PickupXCoord;
193      instance.Coordinates[customerIdx + depotIdx, 1] = order.PickupYCoord;
194      customerIdx++;
195
196      if (!order.ServiceRequest) {
197        orderAssignment[customerIdx] = order.Id;
198
199        instance.Demand[customerIdx] = -order.Demand;
200        instance.PickupDeliveryLocation[customerIdx] = customerIdx;
201        instance.ServiceTime[customerIdx] = order.DeliveryServiceTime;
202        instance.ReadyTime[customerIdx + depotIdx] = Math.Max(0, order.DeliveryReadyTime - timeDelta);
203        instance.DueTime[customerIdx + depotIdx] = Math.Max(0, order.DeliveryDueTime - timeDelta);
204        instance.Coordinates[customerIdx + depotIdx, 0] = order.DeliveryXCoord;
205        instance.Coordinates[customerIdx + depotIdx, 1] = order.DeliveryYCoord;
206        customerIdx++;
207      }
208
209      foreach (PotvinEncoding solution in solutions) {
210        if (!order.ServiceRequest && !solution.Unrouted.Contains(customerIdx - 1))
211          solution.Unrouted.Add(customerIdx - 1);
212
213        if (!solution.Unrouted.Contains(customerIdx))
214          solution.Unrouted.Add(customerIdx);
215      }
216    }
217
218    public void AddOrder(Order order) {
219      foreach (DynPDPProblemInstance instance in instances) {
220        int customerIdx = instance.Demand.Length;
221        int depotIdx = instance.Vehicles.Value;
222
223        int added = order.ServiceRequest ? 1 : 2;
224        (instance.Coordinates as IStringConvertibleMatrix).Rows += added;
225        (instance.ReadyTime as IStringConvertibleArray).Length += added;
226        (instance.DueTime as IStringConvertibleArray).Length += added;
227        (instance.Demand as IStringConvertibleArray).Length += added;
228        (instance.ServiceTime as IStringConvertibleArray).Length += added;
229        (instance.PickupDeliveryLocation as IStringConvertibleArray).Length += added;
230
231        AddOrder(instance, order, ref customerIdx, ref depotIdx);
232
233        instance.ResetDistanceMatrix();
234      }
235    }
236
237    public void UpdateVehicle(Vehicle vehicle, bool diversionAllowed) {
238      bool last = false;
239      for (int i = 0; i < instances.Count; i++) {
240        DynPDPProblemInstance instance = instances[i];
241        last = (i == instances.Count - 1);
242        int vehicleIdx = vehicleAssignment.First(kvp => kvp.Value == vehicle.Id).Key;
243
244        if (!diversionAllowed && vehicle.VehicleState == VehicleState.Moving)
245          instance.VehicleStates[vehicleIdx] = VehicleState.Waiting;
246        else
247          instance.VehicleStates[vehicleIdx] = vehicle.VehicleState;
248
249        if (diversionAllowed) {
250          instance.Coordinates[vehicleIdx, 0] = vehicle.PositionX;
251          instance.Coordinates[vehicleIdx, 1] = vehicle.PositionY;
252
253          instance.Capacity[vehicleIdx] = vehicle.Capacity;
254
255          instance.ResetDistanceMatrix();
256          if (vehicle.Distance > 0)
257            instance.VehicleUsed[vehicleIdx] = true;
258        } else {
259          var found = orderAssignment.Where(kvp => kvp.Value == vehicle.CurrentOrder).ToList();
260          if (found.Count() > 0) {
261            instance.Coordinates[vehicleIdx, 0] = vehicle.TargetPositionX;
262            instance.Coordinates[vehicleIdx, 1] = vehicle.TargetPositionY;
263
264            int target = -1, source = -1;
265            if (found.Count == 2 &&
266               (vehicle.CurrentAction == VehicleAction.Pickup || vehicle.CurrentAction == VehicleAction.Deliver)) {
267              if (instance.Demand[found[0].Key] >= 0) {
268                source = found[0].Key;
269                target = found[1].Key;
270              } else {
271                target = found[0].Key;
272                source = found[1].Key;
273              }
274
275              int vehicleId = vehicleAssignment.First(
276               kvp => kvp.Value == vehicle.Id).Key;
277              instance.PickupDeliveryLocation[target] = -vehicleId;
278            } else if (found.Count == 1 &&
279              (vehicle.CurrentAction == VehicleAction.Deliver)) {
280              source = found[0].Key;
281            }
282
283            if (source >= 0) {
284              if(last)
285                RemoveCustomer(source, vehicleIdx, diversionAllowed);
286              instance.ResetDistanceMatrix();
287            }
288
289            instance.VehicleUsed[vehicleIdx] = true;
290          }
291        }
292
293        instance.ReadyTime[vehicleIdx] = Math.Max(0, vehicle.ReadyTime - timeDelta);
294        vehicleAssignment[vehicleIdx] = vehicle.Id;
295      }
296    }
297
298    private void RemoveCustomer(int customer, int vehicle, bool diversionAllowed) {
299      foreach (DynPDPProblemInstance instance in instances) {
300        if (!diversionAllowed) {
301          instance.Capacity[vehicle] -= instance.Demand[customer];
302        }
303
304        int customers = instance.Cities.Value;
305        int depots = instance.Vehicles.Value;
306
307        for (int i = customer; i < customers - 1; i++) {
308          instance.Demand[i] = instance.Demand[i + 1];
309          instance.ServiceTime[i] = instance.ServiceTime[i + 1];
310          instance.PickupDeliveryLocation[i] = instance.PickupDeliveryLocation[i + 1];
311
312          int index = i + depots;
313          instance.ReadyTime[index] = instance.ReadyTime[index + 1];
314          instance.DueTime[index] = instance.DueTime[index + 1];
315          instance.Coordinates[index, 0] = instance.Coordinates[index + 1, 0];
316          instance.Coordinates[index, 1] = instance.Coordinates[index + 1, 1];
317        }
318
319        for (int i = 0; i < customers; i++) {
320          if (instance.PickupDeliveryLocation[i] > customer)
321            instance.PickupDeliveryLocation[i] -= 1;
322        }
323
324        (instance.Coordinates as IStringConvertibleMatrix).Rows -= 1;
325        (instance.ReadyTime as IStringConvertibleArray).Length -= 1;
326        (instance.DueTime as IStringConvertibleArray).Length -= 1;
327        (instance.Demand as IStringConvertibleArray).Length -= 1;
328        (instance.ServiceTime as IStringConvertibleArray).Length -= 1;
329        (instance.PickupDeliveryLocation as IStringConvertibleArray).Length -= 1;
330      }
331
332      foreach (PotvinEncoding solution in solutions) {
333        int i;
334        foreach (Tour tour in solution.Tours) {
335          i = 0;
336          while (i < tour.Stops.Count) {
337            if (tour.Stops[i] > (customer + 1)) {
338              tour.Stops[i] = tour.Stops[i] - 1;
339              i++;
340            } else if (tour.Stops[i] < (customer + 1)) {
341              i++;
342            } else {
343              tour.Stops.RemoveAt(i);
344            }
345          }
346        }
347
348        solution.Repair();
349
350        i = 0;
351        while (i < solution.Unrouted.Count) {
352          if (solution.Unrouted[i] > (customer + 1)) {
353            solution.Unrouted[i] = solution.Unrouted[i] - 1;
354            i++;
355          } else if (solution.Unrouted[i] < (customer + 1)) {
356            i++;
357          } else {
358            solution.Unrouted.RemoveAt(i);
359          }
360        }
361      }
362
363      Dictionary<int, Guid> newOrderAssignment = new Dictionary<int, Guid>();
364      foreach (int assigned in orderAssignment.Keys) {
365        if (assigned > customer)
366          newOrderAssignment[assigned - 1] = orderAssignment[assigned];
367        else if (assigned != customer)
368          newOrderAssignment[assigned] = orderAssignment[assigned];
369      }
370      orderAssignment = newOrderAssignment;
371    }
372
373    public void UpdateOrder(Order order, bool diversionAllowed) {
374      bool last = false;
375      for(int i = 0; i < instances.Count; i++) {
376        DynPDPProblemInstance instance = instances[i];
377        last = (i == instances.Count - 1);
378        var customers = orderAssignment.Where(
379          kvp => kvp.Value == order.Id).ToList();
380        int depots = instance.Vehicles.Value;
381        int vehicle = vehicleAssignment.First(
382              kvp => kvp.Value == order.Vehicle).Key;
383
384        int source = -1;
385        int target = -1;
386
387        if (order.OrderState == OrderState.PickingUp || order.OrderState == OrderState.PickedUp) {
388          if (!order.ServiceRequest && customers.Count == 2) {
389            if (instance.Demand[customers[0].Key] >= 0) {
390              source = customers[0].Key;
391              target = customers[1].Key;
392            } else {
393              source = customers[1].Key;
394              target = customers[0].Key;
395            }
396
397            instance.PickupDeliveryLocation[target] = -vehicle;
398            if (last)
399              RemoveCustomer(source, vehicle, diversionAllowed);
400            instance.ResetDistanceMatrix();
401          } else if (order.ServiceRequest && customers.Count == 1) {
402            target = customers[0].Key;
403
404            if (last)
405              RemoveCustomer(target, vehicle, diversionAllowed);
406            instance.ResetDistanceMatrix();
407          }
408        } else if (order.OrderState == OrderState.Delivering || order.OrderState == OrderState.Delivered) {
409          if (customers.Count == 1) {
410            target = customers[0].Key;
411
412            if (last)
413              RemoveCustomer(target, vehicle, diversionAllowed);
414            instance.ResetDistanceMatrix();
415          } else if (customers.Count == 2) {
416            if (instance.Demand[customers[0].Key] >= 0) {
417              source = customers[0].Key;
418              target = customers[1].Key;
419            } else {
420              source = customers[1].Key;
421              target = customers[0].Key;
422            }
423
424            if (last)
425              RemoveCustomer(source, vehicle, diversionAllowed);
426            if (last)
427              RemoveCustomer(target - 1, vehicle, diversionAllowed);
428            instance.ResetDistanceMatrix();
429          }
430        }
431      }
432    }
433
434    public void InitializeInstance(List<Vehicle> vehicles, List<Order> orders) {
435      if (vehicles.Count > 0) {
436        foreach (DynPDPProblemInstance instance in instances) {
437          timeDelta = 0;
438
439          instance.Coordinates = new DoubleMatrix(vehicles.Count + orders.Count * 2, 2);
440          instance.DepotCoordinates = new DoubleMatrix(vehicles.Count, 2);
441          instance.ReadyTime = new DoubleArray(vehicles.Count + orders.Count * 2);
442          instance.DueTime = new DoubleArray(vehicles.Count + orders.Count * 2);
443
444          instance.Capacity = new DoubleArray(vehicles.Count);
445          instance.VehicleDepotAssignment = new IntArray(vehicles.Count);
446          instance.VehicleUsed = new BoolArray(vehicles.Count);
447          instance.VehicleStates.Clear();
448          for (int i = 0; i < vehicles.Count; i++) {
449            instance.VehicleStates.Add(VehicleState.Parked);
450          }
451
452          int depotIdx = 0;
453          int vehicleIdx = 0;
454          foreach (Vehicle vehicle in vehicles) {
455            vehicleAssignment[vehicleIdx] = vehicle.Id;
456
457            instance.Coordinates[depotIdx, 0] = vehicle.DepotX;
458            instance.Coordinates[depotIdx, 1] = vehicle.DepotY;
459            instance.DepotCoordinates[depotIdx, 0] = vehicle.DepotX;
460            instance.DepotCoordinates[depotIdx, 1] = vehicle.DepotY;
461
462            instance.ReadyTime[vehicleIdx] = 0;
463            instance.DueTime[vehicleIdx] = vehicle.DueTime;
464
465            instance.Capacity[vehicleIdx] = vehicle.Capacity;
466            instance.VehicleDepotAssignment[vehicleIdx] = depotIdx;
467
468            depotIdx++;
469            vehicleIdx++;
470          }
471
472          instance.Depots.Value = depotIdx;
473          instance.Vehicles.Value = vehicleIdx;
474
475          foreach (PotvinEncoding solution in solutions) {
476            (solution.VehicleAssignment as IStringConvertibleArray).Length = instance.Vehicles.Value;
477          }
478
479          instance.Demand = new DoubleArray(orders.Count * 2);
480          instance.ServiceTime = new DoubleArray(orders.Count * 2);
481          instance.PickupDeliveryLocation = new IntArray(orders.Count * 2);
482
483          int customerIdx = 0;
484          foreach (Order order in orders) {
485            AddOrder(instance, order, ref customerIdx, ref depotIdx);
486          }
487
488          if (customerIdx != orders.Count * 2) {
489            (instance.Coordinates as IStringConvertibleMatrix).Rows = vehicles.Count + customerIdx;
490            (instance.ReadyTime as IStringConvertibleArray).Length = vehicles.Count + customerIdx;
491            (instance.DueTime as IStringConvertibleArray).Length = vehicles.Count + customerIdx;
492            (instance.Demand as IStringConvertibleArray).Length = customerIdx;
493            (instance.ServiceTime as IStringConvertibleArray).Length = customerIdx;
494            (instance.PickupDeliveryLocation as IStringConvertibleArray).Length = customerIdx;
495          }
496
497          instance.ResetDistanceMatrix();
498          instance.Initialize();
499        }
500        initialized = true;
501      }
502    }
503  }
504}
Note: See TracBrowser for help on using the repository browser.