IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v73y2015icp114-132.html
   My bibliography  Save this article

An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport

Author

Listed:
  • Tang, Jiafu
  • Yu, Yang
  • Li, Jia

Abstract

Door-to-Door service of Pickup and Delivery of Customers to the Airport (D2PDCA) is a new service provided by certain Airline Ticket Sales Agencies (ATSAs) in China. This new service provides an attractive alternative way by picking up customer at this/her specified position and at any time he/she preferred and delivering to the airport more conveniently than airport shuttle and thus earn high customer service quality. Compared with the single-trip mode, the multi-trip mode of D2PDCA (MTM-D2PDCA) service can reduce travel distances, the number of vehicles required and the operating cost. To obtain the exact solution of the MTM-D2PDCA problem, we propose a novel, exact algorithm based on the trip-chain-oriented set-partitioning (TCO-SP) model, where a trip-chain represents multiple trips made by a specific vehicle. In the exact algorithm, we propose an improved label-correcting method to remove infeasible trip-chains quickly and thus speed the search process. Based on the feasible trip-chains, the MTM-D2PDCA problem is formulated as the novel TCO-SP model, which can be solved exactly by the optimization software CPLEX. In addition, we present several mathematical insights into the relationship between the number of trip-chains and the number of local optimal trips that are applicable in both theory and practice. Extensive experiments are conducted to illustrate the application of the model and demonstrate the cost savings of the MTM-D2PDCA mode over the single-trip mode and provide managerial insights into successfully operating a MTM-D2PDCA service.

Suggested Citation

  • Tang, Jiafu & Yu, Yang & Li, Jia, 2015. "An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 114-132.
  • Handle: RePEc:eee:transe:v:73:y:2015:i:c:p:114-132
    DOI: 10.1016/j.tre.2014.11.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554514001902
    Download Restriction: Full text for ScienceDirect subscribers only

    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. Liu, Shuguang & Huang, Weilai & Ma, Huiming, 2009. "An effective genetic algorithm for the fleet size and mix vehicle routing problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(3), pages 434-445, May.
    2. Desrochers, Martin & Soumis, Francois, 1988. "A reoptimization algorithm for the shortest path problem with time windows," European Journal of Operational Research, Elsevier, vol. 35(2), pages 242-254, May.
    3. Li, Jing-Quan & Mirchandani, Pitu B. & Borenstein, Denis, 2009. "A Lagrangian heuristic for the real-time vehicle rescheduling problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(3), pages 419-433, May.
    4. Gulczynski, Damon & Golden, Bruce & Wasil, Edward, 2010. "The split delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 612-626, September.
    5. Derigs, Ulrich & Kurowsky, René & Vogel, Ulrich, 2011. "Solving a real-world vehicle routing problem with multiple use of tractors and trailers and EU-regulations for drivers arising in air cargo road feeder services," European Journal of Operational Research, Elsevier, vol. 213(1), pages 309-319, August.
    6. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2007. "An exact algorithm for a single-vehicle routing problem with time windows and multiple routes," European Journal of Operational Research, Elsevier, vol. 178(3), pages 755-766, May.
    7. Zhong, Yingjie & Cole, Michael H., 2005. "A vehicle routing problem with backhauls and time windows: a guided local search solution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 41(2), pages 131-144, March.
    8. Qureshi, A.G. & Taniguchi, E. & Yamada, T., 2009. "An exact solution approach for vehicle routing and scheduling problems with soft time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(6), pages 960-977, November.
    9. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.
    10. Brandao, Jose & Mercer, Alan, 1997. "A tabu search algorithm for the multi-trip vehicle routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 100(1), pages 180-191, July.
    11. Yu, Bin & Yang, Zhong Zhen, 2011. "An ant colony optimization model: The period vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(2), pages 166-181, March.
    12. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    Full references (including those not matched with items on IDEAS)

    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:transe:v:73:y:2015:i:c:p:114-132. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.