Advanced Search
MyIDEAS: Login

Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

Contents:

Author Info

  • Cheang, Brenda
  • Gao, Xiang
  • Lim, Andrew
  • Qin, Hu
  • Zhu, Wenbin
Registered author(s):

    Abstract

    We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712004742
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.

    Bibliographic Info

    Article provided by Elsevier in its journal European Journal of Operational Research.

    Volume (Year): 223 (2012)
    Issue (Month): 1 ()
    Pages: 60-75

    as in new window
    Handle: RePEc:eee:ejores:v:223:y:2012:i:1:p:60-75

    Contact details of provider:
    Web page: http://www.elsevier.com/locate/eor

    Related research

    Keywords: Traveling salesman; Pickup and delivery; Last-in-first-out loading; Distance constraint; Metaheuristic;

    References

    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
    as in new window
    1. Felipe, Angel & Teresa Ortuño, M. & Tirado, Gregorio, 2011. "Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints," European Journal of Operational Research, Elsevier, vol. 211(1), pages 66-75, May.
    2. Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
    3. Kalantari, Bahman & Hill, Arthur V. & Arora, Sant R., 1985. "An algorithm for the traveling salesman problem with pickup and delivery customers," European Journal of Operational Research, Elsevier, vol. 22(3), pages 377-386, December.
    4. Manuel Iori & Silvano Martello, 2010. "Rejoinder on: Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer, vol. 18(1), pages 41-42, July.
    5. R. K. Ahuja & J. B. Orlin & S. Pallottino & M. P. Scaparra & M. G. Scutellà, 2004. "A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem," Management Science, INFORMS, vol. 50(6), pages 749-760, June.
    6. Li, Yongquan & Lim, Andrew & Oon, Wee-Chong & Qin, Hu & Tu, Dejian, 2011. "The tree representation for the pickup and delivery traveling salesman problem with LIFO loading," European Journal of Operational Research, Elsevier, vol. 212(3), pages 482-496, August.
    7. A. Felipe & M. Ortuño & G. Tirado, 2009. "New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer, vol. 17(1), pages 190-213, July.
    8. Petersen, Hanne L. & Madsen, Oli B.G., 2009. "The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches," European Journal of Operational Research, Elsevier, vol. 198(1), pages 139-147, October.
    9. Nagy, Gabor & Salhi, Said, 2005. "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 162(1), pages 126-141, April.
    10. Li, Haibing & Lim, Andrew, 2003. "Local search with annealing-like restarts to solve the VRPTW," European Journal of Operational Research, Elsevier, vol. 150(1), pages 115-127, October.
    11. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer, vol. 18(1), pages 4-27, July.
    12. Healy, Patrick & Moll, Robert, 1995. "A new extension of local search applied to the Dial-A-Ride Problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 83-104, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:223:y:2012:i:1:p:60-75. 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: (Zhang, Lei).

    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 references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link 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 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.