Free cookie consent management tool by TermsFeed Policy Generator

Changeset 6870 for branches/VRP


Ignore:
Timestamp:
10/05/11 15:54:51 (12 years ago)
Author:
svonolfe
Message:

Improved the performance of the PFIH for multi depot problem instances (#1177)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Creators/PushForwardInsertionCreator.cs

    r6857 r6870  
    116116    }
    117117
    118     private static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
     118    private static int GetNearestDepot(IVRPProblemInstance problemInstance, List<int> depots, int customer,
     119      double alpha, double beta, double gamma, out double minCost) {
     120      int nearest = -1;
     121      minCost = double.MaxValue;
     122
     123      int depotCount = 1;
     124      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
     125      if (mdp != null) {
     126        depotCount = mdp.Depots.Value;
     127      }
     128
     129      foreach (int depot in depots) {
     130        double x0 = problemInstance.Coordinates[depot, 0];
     131        double y0 = problemInstance.Coordinates[depot, 1];
     132
     133        double distance = GetDistance(customer + depotCount - 1, depot, problemInstance);
     134       
     135        double dueTime = 0;
     136        if (problemInstance is ITimeWindowedProblemInstance)
     137          dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[customer + depotCount - 1];
     138        if (dueTime == double.MaxValue)
     139          dueTime = 0;
     140
     141        double dist;
     142        if (problemInstance.Coordinates[customer + depotCount - 1, 0] < x0)
     143          dist = -distance;
     144        else
     145          dist = distance;
     146
     147        double cost = alpha * distance + // distance 0 <-> City[i]
     148                   -beta * dueTime + // latest arrival time
     149                   -gamma * (Math.Asin((problemInstance.Coordinates[customer + depotCount - 1, 1] - y0) / dist) / 360 * dist); // polar angle
     150
     151        if (cost < minCost) {
     152          minCost = cost;
     153          nearest = depot;
     154        }
     155      }
     156
     157      return nearest;
     158    }
     159
     160    private static List<int> SortCustomers(IVRPProblemInstance problemInstance, List<int> customers, List<int> depots,
     161      Dictionary<int, int> depotAssignment,
     162      double alpha, double beta, double gamma) {
     163      List<int> sortedCustomers = new List<int>();
     164      depotAssignment.Clear();
     165
     166      List<double> costList = new List<double>();
     167
     168      for (int i = 0; i < customers.Count; i++) {
     169        double cost;
     170        int depot = GetNearestDepot(problemInstance, depots, customers[i],
     171          alpha, beta, gamma,
     172          out cost);
     173        depotAssignment[customers[i]] = depot;
     174
     175        int index = 0;
     176        while (index < costList.Count && costList[index] < cost) index++;
     177        costList.Insert(index, cost);
     178        sortedCustomers.Insert(index, customers[i]);
     179      }
     180
     181      return sortedCustomers;
     182    }
     183
     184    private static bool RemoveUnusedDepots(List<int> depots, Dictionary<int, List<int>> vehicles) {
     185      List<int> toBeRemoved = new List<int>();
     186
     187      foreach (int depot in depots) {
     188        if (vehicles[depot].Count == 0)
     189          toBeRemoved.Add(depot);
     190      }
     191
     192      foreach (int depot in toBeRemoved) {
     193        depots.Remove(depot);
     194        vehicles.Remove(depot);
     195      }
     196
     197      return toBeRemoved.Count > 0;
     198    }
     199
     200    public static PotvinEncoding CreateSolution(IVRPProblemInstance problemInstance, IRandom random,
    119201      double alphaValue = 0.7, double betaValue = 0.1, double gammaValue = 0.2,
    120202      double alphaVariance = 0.5, double betaVariance = 0.07, double gammaVariance = 0.14) {
    121203      PotvinEncoding result = new PotvinEncoding(problemInstance);
     204
     205      IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
     206      IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
    122207
    123208      double alpha, beta, gamma;
     
    126211      gamma = N(gammaValue, Math.Sqrt(gammaVariance), random);
    127212
    128       int totalTours = 0;
    129 
    130       double distance = 0;
    131       double cost = 0;
    132       List<int> unroutedList = new List<int>();
    133       List<double> costList = new List<double>();
    134 
    135       IPickupAndDeliveryProblemInstance pdp = problemInstance as IPickupAndDeliveryProblemInstance;
    136       IMultiDepotProblemInstance mdp = problemInstance as IMultiDepotProblemInstance;
    137 
    138       int depots = 1;
     213      List<int> unroutedCustomers = new List<int>();
     214      for (int i = 1; i <= problemInstance.Cities.Value; i++) {
     215        if (pdp == null ||
     216           (problemInstance.GetDemand(i) >= 0 ||
     217            pdp.GetPickupDeliveryLocation(i) <= 0))
     218          unroutedCustomers.Add(i);
     219      }
     220
     221      List<int> depots = new List<int>();
    139222      if (mdp != null) {
    140         depots = mdp.Depots.Value;
    141         for (int i = 0; i < result.VehicleAssignment.Length; i++)
    142           result.VehicleAssignment[i] = -1;
    143       }
    144 
    145       List<int> unrouted = new List<int>();
    146       for (int i = 1; i <= problemInstance.Cities.Value; i++)
    147         if (pdp == null || problemInstance.GetDemand(i) >= 0)
    148           unrouted.Add(i);
    149 
    150       for (int depot = 0; depot < depots; depot++) {
     223        for (int i = 0; i < mdp.Depots.Value; i++) {
     224          depots.Add(i);
     225        }
     226      } else {
     227        depots.Add(0);
     228      }
     229
     230      Dictionary<int, List<int>> vehicles = new Dictionary<int, List<int>>();
     231      foreach (int depot in depots) {
     232        vehicles[depot] = new List<int>();
     233
    151234        int vehicleCount = problemInstance.Vehicles.Value;
    152         List<int> vehicles = new List<int>();
    153235        if (mdp != null) {
    154           vehicleCount = 0;
    155           for (int i = 0; i < mdp.VehicleDepotAssignment.Length; i++) {
    156             if (mdp.VehicleDepotAssignment[i] == depot) {
    157               vehicleCount++;
    158               vehicles.Add(i);
     236          for (int vehicle = 0; vehicle < mdp.VehicleDepotAssignment.Length; vehicle++) {
     237            if (mdp.VehicleDepotAssignment[vehicle] == depot) {
     238              vehicles[depot].Add(vehicle);
    159239            }
    160240          }
    161241        } else {
    162           for (int i = 0; i < problemInstance.Vehicles.Value; i++)
    163             vehicles.Add(i);
    164         }
    165 
    166         costList.Clear();
    167         unroutedList.Clear();
    168 
    169         double x0 = problemInstance.Coordinates[depot, 0];
    170         double y0 = problemInstance.Coordinates[depot, 1];
    171 
    172         /*-----------------------------------------------------------------------------
    173         * generate cost list
    174         *-----------------------------------------------------------------------------
    175         */
    176         for (int i = 1; i <= problemInstance.Cities.Value; i++) {
    177           //only insert sources
    178           if (unrouted.Contains(i) && (pdp == null || problemInstance.GetDemand(i) >= 0)) {
    179             distance = GetDistance(i + depots - 1, depot, problemInstance);
    180             if (problemInstance.Coordinates[i + depots - 1, 0] < x0) distance = -distance;
    181 
    182             double dueTime = 0;
    183             if (problemInstance is ITimeWindowedProblemInstance)
    184               dueTime = (problemInstance as ITimeWindowedProblemInstance).DueTime[i + depots - 1];
    185 
    186             cost = -alpha * distance + // distance 0 <-> City[i]
    187                    beta * dueTime + // latest arrival time
    188                    gamma * (Math.Asin((problemInstance.Coordinates[i + depots - 1, 0] - y0) / distance) / 360 * distance); // polar angle
    189 
    190             int index = 0;
    191             while (index < costList.Count && costList[index] < cost) index++;
    192 
    193             costList.Insert(index, cost);
    194 
    195             unroutedList.Insert(index, i);
    196           }
    197         }
    198 
    199         int tours = 0;
     242          for (int vehicle = 0; vehicle < vehicleCount; vehicle++) {
     243            vehicles[depot].Add(vehicle);
     244          }
     245        }
     246      }
     247
     248      RemoveUnusedDepots(depots, vehicles);
     249      Dictionary<int, int> depotAssignment = new Dictionary<int, int>();
     250
     251      unroutedCustomers = SortCustomers(
     252        problemInstance, unroutedCustomers, depots, depotAssignment,
     253        alpha, beta, gamma);
     254
     255      /////////
     256      Tour tour = new Tour();
     257      result.Tours.Add(tour);
     258      int currentCustomer = unroutedCustomers[0];
     259      unroutedCustomers.RemoveAt(0);
     260
     261      int currentDepot = depotAssignment[currentCustomer];
     262      int currentVehicle = vehicles[currentDepot][0];
     263      vehicles[currentDepot].RemoveAt(0);
     264      if (RemoveUnusedDepots(depots, vehicles)) {
     265        unroutedCustomers = SortCustomers(
     266        problemInstance, unroutedCustomers, depots, depotAssignment,
     267        alpha, beta, gamma);
     268      }
     269
     270      result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
     271
     272      tour.Stops.Add(currentCustomer);
     273      if (pdp != null && pdp.GetPickupDeliveryLocation(currentCustomer) > 0) {
     274        tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
     275      }
     276      ////////
     277
     278      while (unroutedCustomers.Count > 0) {
    200279        double minimumCost = double.MaxValue;
     280        int customer = -1;
    201281        int indexOfMinimumCost = -1;
    202282        int indexOfMinimumCost2 = -1;
    203         int indexOfCustomer = -1;
    204 
    205         Tour tour = new Tour();
    206         result.Tours.Add(tour);
    207         result.VehicleAssignment[totalTours] = vehicles[0];
    208         vehicles.RemoveAt(0);
    209         tours++;
    210         totalTours++;
    211 
    212         tour.Stops.Add(unroutedList[0]);
    213 
    214         if (pdp != null) {
    215           tour.Stops.Add(pdp.GetPickupDeliveryLocation(unroutedList[0]));
    216         }
    217 
    218         unrouted.Remove(unroutedList[0]);
    219         unroutedList.RemoveAt(0);
    220 
    221         while (unroutedList.Count > 0 && (tours < vehicleCount || depot == depots - 1)) {
    222           for (int c = 0; c < unroutedList.Count; c++) {
    223             VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
    224             double originalCosts = eval.Quality;
    225             int customer = unroutedList[c];
    226 
    227             for (int i = 0; i <= tour.Stops.Count; i++) {
    228               tour.Stops.Insert(i, customer);
    229               eval = problemInstance.EvaluateTour(tour, result);
    230               double tourCost = eval.Quality - originalCosts;
    231 
    232               if (pdp != null) {
    233                 for (int j = i + 1; j <= tour.Stops.Count; j++) {
    234                   bool feasible;
    235                   cost = tourCost +
    236                     problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unroutedList[c]), 0, j, out feasible);
    237                   if (cost < minimumCost && feasible) {
    238                     minimumCost = cost;
    239                     indexOfMinimumCost = i;
    240                     indexOfMinimumCost2 = j;
    241                     indexOfCustomer = c;
    242                   }
    243                 }
    244               } else {
    245                 cost = tourCost;
    246                 bool feasible = problemInstance.Feasible(eval);
     283
     284        foreach (int unrouted in unroutedCustomers) {
     285          VRPEvaluation eval = problemInstance.EvaluateTour(tour, result);
     286          double originalCosts = eval.Quality;
     287
     288          for (int i = 0; i <= tour.Stops.Count; i++) {
     289            tour.Stops.Insert(i, unrouted);
     290            eval = problemInstance.EvaluateTour(tour, result);
     291            double tourCost = eval.Quality - originalCosts;
     292
     293            if (pdp != null && pdp.GetPickupDeliveryLocation(unrouted) > 0) {
     294              for (int j = i + 1; j <= tour.Stops.Count; j++) {
     295                bool feasible;
     296                double cost = tourCost +
     297                  problemInstance.GetInsertionCosts(eval, result, pdp.GetPickupDeliveryLocation(unrouted), 0, j, out feasible);
    247298                if (cost < minimumCost && feasible) {
     299                  customer = unrouted;
    248300                  minimumCost = cost;
    249301                  indexOfMinimumCost = i;
    250                   indexOfCustomer = c;
     302                  indexOfMinimumCost2 = j;
    251303                }
    252304              }
    253 
    254               tour.Stops.RemoveAt(i);
     305            } else {
     306              double cost = tourCost;
     307              bool feasible = problemInstance.Feasible(eval);
     308              if (cost < minimumCost && feasible) {
     309                customer = unrouted;
     310                minimumCost = cost;
     311                indexOfMinimumCost = i;
     312              }
    255313            }
    256           }
    257 
    258           // insert customer if found
    259           if (indexOfMinimumCost != -1) {
    260             tour.Stops.Insert(indexOfMinimumCost, unroutedList[indexOfCustomer]);
    261             if (pdp != null) {
    262               tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(unroutedList[indexOfCustomer]));
    263             }
    264 
    265             unrouted.Remove(unroutedList[indexOfCustomer]);
    266             unroutedList.RemoveAt(indexOfCustomer);
    267           } else if (tours < vehicleCount || depot == depots - 1) { // no feasible customer found
    268             tour = new Tour();
    269             result.Tours.Add(tour);
    270             result.VehicleAssignment[totalTours] = vehicles[0];
    271             vehicles.RemoveAt(0);
    272             tours++;
    273             totalTours++;
    274 
    275             tour.Stops.Add(unroutedList[0]);
    276             if (pdp != null) {
    277               tour.Stops.Add(pdp.GetPickupDeliveryLocation(unroutedList[0]));
    278             }
    279 
    280             unrouted.Remove(unroutedList[0]);
    281             unroutedList.RemoveAt(0);
    282           }
    283           // reset minimum   
    284           minimumCost = double.MaxValue;
    285           indexOfMinimumCost = -1;
    286           indexOfMinimumCost2 = -1;
    287           indexOfCustomer = -1;
     314
     315            tour.Stops.RemoveAt(i);
     316          }
     317        }
     318
     319        if (indexOfMinimumCost == -1 && vehicles.Count == 0) {
     320          indexOfMinimumCost = tour.Stops.Count;
     321          indexOfMinimumCost2 = tour.Stops.Count + 1;
     322          customer = unroutedCustomers[0];
     323        }
     324
     325        // insert customer if found
     326        if (indexOfMinimumCost != -1) {
     327          tour.Stops.Insert(indexOfMinimumCost, customer);
     328          if (pdp != null && pdp.GetPickupDeliveryLocation(customer) > 0) {
     329            tour.Stops.Insert(indexOfMinimumCost2, pdp.GetPickupDeliveryLocation(customer));
     330          }
     331
     332          unroutedCustomers.Remove(customer);
     333        } else { // no feasible customer found
     334          tour = new Tour();
     335          result.Tours.Add(tour);
     336          currentCustomer = unroutedCustomers[0];
     337          unroutedCustomers.RemoveAt(0);
     338
     339          currentDepot = depotAssignment[currentCustomer];
     340          currentVehicle = vehicles[currentDepot][0];
     341          vehicles[currentDepot].RemoveAt(0);
     342          if (RemoveUnusedDepots(depots, vehicles)) {
     343            unroutedCustomers = SortCustomers(
     344            problemInstance, unroutedCustomers, depots, depotAssignment,
     345            alpha, beta, gamma);
     346          }
     347
     348          result.VehicleAssignment[result.Tours.Count - 1] = currentVehicle;
     349
     350          tour.Stops.Add(currentCustomer);
     351          if (pdp != null && pdp.GetPickupDeliveryLocation(currentCustomer) > 0) {
     352            tour.Stops.Add(pdp.GetPickupDeliveryLocation(currentCustomer));
     353          }
    288354        }
    289355      }
Note: See TracChangeset for help on using the changeset viewer.