Skip to main content
SpringerLink
Log in

An iterated local search algorithm for the Travelling Salesman Problem with Pickups and Deliveries

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

The Travelling Salesman Problem with Pickups and Deliveries (TSPPD) consists in designing a minimum cost tour that starts at the depot, provides either a pickup or delivery service to each of the customers and returns to the depot, in such a way that the vehicle capacity is not exceeded in any part of the tour. In this paper, the TSPPD is solved by considering a metaheuris-tic algorithm based on Iterated Local Search with Variable Neighbourhood Descent and Random neighbourhood ordering. Our aim is to propose a fast, flexible and easy to code algorithm, also capable of producing high quality solutions. The results of our computational experience show that the algorithm finds or improves the best known results reported in the literature within reasonable computational time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1

Similar content being viewed by others

References

  • Altınel İK and Öncan T (2005). A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Journal of the Operational Research Society 56 (8): 954–961.

    Article  Google Scholar 

  • Anily S and Mosheiov G (1994). The traveling salesman problem with delivery and back-hauls. Operations Research Letters 16 (1): 11–18.

    Article  Google Scholar 

  • Applegate DL, Bixby RE, Chvátal V and Cook WL (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press: Princeton, NJ.

    Google Scholar 

  • Baldacci R, Hadjiconstantinou E and Mingozzi A (2003). An exact algorithm for the traveling salesman problem with deliveries and collections. Networks 42 (1): 26–41.

    Article  Google Scholar 

  • Battarra M, Benedettini S and Roli A (2011). Leveraging saving-based algorithms by master-slave genetic algorithms. Engineering Applications of Artificial Intelligence 24 (4): 555–566.

    Article  Google Scholar 

  • Berbeglia G, Cordeau J-F, Gribkovskaia I and Laporte G (2007). Static pickup and delivery problems: A classification scheme and survey. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research 15 (1): 1–31.

    Article  Google Scholar 

  • Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y and Semet F (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society 53 (5): 512–522.

    Article  Google Scholar 

  • Croes GA (1958). A method for solving traveling-salesman problems. Operations Research 6 (6): 791–812.

    Article  Google Scholar 

  • Dongarra J (2010). Performance of various computers using standard linear equations software. (Linpack Benchmark Report). Technical report, University of Tennessee Computer Science, CS-89-85.

  • Erdoğan G, Cordeau J-F and Laporte G (2009). The pickup and delivery traveling salesman problem with first-in-first-out loading. Computers & Operations Research 36 (6): 1800–1808.

    Article  Google Scholar 

  • Erdoğan G, Battarra M, Laporte G and Vigo D (2012). Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs. Computers & Operations Research 39 (5): 1074–1086.

    Article  Google Scholar 

  • Finke G, Claus A and Gunn E (1984). A two-commodity network flow approach to the traveling salesman problem. Congressus Numerantium 41 (1): 167–178.

    Google Scholar 

  • Fischetti M and Lodi A (2003). Local branching. Mathematical Programming 98 (1): 23–47.

    Article  Google Scholar 

  • Gaskell TJ (1967). Bases for vehicle fleet scheduling. Operational Research Quarterly 18 (3): 281–295.

    Article  Google Scholar 

  • Gavish B (1991). Topological design of telecommunication networks-local access design methods. Annals of Operations Research 33 (1): 17–71.

    Article  Google Scholar 

  • Gendreau M, Laporte G and Vigo D (1999). Heuristics for the traveling salesman problem with pickup and delivery. Computers & Operations Research 26 (7): 699–714.

    Article  Google Scholar 

  • Glover F (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 5 (5): 533–549.

    Article  Google Scholar 

  • Gribkovskaia I, Laporte G and Shyshou A (2008). The single vehicle routing problem with deliveries and selective pickups. Computers & Operations Research 35 (9): 2908–2924.

    Article  Google Scholar 

  • Hernández-Pérez H and Salazar-González J-J (2003). The one-commodity pickup-and-delivery travelling salesman problem. In: Jünger M, Reinelt G, and Rinaldi G (eds). Combinatorial Optimization—Eureka, you Shrink. Springer-Verlag: New York, pp 89–104.

    Chapter  Google Scholar 

  • Hernández-Pérez H and Salazar-González J-J (2004). Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science 38 (2): 245–255.

    Article  Google Scholar 

  • Hernández-Pérez H and Salazar-González J-J (2007). The one-commodity pickup-and-delivery traveling salesman problem: Inequalities and algorithms. Networks 50 (4): 258–272.

    Article  Google Scholar 

  • Ladany SP and Mehrez A (1984). Optimal routing of a single vehicle with loading and unloading constraints. Transportation Planning and Technology 8 (4): 301–306.

    Article  Google Scholar 

  • Lourenco HR, Martin OC and Stutzle T (2003). Iterated local search. In: Glover F and Kochenberger GA (eds). Handbook of Metaheuristics. Kluwer: Boston, MA, pp 321–353.

    Google Scholar 

  • Martin O, Otto SW and Felten EW (1991). Large-step Markov chains for the traveling salesman problem. Complex Systems 5 (3): 299–326.

    Google Scholar 

  • Mosheiov G (1994). The travelling salesman problem with pick-up and delivery. European Journal of Operational Research 79 (2): 299–310.

    Article  Google Scholar 

  • Or I (1976). Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD Thesis, Northwestern University.

  • Penna PHV, Subramanian A and Ochi LS (2011). An iterated local search heuristic for the heterogenous fleet vehicle routing problem. Journal of Heuristics, http://dx.doi.org/10.1007/s10732-011-9186-y, published online 8 September.

  • Pisinger D and Ropke S (2007). A general heuristic for vehicle routing problems. Computers & Operations Research 34 (8): 2403–2435.

    Article  Google Scholar 

  • Ropke S and Pisinger D (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research 171 (3): 750–775.

    Article  Google Scholar 

  • Subramanian A, Uchoa E and Ochi L (2010). New lower bounds for the vehicle routing problem with simultaneous pickup and delivery. In: Festa P (ed). Experimental Algorithms. Vol. 6049 of Lecture Notes in Computer Science. Springer: Berlin, Heidelberg, pp 276–287.

    Chapter  Google Scholar 

  • Zhao F-G, Sun J-S, Li S-J and Liu W-M (2009). A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery. International Journal of Automation and Computing 6 (1): 97–102.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universidade Federal da Paraíba, João Pessoa, Brazil

    A Subramanian

  2. University of Southampton, Southampton, UK

    M Battarra

Authors
  1. A Subramanian
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M Battarra
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M Battarra.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Subramanian, A., Battarra, M. An iterated local search algorithm for the Travelling Salesman Problem with Pickups and Deliveries. J Oper Res Soc 64, 402–409 (2013). https://doi.org/10.1057/jors.2012.24

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2012.24

Keywords

Search

Navigation