IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v306y2023i3p1219-1235.html
   My bibliography  Save this article

Modelling and heuristically solving many-to-many heterogeneous vehicle routing problem with cross-docking and two-dimensional loading constraints

Author

Listed:
  • Ji, Bin
  • Zhang, Zheng
  • Yu, Samson S.
  • Zhou, Saiqi
  • Wu, Guohua

Abstract

In light of the existing practical applications of the two-dimensional loading on vehicle scheduling and many-to-many supply-demand relationships between suppliers and customers, we address a many-to-many heterogeneous vehicle routing problem with cross-docking and two-dimensional loading constraints (or the heterogeneous 2L-MVRPCD). The newly proposed problem can be regarded as a generalized problem of the many-to-many vehicle routing with cross-docking (MVRPCD) and capacitated vehicle routing problem with two-dimensional loading constraints (2L-CVRP). To solve small-scale 2L-MVRPCDs, a mixed integer linear programming (MILP) model is developed, whereas two hybrid optimization heuristic algorithms are proposed to solve large-scale 2L-MVRPCDs. The first heuristic incorporates a basic adaptive large neighborhood search (ALNS) algorithm and a new best-fit-skyline (BFS) packing heuristic, while the second heuristic, a Tabu-based ALNS (ALNS/TS), extends the first one by embedding an insert-tabu strategy to enhance the intensity and diversity of search. Wide-ranging instances with various many-to-many supply-demand scenarios and different loading configurations are employed to verify the efficacy of the proposed MILP model and two heuristics. Numerical results show that small-scale heterogeneous 2L-MVRPCD instances with and without the rotation constraints can be solved to optimality by commercial solvers, and the proposed heuristics can achieve high-quality solutions within a reasonable computational time for large-scale instances. Meanwhile, the comparison between the proposed heuristics and existing methods verifies the effectiveness and applicability of the proposed heuristics for solving MVRPCD and 2L-CVRP.

Suggested Citation

  • Ji, Bin & Zhang, Zheng & Yu, Samson S. & Zhou, Saiqi & Wu, Guohua, 2023. "Modelling and heuristically solving many-to-many heterogeneous vehicle routing problem with cross-docking and two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1219-1235.
    • Handle: RePEc:eee:ejores:v:306:y:2023:i:3:p:1219-1235
    DOI: 10.1016/j.ejor.2022.08.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722006440
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.08.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    2. Xianlong Ge & Ziqiang Zhu & Yuanzhi Jin, 2020. "Electric Vehicle Routing Problems with Stochastic Demands and Dynamic Remedial Measures," Mathematical Problems in Engineering, Hindawi, vol. 2020, pages 1-15, August.
    3. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    4. Abeysooriya, Ranga P. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2018. "Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation," International Journal of Production Economics, Elsevier, vol. 195(C), pages 12-26.
    5. Alonso, M.T. & Martinez-Sykora, A. & Alvarez-Valdes, R. & Parreño, F., 2022. "The pallet-loading vehicle routing problem with stability constraints," European Journal of Operational Research, Elsevier, vol. 302(3), pages 860-873.
    6. Oscar L Domínguez Rivero & Angel A Juan Pérez & Ignacio A de la Nuez Pestana & Djamila Ouelhadj, 2016. "An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(1), pages 37-53, January.
    7. Oscar Dominguez & Angel Juan & Barry Barrios & Javier Faulin & Alba Agustin, 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet," Annals of Operations Research, Springer, vol. 236(2), pages 383-404, January.
    8. Yücel, Eda & Salman, F. Sibel & Erdoğan, Güneş, 2022. "Optimizing two-dimensional vehicle loading and dispatching decisions in freight logistics," European Journal of Operational Research, Elsevier, vol. 302(3), pages 954-969.
    9. Manuel Iori & Juan-José Salazar-González & Daniele Vigo, 2007. "An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints," Transportation Science, INFORMS, vol. 41(2), pages 253-264, May.
    10. Drexl, Michael, 2013. "Applications of the vehicle routing problem with trailers and transshipments," European Journal of Operational Research, Elsevier, vol. 227(2), pages 275-283.
    11. Oscar Dominguez & Angel A. Juan & Barry Barrios & Javier Faulin & Alba Agustin, 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet," Annals of Operations Research, Springer, vol. 236(2), pages 383-404, January.
    12. Coindreau, Marc-Antoine & Gallay, Olivier & Zufferey, Nicolas & Laporte, Gilbert, 2021. "Inbound and outbound flow integration for cross-docking operations," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1153-1163.
    13. Gelareh, Shahin & Glover, Fred & Guemri, Oualid & Hanafi, Saïd & Nduwayo, Placide & Todosijević, Raca, 2020. "A comparative study of formulations for a cross-dock door assignment problem," Omega, Elsevier, vol. 91(C).
    14. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    15. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Christos T., 2009. "A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 195(3), pages 729-743, June.
    16. Chrysanthos E. Gounaris & Panagiotis P. Repoussis & Christos D. Tarantilis & Wolfram Wiesemann & Christodoulos A. Floudas, 2016. "An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem," Transportation Science, INFORMS, vol. 50(4), pages 1239-1260, November.
    17. Ji, Bin & Yuan, Xiaohui & Yuan, Yanbin & Lei, Xiaohui & Fernando, Tyrone & Iu, Herbert H.C., 2019. "Exact and heuristic methods for optimizing lock-quay system in inland waterway," European Journal of Operational Research, Elsevier, vol. 277(2), pages 740-755.
    18. M Wen & J Larsen & J Clausen & J-F Cordeau & G Laporte, 2009. "Vehicle routing with cross-docking," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1708-1718, December.
    19. Leung, Stephen C.H. & Zhang, Zhenzhen & Zhang, Defu & Hua, Xian & Lim, Ming K., 2013. "A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 225(2), pages 199-210.
    20. Zhang, Xiangyi & Chen, Lu & Gendreau, Michel & Langevin, André, 2022. "A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 302(1), pages 259-269.
    21. Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2020. "The Vehicle Routing Problem with Stochastic Two-Dimensional Items," Transportation Science, INFORMS, vol. 54(2), pages 453-469, March.
    22. E. K. Burke & G. Kendall & G. Whitwell, 2004. "A New Placement Heuristic for the Orthogonal Stock-Cutting Problem," Operations Research, INFORMS, vol. 52(4), pages 655-671, August.
    23. Peter C. Schuur, 1997. "Classification of Acceptance Criteria for the Simulated Annealing Algorithm," Mathematics of Operations Research, INFORMS, vol. 22(2), pages 266-275, May.
    24. Gaudioso, Manlio & Monaco, Maria Flavia & Sammarra, Marcello, 2021. "A Lagrangian heuristics for the truck scheduling problem in multi-door, multi-product Cross-Docking with constant processing time," Omega, Elsevier, vol. 101(C).
    25. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2011. "A skyline heuristic for the 2D rectangular packing and strip packing problems," European Journal of Operational Research, Elsevier, vol. 215(2), pages 337-346, December.
    26. Philippe Grangier & Michel Gendreau & Fabien Lehuédé & Louis-Martin Rousseau, 2021. "The vehicle routing problem with cross-docking and resource constraints," Journal of Heuristics, Springer, vol. 27(1), pages 31-61, April.
    27. Sayed Ibrahim Sayed & Ivan Contreras & Juan A. Diaz & Dolores E. Luna, 2020. "Integrated cross-dock door assignment and truck scheduling with handling times," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 705-727, October.
    28. Ladier, Anne-Laure & Alpan, Gülgün, 2016. "Cross-docking operations: Current research versus industry practice," Omega, Elsevier, vol. 62(C), pages 145-162.
    29. Jie Zhang & Yifan Zhu & Xiaobo Li & Mengjun Ming & Weiping Wang & Tao Wang, 2022. "Multi-Trip Time-Dependent Vehicle Routing Problem with Split Delivery," Mathematics, MDPI, vol. 10(19), pages 1-24, September.
    30. Amalia I. Nikolopoulou & Panagiotis P. Repoussis & Christos D. Tarantilis & Emmanouil E. Zachariadis, 2019. "Adaptive memory programming for the many-to-many vehicle routing problem with cross-docking," Operational Research, Springer, vol. 19(1), pages 1-38, March.
    31. Repoussis, Panagiotis P. & Tarantilis, Christos D. & Zachariadis, Emmanouil E., 2017. "Moving products between location pairs: Cross-docking versus direct-shippingAuthor-Name: Nikolopoulou, Amalia I," European Journal of Operational Research, Elsevier, vol. 256(3), pages 803-819.
    32. Chen, Cheng & Demir, Emrah & Huang, Yuan, 2021. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1164-1180.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    2. Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2020. "The Vehicle Routing Problem with Stochastic Two-Dimensional Items," Transportation Science, INFORMS, vol. 54(2), pages 453-469, March.
    3. Wei, Lijun & Zhang, Zhenzhen & Zhang, Defu & Leung, Stephen C.H., 2018. "A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 265(3), pages 843-859.
    4. Zhang, Xiangyi & Chen, Lu & Gendreau, Michel & Langevin, André, 2022. "A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 302(1), pages 259-269.
    5. Côté, J.F. & Guastaroba, G. & Speranza, M.G., 2017. "The value of integrating loading and routing," European Journal of Operational Research, Elsevier, vol. 257(1), pages 89-105.
    6. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    7. Zheng Zhang & Bin Ji & Samson S. Yu, 2023. "An Adaptive Tabu Search Algorithm for Solving the Two-Dimensional Loading Constrained Vehicle Routing Problem with Stochastic Customers," Sustainability, MDPI, vol. 15(2), pages 1-23, January.
    8. Xiang Song & Dylan Jones & Nasrin Asgari & Tim Pigden, 2020. "Multi-objective vehicle routing and loading with time window constraints: a real-life application," Annals of Operations Research, Springer, vol. 291(1), pages 799-825, August.
    9. Mahdi Alinaghian & Komail Zamanlou & Mohammad S. Sabbagh, 2017. "A bi-objective mathematical model for two-dimensional loading time-dependent vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1422-1441, November.
    10. İlker Küçükoğlu & Nursel Öztürk, 2019. "A hybrid meta-heuristic algorithm for vehicle routing and packing problem with cross-docking," Journal of Intelligent Manufacturing, Springer, vol. 30(8), pages 2927-2943, December.
    11. Oscar Dominguez & Angel Juan & Barry Barrios & Javier Faulin & Alba Agustin, 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet," Annals of Operations Research, Springer, vol. 236(2), pages 383-404, January.
    12. Oscar Dominguez & Angel A. Juan & Barry Barrios & Javier Faulin & Alba Agustin, 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet," Annals of Operations Research, Springer, vol. 236(2), pages 383-404, January.
    13. Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2014. "An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints," Operations Research, INFORMS, vol. 62(5), pages 1126-1141, October.
    14. Wei, Lijun & Zhang, Zhenzhen & Zhang, Defu & Lim, Andrew, 2015. "A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 243(3), pages 798-814.
    15. Yücel, Eda & Salman, F. Sibel & Erdoğan, Güneş, 2022. "Optimizing two-dimensional vehicle loading and dispatching decisions in freight logistics," European Journal of Operational Research, Elsevier, vol. 302(3), pages 954-969.
    16. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    17. Yu, Vincent F. & Anh, Pham Tuan & Baldacci, Roberto, 2023. "A robust optimization approach for the vehicle routing problem with cross-docking under demand uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    18. Vanajakumari, Manoj & Sun, Haoying & Jones, Ashley & Sriskandarajah, Chelliah, 2022. "Supply chain planning: A case for Hybrid Cross-Docks," Omega, Elsevier, vol. 108(C).
    19. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    20. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:306:y:2023:i:3:p:1219-1235. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.