A specialized genetic algorithm for the fuel consumption heterogeneous fleet vehicle routing problem with bidimensional packing constraints

Escobar-Falcón, L.; Álvarez-Martínez, D.; Wilmer-Escobar, J.; Granada-Echeverri, M.

doi:10.5267/j.ijiec.2020.11.003

Abstract: The vehicle routing problem combined with loading of goods, considering the reduction of fuel consumption, aims at finding the set of routes that will serve the demands of the customers, arguing that the fuel consumption is directly related to the weight of the load in the paths that compose the routes. This study integrates the Fuel Consumption Heterogeneous Vehicle Routing Problem with Two-Dimensional Loading Constraints (2L-FHFVRP). To reduce fuel consumption taking the associated environmental impact into account is a classical VRP variant that has gained increasing attention in the last decade. The objective of this problem is to design the delivery routes to satisfy the customers’ demands with the lowest possible fuel consumption, which depends on the distances of the paths, the assigned vehicles, the loading/unloading pattern and the load weight. In the vehicle routing problem literature, the approximate algorithms have had great success, especially the evolutionary ones, which appear in previous works with quite a sophisticated structure, obtaining excellent results, but that are difficult to implement and adapt to other variants such as the one proposed here. In this study, we present a specialized genetic algorithm to solve the design of routes, keeping its main characteristic: the easy implementation. By contrast, the loading of goods restriction is validated by means of a GRASP algorithm, which has been widely employed for solving packing problems. With a view of confirming the performance of the proposed methodology, we provide a computational study that uses all the available benchmark instances, allowing to illustrate the savings achieved in fuel consumption. In addition, the methodology suggested can be adapted to the version of solely minimizing the total distance traveled for serving the customers (without the fuel consumption) and it is compared to the best works presented in the literature. The computational results show that the methodology manages to be adequately adapted to this version and it is capable of finding improved solutions for some benchmark instances. As for future work, we propose to adjust the methodology to consider the three-dimensional loading problem so that it adapts to more real-life conditions of the industry.

How to cite this paper

 Escobar-Falcón, L., Álvarez-Martínez, D., Wilmer-Escobar, J & Granada-Echeverri, M. (2021). A specialized genetic algorithm for the fuel consumption heterogeneous fleet vehicle routing problem with bidimensional packing constraints.International Journal of Industrial Engineering Computations , 12(2), 191-204.

References

References

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows.
Alvarez-Martínez, D., Alvarez-Valdes, R., & Parreño, F. (2015). A GRASP algorithm for the container loading problem with multi-drop constraints. Pesquisa Operacional, 35(1), 1-24. https://dx.doi.org/10.1590/0101-7438.2015.035.01.0001
Beasley, J. E., & Chu, P. C. (1996). A genetic algorithm for the set covering problem. European Journal of Operational Research, 94(2), 392-404.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
Camacho, G. A., Alvarez, D., & Cuellar, D. (2018). Heuristic Approach For The Multiple Bin-Size Bin Packing Problem. IEEE Latin America Transactions, 16(2), 620-626.
Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group.
Côté, J. F., Guastaroba, G., & Speranza, M. G. (2017). The value of integrating loading and routing. European Journal of Operational Research, 257(1), 89-105.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Demir, E., Bektaş, T., & Laporte, G. (2014). A review of recent research on green road freight transportation. European Journal of Operational Research, 237(3), 775-793.
Dominguez, O., Juan, A. A., Barrios, B., Faulin, J., & Agustin, A. (2016). Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet. Annals of Operations Research, 236(2), 383-404.
Domínguez Rivero, O. L., Juan Pérez, A. A., de la Nuez Pestana, I. A., & Ouelhadj, D. (2016). An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation. Journal of the Operational Research Society, 67(1), 37-53.
Escobar, L. M., Martínez, D. Á., Escobar, J. W., Linfati, R., & Mauricio, G. E. (2015, October). A hybrid metaheuristic approach for the capacitated vehicle routing problem with container loading constraints. In 2015 International Conference on Industrial Engineering and Systems Management (IESM) (pp. 1374-1382). IEEE.
Escobar-Falcón, L. M., Álvarez-Martínez, D., Granada-Echeverri, M., Escobar, J. W., & Romero-Lázaro, R. A. (2016). A matheuristic algorithm for the three-dimensional loading capacitated vehicle routing problem (3L-CVRP). Revista Facultad de Ingeniería Universidad de Antioquia, 78, 09-20.
Feo, T. A., & Resende, M. G. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations research letters, 8(2), 67-71.
Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A tabu search algorithm for a routing and container loading problem. Transportation Science, 40(3), 342-350.
Guimarans, D., Domínguez, O., Juan, A. A., & Martínez, E. (2016). A multi-start simheuristic for the stochastictwo-dimensional vehicle routing problem. Proceedings of the 2016 Winter Simulation Conference (pp. 2326-2334). Piscataway: IEEEPress. https://doi.org/10.1109/WSC.2016.7822273
Guimarans, D., Dominguez, O., Panadero, J., & Juan, A. A. (2018). A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times. Simulation Modelling Practice and Theory, 89, 1-14.
Iori, M., Salazar-González, J. J., & Vigo, D. (2007). An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation science, 41(2), 253-264.
Iori, M., & Martello, S. (2013). An annotated bibliography of combined routing and loading problems. Yugoslav Journal of Operations Research, 23(3), 311-326(16).
Leung, S. C., Zhang, Z., Zhang, D., Hua, X., & Lim, M. K. (2013). A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. European Journal of Operational Research, 225(2), 199-210.
Liu, S., Huang, W., & Ma, H. (2009). An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E: Logistics and Transportation Review, 45(3), 434-445.
Micheli, G. J., & Mantella, F. (2018). Modelling an environmentally-extended inventory routing problem with demand uncertainty and a heterogeneous fleet under carbon control policies. International Journal of Production Economics, 204, 316-327.
Parreño, F., Alvarez-Valdés, R., Oliveira, J. F., & Tamarit, J. M. (2010). Neighborhood structures for the container loading problem: a VNS implementation. Journal of Heuristics, 16(1), 1-22.
Pollaris, H., Braekers, K., Caris, A., Janssens, G. K., & Limbourg, S. (2015). Vehicle routing problems with loading constraints: state-of-the-art and future directions.OR Spectrum, 37(2):297–330.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002.
Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519-2531.
Suzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and pollutants emission. Transportation Research Part D: Transport and Environment, 16(1), 73-77.
Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
Xiao, Y., Zhao, Q., Kaku, I., e Xu, Y. (2012). Development of a fuel consumption optimizationmodel for the capacitated vehicle routing problem.Computers & Operations Research, 39(7), 1419–1431.
Zhang, Z., Wei, L., & Lim, A. (2015). An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints. Transportation Research Part B: Methodological, 82, 20-35.