A biobjective capacitated vehicle routing problem using metaheuristic ILS and decomposition

Abstract: Vehicle routing problems (VRPs) have usually been studied with a single objective function defined by the distances associated with the routing of vehicles. The central problem is to design a set of routes to meet the demands of customers at minimum cost. However, in real life, it is necessary to take into account other objective functions, such as social functions, which consider, for example, the drivers' workload balance. This has led to growth in both the formulation of multiobjective models and exact and approximate solution techniques. In this article, to verify the quality of the results, first, a mathematical model is proposed that takes into account both economic and work balance objectives simultaneously and is solved using an exact method based on the decomposition approach. This method is used to compare the accuracy of the proposed approximate method in test cases of medium mathematical complexity. Second, an approximate method based on the Iterated Local Search (ILS) metaheuristic and Decomposition (ILS/D) is proposed to solve the biobjective Capacitated VRP (bi-CVRP) using test cases of medium and high mathematical complexity. Finally, the nondominated sorting genetic algorithm (NSGA-II) approximate method is implemented to compare both medium- and high-complexity test cases with a benchmark. The obtained results show that ILS/D is a promising technique for solving VRPs with a multiobjective approach.

How to cite this paper

 Galindres-Guancha, L., Toro-Ocampo, E & Gallego-Rendón, R. (2021). A biobjective capacitated vehicle routing problem using metaheuristic ILS and decomposition.International Journal of Industrial Engineering Computations , 12(3), 293-304.

Refrences

Augerat, P., Naddef, D., Belenguer, J. M., Benavent, E., Corberan, A., & Rinaldi, G. (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem.
Bertazzi, L., Golden, B., & Wang, X. (2015). Min–max vs. min–sum vehicle routing: A worst-case analysis. European Journal of Operational Research, 240(2), 372-381.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
Galindres-Guancha, L., Toro-Ocampo, E., & Rendón, R. (2018). Multi-objective MDVRP solution considering route balance and cost using the ILS metaheuristic. International Journal of Industrial Engineering Computations, 9(1), 33-46.
Gallego Rendón, R. A., Toro Ocampo, E. M., & Escobar Zuluaga, A. H. (2015). Técnicas Heurísticas y Metaheurísticas. Universidad Tecnológica de Pereira. Vicerrectoría de Investigaciones, Innovación y Extensión. Ingenierías Eléctrica, Electrónica, Física y Ciencias de la Computación.
Halvorsen-Weare, E. E., & Savelsbergh, M. W. (2016). The bi-objective mixed capacitated general routing problem with different route balance criteria. European Journal of Operational Research, 251(2), 451-465.
Irnich, S., Toth, P., & Vigo, D. (2014). Chapter 1: The family of vehicle routing problems. In Vehicle Routing: Problems, Methods, and Applications, Second Edition (pp. 1-33). Society for Industrial and Applied Mathematics.
Jiang, S., Ong, Y. S., Zhang, J., & Feng, L. (2014). Consistencies and contradictions of performance metrics in multiobjective optimization. IEEE transactions on cybernetics, 44(12), 2391-2404.
Jozefowiez, N., Semet, F., & Talbi, E. G. (2005, October). Enhancements of NSGA II and its application to the vehicle routing problem with route balancing. In International Conference on Artificial Evolution (Evolution Artificielle) (pp. 131-142). Springer, Berlin, Heidelberg.
Lee, T. R., & Ueng, J. H. (1999). A study of vehicle routing problems with load‐balancing. International Journal of Physical Distribution & Logistics Management.
Li, J. Q., Borenstein, D., & Mirchandani, P. B. (2008). Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil. Omega, 36(6), 1133-1149.
Li, K., Wang, R., Zhang, T., & Ishibuchi, H. (2018). Evolutionary many-objective optimization: A comparative study of the state-of-the-art. IEEE Access, 6, 26194-26214.
Lozano, J., González-Gurrola, L. C., Rodríguez-Tello, E., & Lacomme, P. (2016, October). A statistical comparison of objective functions for the vehicle routing problem with route balancing. In 2016 Fifteenth Mexican international conference on artificial intelligence (MICAI) (pp. 130-135). IEEE.
Marler, R. T., & Arora, J. S. (2004). Survey of multi-objective optimization methods for engineering. Structural and multidisciplinary optimization, 26(6), 369-395.
Matl, P., Hartl, R. F., & Vidal, T. (2018). Workload equity in vehicle routing problems: A survey and analysis. Transportation Science, 52(2), 239-260.
Oyola, J., & Løkketangen, A. (2014). GRASP-ASP: An algorithm for the CVRP with route balancing. Journal of Heuristics, 20(4), 361-382.
Reiter, P., & Gutjahr, W. J. (2012). Exact hybrid algorithms for solving a bi-objective vehicle routing problem. Central European Journal of Operations Research, 20(1), 19-43.
Riquelme, N., Von Lücken, C., & Baran, B. (2015, October). Performance metrics in multi-objective optimization. In 2015 Latin American Computing Conference (CLEI) (pp. 1-11). IEEE.
Samanlioglu, F. (2013). A multi-objective mathematical model for the industrial hazardous waste location-routing problem. European Journal of Operational Research, 226(2), 332-340.
Sarpong, B. M., Artigues, C., & Jozefowiez, N. (2013, September). Column generation for bi-objective vehicle routing problems with a min-max objective. In ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems-2013 (Vol. 33, pp. 137-149). Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik.
Schwarze, S., & Voß, S. (2013). Improved load balancing and resource utilization for the skill vehicle routing problem. Optimization Letters, 7(8), 1805-1823.
Silva, M. M., Subramanian, A., Vidal, T., & Ochi, L. S. (2012). A simple and effective metaheuristic for the minimum latency problem. European Journal of Operational Research, 221(3), 513-520.
Subramanian, A., Ochi, L. S., & Cabral, L. D. A. F. (2008). An Efficient Iterated Local Search Algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Proc. of the XL SBPO (CD-ROM), 1569-1580.
Sun, Y., Liang, Y., Zhang, Z., & Wang, J. (2017, June). M-NSGA-II: A memetic algorithm for vehicle routing problem with route balancing. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (pp. 61-71). Springer, Cham.
Tian, Y., Cheng, R., Zhang, X., & Jin, Y. (2017). PlatEMO: A MATLAB platform for evolutionary multi-objective optimization [educational forum]. IEEE Computational Intelligence Magazine, 12(4), 73-87.
Trivedi, A., Srinivasan, D., Sanyal, K., & Ghosh, A. (2016). A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Transactions on Evolutionary Computation, 21(3), 440-462.
Wang, Z., Zhang, Q., Gong, M., & Zhou, A. (2014, July). A replacement strategy for balancing convergence and diversity in MOEA/D. In 2014 IEEE Congress on Evolutionary Computation (CEC) (pp. 2132-2139). IEEE.
Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6), 712-731.
Zhou, A., & Zhang, Q. (2015). Are all the subproblems equally important? Resource allocation in decomposition-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 20(1), 52-64.
Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 3(4), 257-271.