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

The paired mail carrier problem

Author

Listed:
  • Luo, Yuchen
  • Golden, Bruce
  • Poikonen, Stefan
  • Wasil, Edward
  • Zhang, Rui

Abstract

Often traditional mail carrier models assume that one carrier is assigned to each truck. This carrier drives the truck according to a delivery route, gets out of the truck at a stop, and services customers using a walking loop. We introduce the Paired Mail Carrier Problem (PMCP), which allows for two mail carriers per truck. If at least one carrier is in the truck, the truck may move forward. Given two mail carriers per truck, the objective is to minimize the time from the start to the end of the route while ensuring that each service stop is fully serviced and obeys all feasibility constraints. We develop a mixed integer programming (MIP) formulation and two fast heuristics for the PMCP. The MIP formulation obtains optimal solutions for smaller instances within reasonable running times. Furthermore, we demonstrate that, in addition to being very efficient (running time is on the order of milliseconds, even for large instances), our heuristics are near-optimal (within 5% of optimality) on instances up to 80 stops. More importantly, we evaluate the impact of the paired mail carrier (PMC) setting on both a one-truck situation and a fleet (multiple trucks) situation, relative to the single mail carrier (SMC) setting. Overall, the PMC setting not only can accomplish over 50% extra work within the same shift hours but also can lead to 22% cost savings. Finally, we discuss an extension where we can have three or more mail carriers per truck.

Suggested Citation

  • Luo, Yuchen & Golden, Bruce & Poikonen, Stefan & Wasil, Edward & Zhang, Rui, 2023. "The paired mail carrier problem," European Journal of Operational Research, Elsevier, vol. 308(2), pages 801-817.
    • Handle: RePEc:eee:ejores:v:308:y:2023:i:2:p:801-817
    DOI: 10.1016/j.ejor.2022.11.032
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172200889X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.11.032?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. Pureza, Vitória & Morabito, Reinaldo & Reimann, Marc, 2012. "Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW," European Journal of Operational Research, Elsevier, vol. 218(3), pages 636-647.
    2. Coindreau, Marc-Antoine & Gallay, Olivier & Zufferey, Nicolas, 2019. "Vehicle routing with transportable resources: Using carpooling and walking for on-site services," European Journal of Operational Research, Elsevier, vol. 279(3), pages 996-1010.
    3. Dalla Chiara, Giacomo & Goodchild, Anne, 2020. "Do commercial vehicles cruise for parking? Empirical evidence from Seattle," Transport Policy, Elsevier, vol. 97(C), pages 26-36.
    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. Le Colleter, Théo & Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2023. "Small and large neighborhood search for the park-and-loop routing problem with parking selection," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1233-1248.
    2. Tscharaktschiew, Stefan & Reimann, Felix, 2021. "On employer-paid parking and parking (cash-out) policy: A formal synthesis of different perspectives," Transport Policy, Elsevier, vol. 110(C), pages 499-516.
    3. Abhishek, & Legros, Benjamin & Fransoo, Jan C., 2021. "Performance evaluation of stochastic systems with dedicated delivery bays and general on-street parking," Other publications TiSEM 09ed9572-d59c-4f28-a9c4-b, Tilburg University, School of Economics and Management.
    4. Zhang, Lele & Ding, Pengyuan & Thompson, Russell G., 2023. "A stochastic formulation of the two-echelon vehicle routing and loading bay reservation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    5. Narayanan, Santhanakrishnan & Antoniou, Constantinos, 2022. "Electric cargo cycles - A comprehensive review," Transport Policy, Elsevier, vol. 116(C), pages 278-303.
    6. 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.
    7. José Manuel Belenguer & Enrique Benavent & Antonio Martínez & Christian Prins & Caroline Prodhon & Juan G. Villegas, 2016. "A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots," Transportation Science, INFORMS, vol. 50(2), pages 735-749, May.
    8. Yu Liu & Shenle Pan & Pauline Folz & Fano Ramparany & Sébastien Bolle & Eric Ballot & Thierry Coupaye, 2022. "Connected Freight Parking in Smart City Logistics," Post-Print hal-03697724, HAL.
    9. Cruz-Daraviña, Paola Andrea & Bocarejo Suescún, Juan Pablo, 2021. "Freight operations in city centers: A land use conflict in urban planning," Land Use Policy, Elsevier, vol. 108(C).
    10. Amaya, Johanna & Encarnación, Trilce & Delgado-Lindeman, Maira, 2023. "Understanding Delivery Drivers’ Parking Preferences in Urban Freight Operations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 176(C).
    11. Majsa Ammouriova & Massimo Bertolini & Juliana Castaneda & Angel A. Juan & Mattia Neroni, 2022. "A Heuristic-Based Simulation for an Education Process to Learn about Optimization Applications in Logistics and Transportation," Mathematics, MDPI, vol. 10(5), pages 1-18, March.
    12. Iacobucci, Evan & McDonald, Noreen & Edwards, Charles H.W. & Steiner, Ruth, 2022. "Using social media to understand challenges faced by US urban parcel delivery drivers: Reports from the curb," Transport Policy, Elsevier, vol. 126(C), pages 96-106.
    13. Hagen, Tobias & Saki, Siavash & Scheel-Kopeinig, Sabine, 2021. "start2park - determining, explaining and predicting cruising for parking," Working Paper Series 20, Frankfurt University of Applied Sciences, Faculty of Business and Law.
    14. Ranjbari, Andisheh & Diehl, Caleb & Dalla Chiara, Giacomo & Goodchild, Anne, 2023. "Do parcel lockers reduce delivery times? Evidence from the field," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    15. Kadkhodaei, Masoud & Shad, Rouzbeh & Ziaee, Seyed Ali & Kadkhodaei, Mohsen, 2023. "Prediction model for drivers' tendency to perpetrate a double parking violation on urban trips," Transport Policy, Elsevier, vol. 141(C), pages 331-339.
    16. Kadkhodaei, Masoud & Shad, Rouzbeh & Ziaee, Seyed Ali, 2022. "Affecting factors of double parking violations on urban trips," Transport Policy, Elsevier, vol. 120(C), pages 80-88.
    17. Huang, Nan & Qin, Hu & Du, Yuquan & Wang, Li, 2024. "An exact algorithm for the multi-trip vehicle routing problem with time windows and multi-skilled manpower," European Journal of Operational Research, Elsevier, vol. 319(1), pages 31-49.
    18. Antonio Martinez-Sykora & Fraser McLeod & Carlos Lamas-Fernandez & Tolga Bektaş & Tom Cherrett & Julian Allen, 2020. "Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving," Annals of Operations Research, Springer, vol. 295(2), pages 645-693, December.
    19. Ali, Ousmane & Côté, Jean-François & Coelho, Leandro C., 2021. "Models and algorithms for the delivery and installation routing problem," European Journal of Operational Research, Elsevier, vol. 291(1), pages 162-177.
    20. Ramirez-Rios, Diana G. & Kalahasthi, Lokesh Kumar & Holguín-Veras, José, 2023. "On-street parking for freight, services, and e-commerce traffic in US cities: A simulation model incorporating demand and duration," Transportation Research Part A: Policy and Practice, Elsevier, vol. 169(C).

    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:308:y:2023:i:2:p:801-817. 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.