A new MILP model for vehicle routing-loading problem under fragility, LIFO, and rotation constraints

Document Type : Original Article

Authors

Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran

Abstract

Simultaneous optimization of vehicle routing and loading decisions in three-dimensional case is one of the important problems in logistics and has received great attention from researchers. To the best of our knowledge, optimization models presented in the literature for this problem either are too complicated or do not include important loading assumptions such as item fragility, last-in-first-out arrangement, and the possibility of rotation. To overcome the shortcoming of the existing models, in this paper, we present a novel mixed-integer linear programming (MILP) model which not only involves important loading assumptions, but also does not have the complexity of previous models. Moreover, we provide valid inequalities to strengthen the LP relaxation bound and accelerate the solution process. Further, we show that how a restricted version of our model can be incorporated in loading procedures of meta-heuristic algorithms to improve their efficiency. Computational results over instances, taken from the literature, show the performance of the proposed approach

Keywords

Main Subjects

References

[1] B. Abdoli, S. A. MirHassani, and F. Hooshmand, Hooshmand, f. model and algorithm for bi-fuel vehicle routing problem to reduce ghg emissions, Environ. Sci. Pollut. Res., 24 (2017), pp. 21610–21624.
[2] A. Ayough, B. Khorshidvand, N. Massomnedjad, and A. Motameni, An integrated approach for threedimensional capacitated vehicle routing problem considering time windows, J. Model. Manag., (2020).
[3] R. Baldacci, A. Mingozzi, and R. Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, European J. Oper. Res., 218 (2012), pp. 1–6.
[4] A. Bortfeldt, A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints, Comput. Oper. Res., 39 (2012), pp. 2248–2257.
[5] A. Bortfeldt and J. Homberger, Packing first, routing second—a heuristic for the vehicle routing and loading problem, Comput. Oper. Res., 40 (2013), pp. 873–885.
[6] A. Bortfeldt and G. Wascher ¨ , Constraints in container loading–a state-of-the-art review, Euro. J. Oper. Res., 229 (2013), pp. 1–20.
[7] K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Comput. Ind. Eng., 99 (2016), pp. 300–313.
[8] S. Ceschia, A. Schaerf, and T. Stutzle ¨ , Local search techniques for a routing-packing problem, Comput. Ind. Eng., 66 (2013), pp. 1138–1149.
[9] O. Dominguez, A. A. Juan, and J. Faulin, A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations, Int. Trans. Oper. Res., 21 (2014), pp. 375–398.
[10] R. Elshaer and H. Awad, A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants, Comput. Ind. Eng., 140 (2020), p. 106242.
[11] G. Fuellerer, K. F. Doerner, R. F. Hartl, and M. Iori, Metaheuristics for vehicle routing problems with three-dimensional loading constraints, Central Euro. J. Oper. Res., 201 (2010), pp. 751–759.
[12] M. Gendreau, M. Iori, G. Laporte, and S. Martello, A tabu search algorithm for a routing and container loading problem, Transportation Science, 40 (2006), pp. 342–350.
[13] F. Hooshmand and S. A. MirHassani, Time dependent green vrp with alternative fuel powered vehicles, Energy Systems, 10 (2019), pp. 721–756. [
14] R. P. Hornstra, A. Silva, K. J. Roodbergen, and L. C. Coelho, The vehicle routing problem with simultaneous pickup and delivery and handling costs, Comput. Oper. Res., 115 (2020), pp. 104858, 20.
[15] M. Iori, J.-J. Salazar-Gonzalez, and D. Vigo ´ , An exact approach for the vehicle routing problem with two-dimensional loading constraints, Transportation science, 41 (2007), pp. 253–264.
[16] L. Junqueira, J. F. Oliveira, M. A. Carravilla, and R. Morabito, An optimization model for the vehicle routing problem with practical three-dimensional loading constraints, Int. Trans. Oper. Res., 20 (2013), pp. 645–666. [17] S. Khebbache-Hadji, C. Prins, A. Yalaoui, and M. Reghioui, Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows, Central Euro. J. Oper. Res., 21 (2013), pp. 307–336.
[18] C. Krebs and J. F. Ehmke, Axle weights in combined vehicle routing and container loading problems, EURO J. Transp. Logist., 10 (2021), p. 100043.
[19] C. Krebs, J. F. Ehmke, and H. Koch, Advanced loading constraints for 3d vehicle routing problems, OR Spectrum, 43 (2021), pp. 835–875.
[20] S. C. Leung, Z. Zhang, D. Zhang, X. Hua, and M. K. Lim, A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints, Eur. J. Oper. Res., 225 (2013), pp. 199– 210.
[21] S. C. Leung, X. Zhou, D. Zhang, and J. Zheng, Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem, Comput. Oper. Res., 38 (2011), pp. 205–215.
[22] L. Mart´ınez and C.-A. Amaya, A vehicle routing problem with multi-trips and time windows for circular items, J. Oper. Res. Soc., 64 (2013), pp. 1630–1643.
[23] L. Miao, Q. Ruan, K. Woghiren, and Q. Ruo, A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints, RAIRO-Operations Research, 46 (2012), pp. 63–82.
[24] S. A. MirHassani and F. Hooshmand, Methods and models in mathematical programming, Springer, 2019.
[25] A. Moura, A model-based heuristic to the vehicle routing and loading problem, Int. Trans. Oper. Res., 26 (2019), pp. 888–907.
[26] A. Moura and J. F. Oliveira, An integrated approach to the vehicle routing and container loading problems, OR spectrum, 31 (2009), pp. 775–800.
[27] H. Pollaris, K. Braekers, A. Caris, G. K. Janssens, and S. Limbourg, Vehicle routing problems with loading constraints: state-of-the-art and future directions, OR Spectrum, 37 (2015), pp. 297–330.
[28] Q. Ruan, Z. Zhang, L. Miao, and H. Shen, A hybrid approach for the vehicle routing problem with three-dimensional loading constraints, Comput. Oper. Res., 40 (2013), pp. 1579–1589.
[29] Y. Tao and F. Wang, An effective tabu search approach with improved loading algorithms for the 3l-cvrp, Comput. Oper. Res., 55 (2015), pp. 127–140.
[30] C. D. Tarantilis, E. E. Zachariadis, and C. T. Kiranoudis, A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem, IEEE Trans. Intell. Transp. Syst., 10 (2009), pp. 255–271.
[31] C. A. Vega-Mej´ıa, J. R. Montoya-Torres, and S. M. Islam, A nonlinear optimization model for the balanced vehicle routing problem with loading constraints, Int. Trans. Oper. Res., 26 (2019), pp. 794–835.
[32] E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, Integrated distribution and loading planning via a compact metaheuristic algorithm, Eur. J. Oper. Res., 228 (2013), pp. 56–71.
[33] W. Zhu, H. Qin, A. Lim, and L. Wang, A two-stage tabu search algorithm with enhanced packing heuristics for the 3l-cvrp and m3l-cvrp, Comput. Oper. Res., 39 (2012), pp. 2178–2195.
AUT Journal of Mathematics and Computing
Volume 4, Issue 2
March 2023
Pages 205-218

Files

Share

How to cite

Statistics