Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DynamicVehicleRouting/HeuristicLab.PDPSimulation/3.3/Operators/DynPushForwardInsertionCreator.cs @ 8670

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

Added first version of the dynamic vehicle routing addon (#1955)

File size: 25.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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 HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Common;
31using HeuristicLab.Problems.VehicleRouting.Interfaces;
32using HeuristicLab.Problems.VehicleRouting.ProblemInstances;
33using HeuristicLab.Problems.VehicleRouting.Variants;
34using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
35using HeuristicLab.Problems.VehicleRouting;
36
37namespace HeuristicLab.PDPSimulation.Operators {
38  [Item("DynPushForwardInsertionCreator", "Creates a randomly initialized VRP solution.")]
39  [StorableClass]
40  public sealed class DynPushForwardInsertionCreator : PotvinCreator, IStochasticOperator {
41    #region IStochasticOperator Members
42    public ILookupParameter<IRandom> RandomParameter {
43      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
44    }
45    #endregion
46
47    public IValueParameter<DoubleValue> Alpha {
48      get { return (IValueParameter<DoubleValue>)Parameters["Alpha"]; }
49    }
50    public IValueParameter<DoubleValue> AlphaVariance {
51      get { return (IValueParameter<DoubleValue>)Parameters["AlphaVariance"]; }
52    }
53    public IValueParameter<DoubleValue> Beta {
54      get { return (IValueParameter<DoubleValue>)Parameters["Beta"]; }
55    }
56    public IValueParameter<DoubleValue> BetaVariance {
57      get { return (IValueParameter<DoubleValue>)Parameters["BetaVariance"]; }
58    }
59    public IValueParameter<DoubleValue> Gamma {
60      get { return (IValueParameter<DoubleValue>)Parameters["Gamma"]; }
61    }
62    public IValueParameter<DoubleValue> GammaVariance {
63      get { return (IValueParameter<DoubleValue>)Parameters["GammaVariance"]; }
64    }
65
66    [StorableConstructor]
67    private DynPushForwardInsertionCreator(bool deserializing) : base(deserializing) { }
68
69    public DynPushForwardInsertionCreator()
70      : base() {
71      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator."));
72      Parameters.Add(new ValueParameter<DoubleValue>("Alpha", "The alpha value.", new DoubleValue(0.7)));
73      Parameters.Add(new ValueParameter<DoubleValue>("AlphaVariance", "The alpha variance.", new DoubleValue(0.5)));
74      Parameters.Add(new ValueParameter<DoubleValue>("Beta", "The beta value.", new DoubleValue(0.1)));
75      Parameters.Add(new ValueParameter<DoubleValue>("BetaVariance", "The beta variance.", new DoubleValue(0.07)));
76      Parameters.Add(new ValueParameter<DoubleValue>("Gamma", "The gamma value.", new DoubleValue(0.2)));
77      Parameters.Add(new ValueParameter<DoubleValue>("GammaVariance", "The gamma variance.", new DoubleValue(0.14)));
78    }
79
80    public override IDeepCloneable Clone(Cloner cloner) {
81      return new DynPushForwardInsertionCreator(this, cloner);
82    }
83
84    private DynPushForwardInsertionCreator(DynPushForwardInsertionCreator original, Cloner cloner)
85      : base(original, cloner) {
86    }
87
88    // use the Box-Mueller transform in the polar form to generate a N(0,1) random variable out of two uniformly distributed random variables
89    private static double Gauss(IRandom random) {
90      double u = 0.0, v = 0.0, s = 0.0;
91      do {
92        u = (random.NextDouble() * 2) - 1;
93        v = (random.NextDouble() * 2) - 1;
94        s = Math.Sqrt(u * u + v * v);
95      } while (s < Double.Epsilon || s > 1);
96      return u * Math.Sqrt((-2.0 * Math.Log(s)) / s);
97    }
98
99    private static double N(double mu, double sigma, IRandom random) {
100      return mu + (sigma * Gauss(random)); // transform the random variable sampled from N(0,1) to N(mu,sigma)
101    }
102
103    private static double GetDistance(int start, int end, IVRPProblemInstance problemInstance, PotvinEncoding solution) {
104      double distance = 0.0;
105
106      if (problemInstance is DynPDPProblemInstance) {
107        distance = (problemInstance as DynPDPProblemInstance).GetDistance(start, end);
108      }
109      else if (problemInstance.UseDistanceMatrix.Value && problemInstance.DistanceMatrix != null) {
110        distance = problemInstance.DistanceMatrix[start, end];
111      } else {
112        double startX = problemInstance.Coordinates[start, 0];
113        double startY = problemInstance.Coordinates[start, 1];
114
115        double endX = problemInstance.Coordinates[end, 0];
116        double endY = problemInstance.Coordinates[end, 1];
117
118        distance =
119            Math.Sqrt(
120              Math.Pow(startX - endX, 2) +
121              Math.Pow(startY - endY, 2));
122      }
123
124      return distance;
125    }
126
127    private static double GetCosts(int customer, int vehicle, IVRPProblemInstance problemInstance,
128      Dictionary<int, List<int>> vehicles, Dictionary<int, Tour> vehicleTours, List<bool> vehicleUsed, PotvinEncoding solution,
129      double alpha, double beta, double gamma, out bool feasible, out bool existingRoute) {
130      int depotCount = 1;
131      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
132      if (mdp != null) {
133        depotCount = mdp.Depots.Value;
134      }
135
136      feasible = true;
137
138      double distance = GetDistance(vehicle, customer + depotCount - 1, problemInstance, solution);
139      if (vehicleUsed != null) {
140        existingRoute = vehicleUsed[vehicle];
141      } else {
142        existingRoute = true;
143      }
144
145      double dueTime = 0;
146      if (problemInstance is ITimeWindowedProblemInstance) {
147        ITimeWindowedProblemInstance vrptw = problemInstance as ITimeWindowedProblemInstance;
148        dueTime = vrptw.DueTime[customer + depotCount - 1];
149      }
150
151      if (vehicleTours.ContainsKey(vehicle)) {
152        Tour tour = vehicleTours[vehicle];
153
154        IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
155        if (pdp != null && pdp.GetPickupDeliveryLocation(customer) > 0) {
156          solution.InsertPair(tour, customer, pdp.GetPickupDeliveryLocation(customer), problemInstance);
157        } else {
158          tour.Stops.Insert(solution.FindBestInsertionPlace(tour, customer), customer);
159        }
160
161        feasible = problemInstance.TourFeasible(tour, solution);
162
163        tour.Stops.Remove(customer);
164        if (pdp != null && pdp.GetPickupDeliveryLocation(customer) > 0) {
165          tour.Stops.Remove(pdp.GetPickupDeliveryLocation(customer));
166        }
167      }
168      else if (problemInstance is ITimeWindowedProblemInstance) {
169        IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
170        ITimeWindowedProblemInstance vrptw = problemInstance as ITimeWindowedProblemInstance;
171        double time = vrptw.ReadyTime[vehicle];
172        time += distance;
173        if (time > dueTime) {
174          feasible = false;
175        } else {
176          time += vrptw.ServiceTime[customer - 1];
177          if (pdp != null && pdp.GetPickupDeliveryLocation(customer) > 0) {
178            int targetCustomer = pdp.GetPickupDeliveryLocation(customer);
179            time += GetDistance(customer + depotCount - 1, targetCustomer + depotCount - 1, problemInstance, solution);
180            if (time > vrptw.DueTime[targetCustomer + depotCount - 1]) {
181              feasible = false;
182            }
183
184            time += vrptw.ServiceTime[targetCustomer - 1];
185            time += GetDistance(targetCustomer + depotCount - 1, vehicle, problemInstance, solution);
186
187            if (time > vrptw.DueTime[vehicle]) {
188              feasible = false;
189            }
190          } else {
191            time += GetDistance(customer + depotCount - 1, vehicle, problemInstance, solution);
192            if (time > vrptw.DueTime[vehicle]) {
193              feasible = false;
194            }
195          }
196        }
197      }
198
199      if (problemInstance is IHeterogenousCapacitatedProblemInstance) {
200        IHeterogenousCapacitatedProblemInstance cvrp = problemInstance as IHeterogenousCapacitatedProblemInstance;
201        double demand = problemInstance.GetDemand(customer);
202        if (demand > cvrp.Capacity[vehicle])
203          feasible = false;
204      } else if (problemInstance is IHomogenousCapacitatedProblemInstance) {
205        IHomogenousCapacitatedProblemInstance cvrp = problemInstance as IHomogenousCapacitatedProblemInstance;
206        double demand = problemInstance.GetDemand(customer);
207        if (demand > cvrp.Capacity.Value)
208          feasible = false;
209      }
210
211      double x0 = problemInstance.Coordinates[vehicle, 0];
212      double y0 = problemInstance.Coordinates[vehicle, 1];
213      double dist;
214      if (problemInstance.Coordinates[customer + depotCount - 1, 0] < x0)
215        dist = -distance;
216      else
217        dist = distance;
218      double polarAngle = (dist != 0 ? (Math.Asin((problemInstance.Coordinates[customer + depotCount - 1, 1] - y0) / dist) / 360 * dist) : 0);
219
220      if (problemInstance is ITimeWindowedProblemInstance) {
221        ITimeWindowedProblemInstance vrptw = problemInstance as ITimeWindowedProblemInstance;
222
223        if (dueTime == double.MaxValue)
224          dueTime = 0;
225        else {
226          dueTime -= vrptw.ReadyTime[vehicle];
227        }
228      }
229
230      double cost = alpha * distance + // distance 0 <-> City[i]
231                   -beta * dueTime + // latest arrival time
232                  -gamma * polarAngle; // polar angle
233
234      if (vehicleUsed != null) {
235        if (!vehicleUsed[vehicle])
236          cost += problemInstance.FleetUsageFactor.Value;
237      }
238
239      return cost;
240    }
241
242    private static int GetNearestDepot(IVRPProblemInstance problemInstance, List<int> depots, int customer,
243      Dictionary<int, List<int>> vehicles, Dictionary<int, Tour> vehicleTours, List<bool> vehicleUsed, PotvinEncoding solution,
244      double alpha, double beta, double gamma, out double minCost, out bool bound, out bool bestExistingRoute) {
245      int nearest = -1;
246      minCost = double.MaxValue;
247      bestExistingRoute = false;
248
249      bool bestFeasible = false;
250      int feasibleCount = 0;
251      foreach (int depot in depots) {
252        int vehicle = vehicles[depot][0];
253
254        bool existingRoute;
255        bool feasible;
256        double cost = GetCosts(
257          customer, vehicle,
258          problemInstance, vehicles, vehicleTours, vehicleUsed,
259          solution, alpha, beta, gamma, out feasible, out existingRoute);
260
261        if (feasible)
262          feasibleCount++;
263
264        if ((feasible && !bestFeasible) ||
265          (feasible == bestFeasible && existingRoute && !bestExistingRoute) ||
266          (feasible == bestFeasible && existingRoute == bestExistingRoute && cost < minCost)) {
267          minCost = cost;
268          nearest = depot;
269          bestFeasible = feasible;
270          bestExistingRoute = existingRoute;
271        }
272      }
273
274      bound = (feasibleCount == 1);
275
276      return nearest;
277    }
278
279    private static List<int> SortCustomers(IVRPProblemInstance problemInstance, List<int> customers, List<int> depots,
280      Dictionary<int, int> depotAssignment, Dictionary<int, int> customerBinding,
281      Dictionary<int, List<int>> vehicles, Dictionary<int, Tour> vehicleTours, List<bool> vehicleUsed, PotvinEncoding solution,
282      double alpha, double beta, double gamma) {
283      List<int> sortedCustomers = new List<int>();
284      depotAssignment.Clear();
285      customerBinding.Clear();
286
287      List<bool> boundList = new List<bool>();
288      List<bool> existingRouteList = new List<bool>();
289      List<double> costList = new List<double>();
290
291      for (int i = 0; i < customers.Count; i++) {
292        double cost;
293        bool bound;
294        bool existingRoute;
295        int depot = GetNearestDepot(problemInstance, depots, customers[i], vehicles, vehicleTours, vehicleUsed, solution,
296          alpha, beta, gamma,
297          out cost, out bound, out existingRoute);
298        depotAssignment[customers[i]] = depot;
299        if (bound) {
300          customerBinding.Add(customers[i], depot);
301        }
302
303        int index = 0;
304        while (index < costList.Count &&
305          ((!bound && boundList[index]) ||
306           (bound == boundList[index] && !existingRoute && existingRouteList[index]) ||
307           (bound == boundList[index] && existingRoute == existingRouteList[index] && costList[index] < cost)))
308          index++;
309
310        costList.Insert(index, cost);
311        boundList.Insert(index, bound);
312        existingRouteList.Insert(index, existingRoute);
313        sortedCustomers.Insert(index, customers[i]);
314      }
315
316      return sortedCustomers;
317    }
318
319    private static bool RemoveUnusedDepots(List<int> depots, Dictionary<int, List<int>> vehicles) {
320      List<int> toBeRemoved = new List<int>();
321
322      foreach (int depot in depots) {
323        if (vehicles[depot].Count == 0)
324          toBeRemoved.Add(depot);
325      }
326
327      foreach (int depot in toBeRemoved) {
328        depots.Remove(depot);
329        vehicles.Remove(depot);
330      }
331
332      return toBeRemoved.Count > 0;
333    }
334
335    private static Dictionary<int, Tour> CreateInitialTours(IVRPProblemInstance problemInstance, Dictionary<int, List<int>> vehicles, PotvinEncoding result) {
336      Dictionary<int, Tour> vehicleTours = new Dictionary<int, Tour>();
337      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
338
339      int currentVehicle;
340
341      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
342        if (pdp != null && pdp.GetPickupDeliveryLocation(i) <= 0) {
343          currentVehicle = -pdp.GetPickupDeliveryLocation(i);
344          foreach (int depot in vehicles.Keys) {
345            if (vehicles[depot].Contains(currentVehicle)) {
346              vehicles[depot].Remove(currentVehicle);
347              vehicles[depot].Insert(0, currentVehicle);
348              break;
349            }
350          }
351
352          Tour tour;
353
354          if (!vehicleTours.ContainsKey(currentVehicle)) {
355            tour = new Tour();
356            result.Tours.Add(tour);
357            vehicleTours[currentVehicle] = tour;
358            result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
359          } else {
360            tour = vehicleTours[currentVehicle];
361          }
362
363          tour.Stops.Add(i);
364        }
365      }
366
367      foreach (int vehicle in vehicleTours.Keys) {
368        Tour vehicleTour = vehicleTours[vehicle];
369        List<int> customers = new List<int>(vehicleTour.Stops);
370        vehicleTour.Stops.Clear();
371
372        if (problemInstance is DynPDPProblemInstance &&
373          (problemInstance as DynPDPProblemInstance).CurrentPlan != null) {
374          PotvinEncoding plan = (problemInstance as DynPDPProblemInstance).CurrentPlan;
375          Tour planTour = plan.Tours.Find(t => plan.GetVehicleAssignment(plan.Tours.IndexOf(t)) == vehicle);
376
377          customers.Sort((x, y) => planTour.Stops.IndexOf(x).CompareTo(planTour.Stops.IndexOf(y)));
378          foreach (int customer in customers)
379            vehicleTour.Stops.Add(customer);
380        } else {
381          for (int i = 0; i < customers.Count; i++) {
382            int stop = result.FindBestInsertionPlace(vehicleTour, customers[i]);
383            vehicleTour.Stops.Insert(stop, customers[i]);
384          }
385        }
386      }
387
388      return vehicleTours;
389    }
390
391    public static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random, List<bool> vehicleUsed,
392      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
393      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
394      PotvinEncoding result = new PotvinEncoding(problemInstance);
395
396      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
397      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
398
399      if (mdp != null) {
400        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
401          result.VehicleAssignment[i] = -1;
402        }
403      }
404
405      double alpha, beta, gamma;
406      lock (random) {
407        alpha = N(alphaValue, Math.Sqrt(alphaVariance), random);
408        beta = N(betaValue, Math.Sqrt(betaVariance), random);
409        gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
410      }
411
412      #region initialization
413      List<int> unroutedCustomers = new List<int>();
414      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
415        if (pdp == null || (problemInstance.GetDemand(i) >= 0) || (pdp.GetPickupDeliveryLocation(i) == i))
416          unroutedCustomers.Add(i);
417      }
418
419      List<int> depots = new List<int>();
420      if (mdp != null) {
421        for (int i = 0; i < mdp.Depots.Value; i++) {
422          depots.Add(i);
423        }
424      } else {
425        depots.Add(0);
426      }
427
428      Dictionary<int, List<int>> vehicles = new Dictionary<int, List<int>>();
429      foreach (int depot in depots) {
430        vehicles[depot] = new List<int>();
431
432        int vehicleCount = problemInstance.Vehicles.Value;
433        if (mdp != null) {
434          for (int vehicle = 0; vehicle < mdp.VehicleDepotAssignment.Length; vehicle++) {
435            if (mdp.VehicleDepotAssignment[vehicle] == depot) {
436              vehicles[depot].Add(vehicle);
437            }
438          }
439        } else {
440          for (int vehicle = 0; vehicle < vehicleCount; vehicle++) {
441            vehicles[depot].Add(vehicle);
442          }
443        }
444
445        if (vehicleUsed != null) {
446          vehicles[depot].Sort(delegate(int x, int y) {
447            if (vehicleUsed[x] && vehicleUsed[y])
448              return 0;
449            else if (vehicleUsed[x])
450              return -1;
451            else
452              return 1;
453          });
454        }
455      }
456
457      Dictionary<int, Tour> vehicleTours = CreateInitialTours(problemInstance, vehicles, result);
458      RemoveUnusedDepots(depots, vehicles);
459      #endregion
460
461      #region route unrouted
462      if (unroutedCustomers.Count > 0) {
463        Tour tour;
464        int currentDepot;
465        int currentVehicle;
466        Dictionary<int, int> depotAssignment = new Dictionary<int, int>();
467
468        //# sort customers globally - start new tour
469        Dictionary<int, int> customerBinding = new Dictionary<int, int>();
470        unroutedCustomers = SortCustomers(
471          problemInstance, unroutedCustomers, depots, depotAssignment, customerBinding,
472          vehicles, vehicleTours, vehicleUsed, result,
473          alpha, beta, gamma);
474
475        int currentCustomer = unroutedCustomers[0];
476        currentDepot = depotAssignment[currentCustomer];
477        currentVehicle = vehicles[currentDepot][0];
478        vehicles[currentDepot].RemoveAt(0);
479        RemoveUnusedDepots(depots, vehicles);
480
481        if (!vehicleTours.ContainsKey(currentVehicle)) {
482          tour = new Tour();
483          result.Tours.Add(tour);
484          result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
485
486          unroutedCustomers.Remove(currentCustomer);
487          tour.Stops.Add(currentCustomer);
488          if (pdp != null && pdp.GetPickupDeliveryLocation(currentCustomer) != currentCustomer) {
489            tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
490          }
491        } else {
492          tour = vehicleTours[currentVehicle];
493        }
494
495        while (unroutedCustomers.Count > 0) {
496          double minimumCost = double.MaxValue;
497          bool bestBoundToRoute = false;
498          int customer = -1;
499          int indexOfMinimumCost = -1;
500          int indexOfMinimumCost2 = -1;
501
502          foreach (int unrouted in unroutedCustomers) {
503            bool boundToRoute = customerBinding.ContainsKey(unrouted) && customerBinding[unrouted] == currentDepot;
504
505            VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
506            double originalCosts = eval.Quality;
507
508            for (int i = 0; i <= tour.Stops.Count; i++) {
509              tour.Stops.Insert(i, unrouted);
510              eval = problemInstance.EvaluateTour(tour, result);
511              double tourCost = eval.Quality - originalCosts;
512
513              if (pdp != null && pdp.GetPickupDeliveryLocation(unrouted) != unrouted) {
514                for (int j = i + 1; j <= tour.Stops.Count; j++) {
515                  bool feasible;
516                  double cost = tourCost +
517                    problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unrouted), 0, j, out feasible);
518                  if ((cost < minimumCost || (!bestBoundToRoute && boundToRoute)) && (boundToRoute || !bestBoundToRoute) && feasible) {
519                    customer = unrouted;
520                    minimumCost = cost;
521                    indexOfMinimumCost = i;
522                    indexOfMinimumCost2 = j;
523                    bestBoundToRoute = boundToRoute;
524                  }
525                }
526              } else {
527                double cost = tourCost;
528                bool feasible = problemInstance.Feasible(eval);
529                if ((cost < minimumCost || (!bestBoundToRoute && boundToRoute)) && (boundToRoute || !bestBoundToRoute) && feasible) {
530                  customer = unrouted;
531                  minimumCost = cost;
532                  indexOfMinimumCost = i;
533                  bestBoundToRoute = boundToRoute;
534                }
535              }
536
537              tour.Stops.RemoveAt(i);
538            }
539          }
540
541          if (indexOfMinimumCost == -1 && vehicles.Count == 0) {
542            indexOfMinimumCost = tour.Stops.Count;
543            indexOfMinimumCost2 = tour.Stops.Count + 1;
544            customer = unroutedCustomers[0];
545          }
546
547          // insert customer if found
548          if (indexOfMinimumCost != -1) {
549            tour.Stops.Insert(indexOfMinimumCost, customer);
550            if (pdp != null && pdp.GetPickupDeliveryLocation(customer) != customer) {
551              tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(customer));
552            }
553            unroutedCustomers.Remove(customer);
554          } else { // no feasible customer found
555            //# sort customers globally - start new tour
556            unroutedCustomers = SortCustomers(
557              problemInstance, unroutedCustomers, depots, depotAssignment, customerBinding,
558              vehicles, vehicleTours, vehicleUsed, result,
559              alpha, beta, gamma);
560           
561            currentCustomer = unroutedCustomers[0];
562            currentDepot = depotAssignment[currentCustomer];
563            currentVehicle = vehicles[currentDepot][0];
564            vehicles[currentDepot].RemoveAt(0);
565            RemoveUnusedDepots(depots, vehicles);
566
567            if (!vehicleTours.ContainsKey(currentVehicle)) {
568              tour = new Tour();
569              result.Tours.Add(tour);
570              result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
571
572              unroutedCustomers.Remove(currentCustomer);
573              tour.Stops.Add(currentCustomer);
574              if (pdp != null && pdp.GetPickupDeliveryLocation(currentCustomer) != currentCustomer) {
575                tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
576              }
577            } else {
578              tour = vehicleTours[currentVehicle];
579            }
580          }
581        }
582      }
583      #endregion
584
585      #region assign vehicles
586      if (mdp != null) {
587        List<int> availableVehicles = new List<int>();
588        for (int i = 0; i < mdp.Vehicles.Value; i++)
589          availableVehicles.Add(i);
590
591        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
592          if (result.VehicleAssignment[i] != -1)
593            availableVehicles.Remove(result.VehicleAssignment[i]);
594        }
595
596        for (int i = 0; i < result.VehicleAssignment.Length; i++) {
597          if (result.VehicleAssignment[i] == -1) {
598            result.VehicleAssignment[i] = availableVehicles[0];
599            availableVehicles.RemoveAt(0);
600          }
601        }
602      }
603      #endregion
604
605      return result;
606    }
607
608    public override IOperation Apply() {
609      List<bool> vehicleUsed = null;
610     
611      DynPDPProblemInstance instance = ProblemInstance as DynPDPProblemInstance;
612      if(instance != null) {
613        vehicleUsed = new List<bool>();
614        for (int i = 0; i < instance.VehicleUsed.Length; i++) {
615          vehicleUsed.Add(instance.VehicleUsed[i]);
616        }
617      }
618
619      VRPToursParameter.ActualValue = CreateSolution(ProblemInstance, RandomParameter.ActualValue, vehicleUsed,
620        Alpha.Value.Value, Beta.Value.Value, Gamma.Value.Value,
621        AlphaVariance.Value.Value, BetaVariance.Value.Value, GammaVariance.Value.Value);
622
623      return base.Apply();
624    }
625  }
626}
627
Note: See TracBrowser for help on using the repository browser.