Desempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitos
Abstract
The vehicle routing problem considering multiple depots is classified as NP-hard. MDVRP determines simultaneously the routes of a set of vehicles and aims to meet a set of clients with a known demand. The objective function of the problem is to minimize the total distance traveled by the routes given that all customers must be served considering capacity constraints in depots and vehicles. This paper presents a hybrid methodology that combines agglomerative clustering techniques to generate initial solutions with an iterated local search algorithm (ILS) to solve the problem. Although previous studies clustering methods have been proposed like strategies to generate initial solutions, in this work the search is intensified on the information generated after applying the clustering technique. Besides an extensive analysis on the performance of techniques, and their effect in the final solution is performed. The operation of the proposed methodology is feasible and effective to solve the problem regarding the quality of the answers and computational times obtained on request evaluated literature.References
K. F. Doerner and V. Schmid, “Survey: Matheuristics for rich vehicle routing problems,” in 7th International Workshop on Hybrid Metaheuristics, HM 2010, vol. 6373 LNCS, M. Blesa, C. Blum, G. Raidl, A. Roli, and M. Samples, Eds. Berlin: Springer, 2010, pp. 206–221.
J. R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Comput. Ind. Eng., vol. 79, pp. 115–129, Jan. 2015.
P. Cassidy and H. Bennett, “Vehicle System Scheduling,” OR Soc., vol. 23, no. 2, pp. 151–163, 2015.
M. Ball, B. Golden, and A. Assad, “Planning for Truck Fleet Size in the Presence of a Common-Carrier Option,” Decis. Sci., vol. 14, no. 1, pp. 103–120, 2007.
B. L. Golden and E. a. Wasil, “OR Practice--Computerized Vehicle Routing in the Soft Drink Industry,” Oper. Res., vol. 35, no. 1, pp. 6–17, 1987.
M. Fisher, R. Greenfield, R. Jaikumar, and J. Lester, “A computerized Vehicle Routing Application,” Interfaces (Providence)., vol. 4, pp. 42–52, 12AD.
W. J. Bell, L. M. Dalberto, M. L. Fisher, a. J. Greenfield, R. Jaikumar, P. Kedia, R. G. Mack, and P. J. Prutzman, “Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer,” Interfaces (Providence)., vol. 13, no. 6, pp. 4–23, 1983.
A. G. G. Brown, C. J. Ellis, G. W. Graves, and D. Ronen, “of the dispatching are to minimize cost of delivered product, to balance the workload among the company trucks, and to load the maximum weight on a truck while adhering to all laws. The important,” vol. 17, no. 1, pp. 2–4, 1987.
J. Pooley, “Integrated Production and Distribution Facility Planning at Ault Foods,” Interfaces (Providence)., vol. 24, no. 4, pp. 113–121, 1994.
R. Baldacci and A. Mingozzi, “A unified exact method for solving different classes of vehicle routing problems,” Math. Program., vol. 120, no. 2, pp. 347–380, Sep. 2009.
N. Christofides, A. Mingozzi, and P. Toth, “Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations,” Math. Program., vol. 20, no. 1, pp. 255–282, Dec. 1981.
R. Baldacci, E. Bartolini, a. Mingozzi, and a. Valletta, “An Exact Algorithm for the Period Routing Problem,” Oper. Res., vol. 59, no. 1, pp. 228–241, 2011.
C. Contardo and R. Martinelli, “A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints,” Discret. Optim., vol. 12, pp. 129–146, May 2014.
S. Salhi and M. Sari, “A multi-level composite heuristic for the multi-depot vehicle fleet mix problem,” Eur. J. Oper. Res., vol. 103, no. 1, pp. 95–112, Nov. 1997.
E. M. Toro O., A. H. Escobar Z., and M. Granada E., “Literature Review On The Vehicle Routing Problem In The Green Transportation Context,” Luna Azul, vol. 42, no. 42, pp. 362–387, Dec. 2015.
I. D. Giosa, I. L. Tansini, and I. O. Viera, “New assignment algorithms for the multi-depot vehicle routing problem,” J. Oper. Res. Soc., vol. 53, no. 9, pp. 977–984, Sep. 2002.
G. Nagy and S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” Eur. J. Oper. Res., vol. 162, no. 1, pp. 126–141, Apr. 2005.
C.-G. Lee, M. a. Epelman, C. C. White, and Y. a. Bozer, “A shortest path approach to the multiple-vehicle routing problem with split pick-ups,” Transp. Res. Part B Methodol., vol. 40, no. 4, pp. 265–284, May 2006.
B. Crevier, J.-F. Cordeau, and G. Laporte, “The multi-depot vehicle routing problem with inter-depot routes,” Eur. J. Oper. Res., vol. 176, no. 2, pp. 756–773, Jan. 2007.
G. Jeon, H. R. Leep, and J. Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm,” Comput. Ind. Eng., vol. 53, no. 4, pp. 680–692, Nov. 2007.
W. Ho, G. T. S. Ho, P. Ji, and H. C. W. Lau, “A hybrid genetic algorithm for the multi-depot vehicle routing problem,” Eng. Appl. Artif. Intell., vol. 21, no. 4, pp. 548–557, Jun. 2008.
G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper. Res., vol. 12, no. 4, pp. 568–581, Aug. 1964.
P. Surekha and S. Sumathi, “Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms,” World Appl. Program., vol. 1, no. 3, pp. 118–131, 2011.
J.-F. Cordeau and M. Maischberger, “A parallel iterated tabu search heuristic for vehicle routing problems,” Comput. Oper. Res., vol. 39, no. 9, pp. 2033–2050, Sep. 2012.
T. Vidal and T. G. G. Crainic, “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems,” Oper. …, vol. 60, no. 3, pp. 611–624, 2012.
A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Comput. Oper. Res., vol. 40, no. 10, pp. 2519–2531, Oct. 2013.
J. W. Escobar, R. Linfati, P. Toth, and M. G. Baldoquin, “A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem,” J. Heuristics, vol. 20, no. 5, pp. 483–509, Oct. 2014.
A. C. Rencher, A Review Of “Methods of Multivariate Analysis, ,” vol. 37, no. 11. 2005.
S. Barreto, C. Ferreira, J. Paixão, and B. S. Santos, “Using clustering analysis in a capacitated location-routing problem,” Eur. J. Oper. Res., vol. 179, no. 3, pp. 968–977, Jun. 2007.
A. Subramanian, “Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems.” Universidade Federal Fluminense, Niteroi, Sao Pablo, pp. 60–69, 2012.
Downloads
