Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation | SpringerLink
Skip to main content
Springer Nature Link
Log in

Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation

  • Conference paper
Parallel Problem Solving from Nature - PPSN VIII (PPSN 2004)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 3242))

Included in the following conference series:

Abstract

We introduce the concept of fruitful regions in a dynamic routing context: regions that have a high potential of generating loads to be transported. The objective is to maximise the number of loads transported, while keeping to capacity and time constraints. Loads arrive while the problem is being solved, which makes it a real-time routing problem. The solver is a self-adaptive evolutionary algorithm that ensures feasible solutions at all times. We investigate under what conditions the exploration of fruitful regions improves the effectiveness of the evolutionary algorithm.

This work is part of DEAL (Distributed Engine for Advanced Logistics) supported as project EETK01141 under the Dutch EET programme.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 9151
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 11439
Price includes VAT (Japan)
  • 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bertsimas, D., Simchi-Levi, D.: A new generation of vehicle routing research: Robust algorithms, addressing uncertainty. Operations Research 44, 286–304 (1996)

    Article  MATH  Google Scholar 

  2. Savelsbergh, M., Sol, M.: The general pickup and delivery problem. Transportation Science 29, 17–29 (1995)

    Article  MATH  Google Scholar 

  3. Psaraftis, H.: Dynamic vehicle routing: status and prospects. Annals of Operations Research 61, 143–164 (1995)

    Article  MATH  Google Scholar 

  4. Ghiani, G., Guerriero, F., Laporte, G., Musmanno, R.: Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. Technical report, Center of Excellence for High Performance Computing, Univ. of Calabria, Italy (2003)

    Google Scholar 

  5. de Paepe, W.: Complexity Results and Competitive Analysis for Vehicle Routing Problems. PhD thesis, Research School for Operations Management and Logistics, Technical University of Eindhoven (2002)

    Google Scholar 

  6. Laporte, G., Louveaux, F.: Formulations and bounds for the stochastic capacitated vehicle routing problem with uncertain supplies, pp. 443–455. Elsevier Science Publishers B.V., Amsterdam (1990)

    Google Scholar 

  7. Laporte, G., Louveaux, F., Mercure, H.: The vehicle routing problem with stochastic travel times. Transportation Science 26, 161–170 (1992)

    Article  MATH  Google Scholar 

  8. Bianchi, L.: Notes on dynamic vehicle routing — the state of the art. Technical report, IDSIA, Galleria 2, 6928 Manno-Lugano, Switzerland (2000)

    Google Scholar 

  9. Golden, B., Assad, A.: Vehicle Routing: methods and studies. Elsevier Science Publishers B.V., Amsterdam (1988)

    MATH  Google Scholar 

  10. Psaraftis, H.: Dynamic vehicle routing problems. In: [9], ch. 11, pp. 223–248.

    Google Scholar 

  11. Powell, W.: A comparative review of alternative algorithms for the dynamic vehicle routing problem. In: [9], ch. 12, pp. 249–291.

    Google Scholar 

  12. Powell, W.: A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers. Transportation Science 30, 195–219 (1996)

    Article  MATH  Google Scholar 

  13. Gendreau, M., Potvin, J.Y.: Dynamic vehicle routing and dispatching. In: Crainic, T., Laporte, G. (eds.) Fleet Management and Logistics, pp. 115–126. Kluwer, Boston (1998)

    Google Scholar 

  14. Solomon, M.: The vehicle routing and scheduling problems with time window constraints. Operations Research 35, 254–265 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  15. Branke, J.: Evolutionary Optimization in Dynamic Environments. Genetic Algorithms and Evolutionary Computation, vol. 3. Kluwer Academic Publishers, Dordrecht (2001)

    Google Scholar 

  16. Bräysy, O., Gendreau, M.: Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Science (to appear)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dutch National Research Institute for Mathematics and Computer Science, P.O. Box 94079, NL-1090 GB, Amsterdam, The Netherlands

    Jano I. van Hemert & J. A. La Poutré

Authors
  1. Jano I. van Hemert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. A. La Poutré
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Birmingham, Birmingham, UK

    Xin Yao

  2. Automated Scheduling, Optimisation and Planning Group, School of Computer Science & IT, University of Nottingham, NG8 1BB, Nottingham, UK

    Edmund K. Burke

  3. Intelligent Systems Group Department of Computer Science and Artificial Intelligence, University of the Basque Country, Paseo Manuel de Lardizábal 1, 20018, San Sebastian, Donostia, Spain

    José A. Lozano

  4. University of the West of England, Bristol, United Kingdom

    Jim Smith

  5. GeNeura Team, Depto. Arquitectura y Tecnología de Computadores, Universidad de Granada, Spain

    Juan Julián Merelo-Guervós

  6. School of Computer Science, The University of Birmingham, B15 1TT, Edgbaston, Birmingham, UK

    John A. Bullinaria

  7. School of Computer Science, University of Birmingham, B15 2TT, Birmingham, Great Britain

    Jonathan E. Rowe

  8. School of Computer Science, University of Birmingham, United Kingdom

    Peter Tiňo

  9. School of Computer Science, The University of Birmingham, B15 2TT, Birmingham, UK

    Ata Kabán

  10. Faculty of Computer Science, Dortmund University of Technology, 44221, Dortmund, Germany

    Hans-Paul Schwefel

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

van Hemert, J.I., La Poutré, J.A. (2004). Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation. In: Yao, X., et al. Parallel Problem Solving from Nature - PPSN VIII. PPSN 2004. Lecture Notes in Computer Science, vol 3242. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30217-9_70

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-30217-9_70

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-23092-2

  • Online ISBN: 978-3-540-30217-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics