Skip to main content
Springer Nature Link
Log in

A Parallel Meta-heuristic for Solving a Multiple Asymmetric Traveling Salesman Problem with Simulateneous Pickup and Delivery Modeling Demand Responsive Transport Problems

  • Conference paper
  • First Online:
Hybrid Artificial Intelligent Systems (HAIS 2015)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 9121))

Included in the following conference series:

Abstract

Transportation is an essential area in the nowadays society. Due to the rapid technological progress, it has gained a great importance, both for business sector and citizenry. Among the different types of transport, one that has gained notoriety recently is the transportation on-demand, because it can affect very positively the people quality of life. There are different kinds of on-demand transportation systems, being the Demand Responsive Transit (DRT) one of the most important one. In this work, a real-life DRT problem is proposed, and modeled as a Rich Traveling Salesman Problem. Specifically, the problem presented is a Multiple Asymmetric Traveling Salesman Problem with Simultaneous Pickup and Delivery. Furthermore, a benchmark for this new problem is also proposed, and its first resolution is offered. For the resolution of this benchmark the recently developed Golden Ball meta-heuristic has been implemented.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 52.74
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://www.bristoldialaride.org.uk/.

  2. 2.

    https://www.capetown.gov.za/en/Transport/Pages/AboutDialaRide.aspx.

  3. 3.

    https://www.tfl.gov.uk/modes/dial-a-ride/.

References

  1. Cordeau, J.F., Laporte, G., Potvin, J.Y., Savelsbergh, M.W.: Transportation on demand. Transp. Handb. Oper. Res. Manage. Sci. 14, 429–466 (2004)

    Google Scholar 

  2. Brake, J., Nelson, J.D., Wright, S.: Demand responsive transport: towards the emergence of a new market segment. J. Transp. Geogr. 12(4), 323–337 (2004)

    Article  Google Scholar 

  3. Ritzinger, U., Puchinger, J., Hartl, R.F.: Dynamic programming based metaheuristics for the dial-a-ride problem. Ann. Oper. Res. 228, 1–18 (2014)

    Google Scholar 

  4. Paquette, J., Cordeau, J.F., Laporte, G., Pascoal, M.: Combining multicriteria analysis and tabu search for dial-a-ride problems. Transp. Res. Part B: Methodol. 52, 1–16 (2013)

    Article  Google Scholar 

  5. Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur. J. Oper. Res. 231(1), 1–21 (2013)

    Article  MathSciNet  Google Scholar 

  6. Osaba, E., Diaz, F., Onieva, E.: Golden ball: a novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Appl. Intell. 41(1), 145–166 (2014)

    Article  Google Scholar 

  7. Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3), 209–219 (2006)

    Article  Google Scholar 

  8. Laporte, G., Mercure, H., Nobert, Y.: An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16(1), 33–46 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  9. Toth, P., Vigo, D.: A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. Eur. J. Oper. Res. 113(3), 528–543 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  10. Montané, F.A.T., Galvao, R.D.: A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput. Oper. Res. 33(3), 595–619 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  11. Bianchessi, N., Righini, G.: Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Comput. Oper. Res. 34(2), 578–594 (2007)

    Article  MATH  Google Scholar 

  12. Osaba, E., Onieva, E., Diaz, F., Carballedo, R., Lopez, P., Perallos, A.: An asymmetric multiple traveling salesman problem with backhauls to solve a dial-a-ride problem. In: IEEE International Symposium on Applied Machine Intelligence and Informatics, pp. 151–156. IEEE (2015)

    Google Scholar 

  13. Reinelt, G.: TSPLIBA traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)

    Article  MATH  Google Scholar 

  14. Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44(10), 2245–2269 (1965)

    Article  MATH  Google Scholar 

  15. Davis, L.: Applying adaptive algorithms to epistatic domains. In: Proceedings of the international joint conference on artificial intelligence, vol. 1, pp. 161–163 (1985)

    Google Scholar 

  16. Savelsbergh, M.W.: The vehicle routing problem with time windows: minimizing route duration. ORSA J. Comput. 4(2), 146–154 (1992)

    Article  MATH  Google Scholar 

Download references

Acknowledgement

The authors would like to thank the Entornos inteligentes ubicuos aplicados a la trazabilidad en el sector de transportes y vehiculares project (UBITRACE PC2013-71A) for its support in the development of this work.

Author information

Authors and Affiliations

  1. Deusto Institute of Technology (DeustoTech), University of Deusto, Av. Universidades 24, 48007, Bilbao, Spain

    E. Osaba, F. Diaz, E. Onieva, Pedro López-García, R. Carballedo & A. Perallos

Authors
  1. E. Osaba
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. Diaz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. E. Onieva
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pedro López-García
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. R. Carballedo
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. A. Perallos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to E. Osaba .

Editor information

Editors and Affiliations

  1. University of Deusto, Bilbao, Spain

    Enrique Onieva

  2. University of Deusto, Bilbao, Spain

    Igor Santos

  3. University of Deusto, Bilbao, Spain

    Eneko Osaba

  4. Universidad de Salamanca, Salamanca, Spain

    Héctor Quintián

  5. Universidad de Salamanca, Salamanca, Spain

    Emilio Corchado

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Osaba, E., Diaz, F., Onieva, E., López-García, P., Carballedo, R., Perallos, A. (2015). A Parallel Meta-heuristic for Solving a Multiple Asymmetric Traveling Salesman Problem with Simulateneous Pickup and Delivery Modeling Demand Responsive Transport Problems. In: Onieva, E., Santos, I., Osaba, E., Quintián, H., Corchado, E. (eds) Hybrid Artificial Intelligent Systems. HAIS 2015. Lecture Notes in Computer Science(), vol 9121. Springer, Cham. https://doi.org/10.1007/978-3-319-19644-2_46

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-19644-2_46

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-19643-5

  • Online ISBN: 978-3-319-19644-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation