IDEAS home Printed from https://ideas.repec.org/p/jgu/wpaper/1823.html
   My bibliography  Save this paper

On Testing Capacity Constraints in Pickup-and-Delivery Problems with Trailers in Amortized Constant Time

Author

Listed:
  • Michael Drexl

    (Deggendorf Institute of Technology, Johannes Gutenberg University Mainz)

Abstract

Ef?cient feasibility tests are important in many heuristics for routing problems. This paper considers several variants of pickup-and-delivery problems with trailers. Its contribution consists in the description of amortized constant-time procedures for testing observance of capacity constraints when inserting tasks into routes. It is demonstrated that the presence of vehicles with detachable trailers makes capacity feasibility tests considerably more involved.

Suggested Citation

  • Michael Drexl, 2018. "On Testing Capacity Constraints in Pickup-and-Delivery Problems with Trailers in Amortized Constant Time," Working Papers 1823, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    • Handle: RePEc:jgu:wpaper:1823
    as

    Download full text from publisher

    File URL: https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1823.pdf
    File Function: First version, 2018
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Grangier, Philippe & Gendreau, Michel & Lehuédé, Fabien & Rousseau, Louis-Martin, 2016. "An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization," European Journal of Operational Research, Elsevier, vol. 254(1), pages 80-91.
    3. Savelsbergh, M. W. P., 1990. "An efficient implementation of local search algorithms for constrained routing problems," European Journal of Operational Research, Elsevier, vol. 47(1), pages 75-85, July.
    4. Ropke, Stefan & Pisinger, David, 2006. "A unified heuristic for a large class of Vehicle Routing Problems with Backhauls," European Journal of Operational Research, Elsevier, vol. 171(3), pages 750-775, June.
    5. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    6. Cheung, Raymond K. & Shi, Ning & Powell, Warren B. & Simao, Hugo P., 2008. "An attribute-decision model for cross-border drayage problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(2), pages 217-234, March.
    7. Michael Drexl, 2018. "On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers," Working Papers 1816, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    9. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    10. 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.
    11. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    12. S. Irnich, 2008. "A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 270-287, May.
    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. Michael Drexl, 2018. "On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers," Working Papers 1816, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    2. Michael Drexl, 2021. "On efficient testing of capacity constraints in pickup-and-delivery problems with trailers," 4OR, Springer, vol. 19(2), pages 289-307, June.
    3. Michael Drexl, 2021. "On the one-to-one pickup-and-delivery problem with time windows and trailers," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(3), pages 1115-1162, September.
    4. Michael Drexl, 2014. "A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints," Working Papers 1412, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 04 Nov 2014.
    5. 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.
    6. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    7. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    8. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    9. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    10. Rist, Yannik & Tilk, Christian & Forbes, Michael, 2024. "Benders Decomposition with Delayed Disaggregation for the Active Passive Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 318(3), pages 836-850.
    11. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    12. Neves-Moreira, F. & Amorim, P. & Guimarães, L. & Almada-Lobo, B., 2016. "A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations," European Journal of Operational Research, Elsevier, vol. 248(2), pages 487-506.
    13. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 248(1), pages 33-51.
    14. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    15. Timo Gschwind & Michael Drexl, 2019. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 53(2), pages 480-491, March.
    16. Yue Lu & Maoxiang Lang & Xueqiao Yu & Shiqi Li, 2019. "A Sustainable Multimodal Transport System: The Two-Echelon Location-Routing Problem with Consolidation in the Euro–China Expressway," Sustainability, MDPI, vol. 11(19), pages 1-25, October.
    17. Timo Gschwind & Michael Drexl, 2016. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Working Papers 1624, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    18. Christian Tilk & Nicola Bianchessi & Michael Drexl & Stefan Irnich & Frank Meisel, 2015. "Branch-and-Price for the Active-Passive Vehicle-Routing Problem," Working Papers 1513, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    19. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    20. 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.

    More about this item

    Keywords

    Pickup-and-Delivery; Trailers; Constant-Time Feasibility Test;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:jgu:wpaper:1823. 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: Research Unit IPP (email available below). General contact details of provider: https://edirc.repec.org/data/vlmaide.html .

    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.