A metaheuristic algorithm for the multi-depot vehicle routing problem with heterogeneous fleet

Abstract: This paper proposes a metaheuristic algorithm to solve the Multi-Depot Vehicle Routing Problem with a Heterogeneous Fleet (MDHFVRP). The problem consists of determining the customers and the vehicles to be assigned to each used depot and the routes to be performed to fulfill the demands of a set of customers. The objective is to minimize the sum of the fixed cost associated with the used vehicles and of the variable traveling costs related to the performed routes. The proposed approach is based on a modified genetic algorithm, which generates an initial population with heuristic solutions obtained from the well-known (LKH) heuristic algorithm for the TSP together with the solution of a mathematical model for the shortest path problem. In addition, two recombination methods and a mutation operator are considered. Computational experiments on benchmark instances show that the proposed algorithm can obtain high-quality solutions within short computing times.

How to cite this paper

 Bolaños, R., Escobar, J & Echeverri, M. (2018). A metaheuristic algorithm for the multi-depot vehicle routing problem with heterogeneous fleet.International Journal of Industrial Engineering Computations , 9(4), 461-478.

Refrences

References

Aras, N., Aksen, D., & Tekin, M. T. (2011). Selective multi-depot vehicle routing problem with pricing. Transportation Research Part C, 19(5), 866-884.
Baldacci, R., & Dell'Amico, M. (2010). Heuristic algorithms for the multi-depot ring-star problem. European Journal of Operational Research, 203(1), 270-281.
Bettinelli, A., Ceselli, A., & Righini, G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C, 19(5), 723-740.
Bolaños, R., Echeverry, M., & Escobar, J. (2015). A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the Multiple Traveling Salesman Problem. Decision Science Letters, 4(4), 559-568.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Cassidy, P. J., & Bennett, H. S. (1972). A Multi-Depot Vehicle Scheduling System. Operational Research Quarterly, 23(2), 151-163.
Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery point. Operation Research, 12(4), 568-581.
Crevier, B., Cordeau, J.-F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756-773.
Dantzig, G., & Ramser, J. (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
Escobar, J.W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1), 70-79.
Escobar, J.W., Linfati, R., Toth, P., & Baldoquin, M. G. (2014). A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem. Journal of Heuristics, 20(5), 483-509.
Escobar, J.W., Linfati, R., Baldoquin, M. G., & Toth, P. (2014). A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem. Transportation Research Part B: Methodological, 67, 344-356.
Escobar, J.W., Linfati, R., & Adarme-Jaimes, W. (2015). A hybrid metaheuristic algorithm for the capacitated location routing problem. Dyna, 82(189), 243-251.
Goldberg, D. E., & Lingle, R. L. (1985). The traveling salesman problem. Proc. First Int. Conf. Genetic Algorithms and their Applications, 154-159.
Gulczynski, D., Golden, B., & Wasil, E. (2011). The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results. Computers & Industrial Engineering, 61(3), 794-804.
Gutin, G., Yeo, A., & Zverovich, A. (2002). Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Proceedings of the romanian academy, series A, 117, 81-86.
Ho, W., Ho, G. T., Jib, P., & Laub, H. W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence, 21(4), 548-557.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan, USA: The University of Michigan Press.
Karakatič, S., & Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519-532.
Kuo, Y., & Wang, C.-C. (2012). A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications, 39(8), 6949-6954.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516.
Linfati, R., Escobar, J. W., & Gatica, G. (2014). Un algoritmo metaheurístico para el problema de localización y ruteo con flota heterogénea. Ingeniería y Ciencia, 10(19), 55-76.
Mancini, S. (2016). A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic. Transportation Research Part C: Emerging Technologies, 70, 100-112.
Mirabi, M., Ghomi, S. F., & Jolai, F. (2010). Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem. Robotics and Computer-Integrated Manufacturing, 26(6), 564-569.
Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162(1), 126-141.
Oliver, I. M., Smith, D. J., & Holland, J. (1987). A study of permutation crossover operators on the traveling salesman problem. Proc. Second Int. Conf. Genetic Algorithms and their Applications, 224-230.
Prins, C. (2009). Two memetic algorithms for heterogeneous fleet vehicle routing problem. Engineering Applications of Artificial Intelligence, 22(6), 916-928.
Renaud, J., Laporte, G., & Boctor, F. F. (1996). A Tabu Search Heuristic For The Multi-Depot Vehicle Routing Problem. Computers Operations Researchs, 23(3), 229-235.
Salhi, S., & Sari, M. (1997). A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European Journal of Operational Research, 103(1), 95-112.
Salhi, S., Imran, A., & Wassan, N. A. (2014). The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation. Computers & Operations Research, 52, 315-32.
Subramanian, A., Vaz-Penna, P. H., Uchoa, E., & Ochi, L. S. (2012). European Journal of Operational Research. A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem, 221(2), 285-295.
Syswerda, G. (1991). Schedule optimization using genetic algorithms. In A Handbook of Genetic Algorithms (Edited by L. Davis), 332-349.
Toth, P., & Vigo, D. (2002). An overview of vehicle routing problems. In P. Toth, D. Vigo, & M. o. Applications (Ed.), The Vehicle Routing Problem (pp. 1-26). SIAM.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). Implicit depot assignments and rotations in vehicle routing heuristics. European Journal of Operational Research, 237, 15-28.
Wren, A., & Holliday, A. (1972). Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points. Operational Research Quarterly, 23(3), 333-344.
Wu, T.-H., Low, C., & Bai, J.-W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.
Xu, Y., Wang, L., & Yang, Y. (2012). A new variable neighborhood search algorithm for the multi depot heterogeneous vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics, 39, 289-296.
Yücenur, G. N., & Demirel, N. C. (2011). A new geometric shape-based genetic clustering algorithm for the multi-depot vehicle routing problem. Expert Systems with Applications, 38(9), 11859-11865.