IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v178y2023ics0191261523001601.html
   My bibliography  Save this article

A branch-price-and-cut algorithm for the local container drayage problem with controllable vehicle interference

Author

Listed:
  • Wang, Naiyu
  • Meng, Qiang
  • Zhang, Canrong

Abstract

This paper investigates a local container drayage problem with controllable vehicle interference (LCDP&CVI) under the tractor-and-trailer separation mode in which a tractor can be coupled or decoupled with a trailer at a customer location or a terminal. The container drayage requests proposed by customers should be fulfilled by a set of vehicle fleets, and each vehicle fleet comprises of a certain number of tractors and trailers that should be matched to each other. The controllable vehicle interference (CVI) means that the routes of any tractors from different vehicle fleets are independent of each other, implying that the interference between tractors is restricted only to the tractors from the same vehicle fleets. A mixed-integer linear programming (MILP) model is proposed for the LCDP&CVI. To exactly solve the problem, we develop a branch-price-and-cut algorithm based on the reformation of the MILP model, including a master problem and a pricing sub-problem. The pricing sub-problem that deals with the temporal synchronization constraints is formulated as the multi-vehicle shortest path problem with interference. By adding the tractor to the temporal-spatial network, a new representation of the pricing sub-problem is constructed, which enables us to solve the sub-problem by the multi-label method. In addition, the symmetrical elimination and dominance rules are incorporated into the multi-label method to enhance its effectiveness. Extensive numerical experiments are conducted to validate the proposed model and solution algorithm. For small-scale instances, the proposed solution algorithm is able to solve instances with up to 24 requests to optimality within two hours, which outperforms significantly the commercial MILP solver in terms of efficiency and effectiveness. For large-scale instances, the proposed algorithm can yield competitive solutions that are superior to the heuristic algorithms reported in the literature. Our experimental results also show that the controllable vehicle mechanism can strike a good balance between computational efficiency and operational costs by meticulously designing the structure of vehicle fleets.

Suggested Citation

  • Wang, Naiyu & Meng, Qiang & Zhang, Canrong, 2023. "A branch-price-and-cut algorithm for the local container drayage problem with controllable vehicle interference," Transportation Research Part B: Methodological, Elsevier, vol. 178(C).
    • Handle: RePEc:eee:transb:v:178:y:2023:i:c:s0191261523001601
    DOI: 10.1016/j.trb.2023.102835
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261523001601
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2023.102835?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. Namboothiri, Rajeev & Erera, Alan L., 2008. "Planning local container drayage operations given a port access appointment system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(2), pages 185-202, March.
    2. Xue, Zhaojie & Zhang, Canrong & Lin, Wei-Hua & Miao, Lixin & Yang, Peng, 2014. "A tabu search heuristic for the local container drayage problem under a new operation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 136-150.
    3. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    4. Imai, Akio & Nishimura, Etsuko & Current, John, 2007. "A Lagrangian relaxation-based heuristic for the vehicle routing with full container load," European Journal of Operational Research, Elsevier, vol. 176(1), pages 87-105, January.
    5. Yanzhi Li & Andrew Lim & Brian Rodrigues, 2005. "Manpower allocation with time windows and job‐teaming constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 302-311, June.
    6. Xue, Zhaojie & Lin, Hui & You, Jintao, 2021. "Local container drayage problem with truck platooning mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    7. Zhang, Ruiyou & Yun, Won Young & Moon, Ilkyeong, 2009. "A reactive tabu search algorithm for the multi-depot container truck transportation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(6), pages 904-914, November.
    8. Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
    9. Claudia Archetti & M. Grazia Speranza & Martin W. P. Savelsbergh, 2008. "An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 42(1), pages 22-31, February.
    10. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    11. You, Jintao & Miao, Lixin & Zhang, Canrong & Xue, Zhaojie, 2020. "A generic model for the local container drayage problem using the emerging truck platooning operation mode," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 181-209.
    12. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    13. Jula, Hossein & Dessouky, Maged & Ioannou, Petros & Chassiakos, Anastasios, 2005. "Container movement by trucks in metropolitan networks: modeling and optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 41(3), pages 235-259, May.
    14. Zhang, Ruiyou & Yun, Won Young & Moon, Il Kyeong, 2011. "Modeling and optimization of a container drayage problem with resource constraints," International Journal of Production Economics, Elsevier, vol. 133(1), pages 351-359, September.
    15. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2018. "Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem," Transportation Science, INFORMS, vol. 52(2), pages 300-319, March.
    16. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    17. Song, Yujian & Zhang, Jiantong & Liang, Zhe & Ye, Chunming, 2017. "An exact algorithm for the container drayage problem under a separation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 231-254.
    18. Moshe Dror, 1994. "Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW," Operations Research, INFORMS, vol. 42(5), pages 977-978, October.
    19. Zhixing Luo & Hu Qin & Wenbin Zhu & Andrew Lim, 2016. "Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 138-171, March.
    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. Bustos-Coral, Daniel & Costa, Alysson M., 2022. "Drayage routing with heterogeneous fleet, compatibility constraints, and truck load configurations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    2. Song, Yujian & Zhang, Jiantong & Liang, Zhe & Ye, Chunming, 2017. "An exact algorithm for the container drayage problem under a separation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 231-254.
    3. Chen, Rui & Meng, Qiang & Jia, Peng, 2022. "Container port drayage operations and management: Past and future," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    4. Chen, Rui & Jia, Shuai & Meng, Qiang, 2023. "Dynamic container drayage booking and routing decision support approach for E-commerce platforms," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    5. Benantar, A. & Abourraja, M.N. & Boukachour, J. & Boudebous, D. & Duvallet, C., 2020. "On the integration of container availability constraints into daily drayage operations arising in France: Modelling and optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    6. Escudero-Santana, Alejandro & Muñuzuri, Jesús & Cortés, Pablo & Onieva, Luis, 2021. "The one container drayage problem with soft time windows," Research in Transportation Economics, Elsevier, vol. 90(C).
    7. Yujian Song & Yuting Zhang & Wanli Wang & Ming Xue, 2023. "A Branch and Price Algorithm for the Drop-and-Pickup Container Drayage Problem with Empty Container Constraints," Sustainability, MDPI, vol. 15(7), pages 1-28, March.
    8. Cui, Haipeng & Chen, Shukai & Chen, Rui & Meng, Qiang, 2022. "A two-stage hybrid heuristic solution for the container drayage problem with trailer reposition," European Journal of Operational Research, Elsevier, vol. 299(2), pages 468-482.
    9. You, Jintao & Miao, Lixin & Zhang, Canrong & Xue, Zhaojie, 2020. "A generic model for the local container drayage problem using the emerging truck platooning operation mode," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 181-209.
    10. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    11. Shiri, Samaneh & Huynh, Nathan, 2016. "Optimization of drayage operations with time-window constraints," International Journal of Production Economics, Elsevier, vol. 176(C), pages 7-20.
    12. You, Jintao & Wang, Yuan & Xue, Zhaojie, 2023. "An exact algorithm for the multi-trip container drayage problem with truck platooning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    13. Xue, Zhaojie & Zhang, Canrong & Lin, Wei-Hua & Miao, Lixin & Yang, Peng, 2014. "A tabu search heuristic for the local container drayage problem under a new operation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 136-150.
    14. Yan, Xiaoyuan & Xu, Min & Xie, Chi, 2023. "Local container drayage problem with improved truck platooning operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    15. Jia, Shuai & Cui, Haipeng & Chen, Rui & Meng, Qiang, 2022. "Dynamic container drayage with uncertain request arrival times and service time windows," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 237-258.
    16. Xue, Zhaojie & Lin, Hui & You, Jintao, 2021. "Local container drayage problem with truck platooning mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    17. Chen, Rui & Chen, Shukai & Cui, Haipeng & Meng, Qiang, 2021. "The container drayage problem for heterogeneous trucks with multiple loads: A revisit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    18. Soares, Ricardo & Marques, Alexandra & Amorim, Pedro & Parragh, Sophie N., 2024. "Synchronisation in vehicle routing: Classification schema, modelling framework and literature review," European Journal of Operational Research, Elsevier, vol. 313(3), pages 817-840.
    19. Tilk, Christian & Drexl, Michael & Irnich, Stefan, 2019. "Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies," European Journal of Operational Research, Elsevier, vol. 276(2), pages 549-565.
    20. Zhang, Ruiyou & Lu, Jye-Chyi & Wang, Dingwei, 2014. "Container drayage problem with flexible orders and its near real-time solution strategies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 235-251.

    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:transb:v:178:y:2023:i:c:s0191261523001601. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.