这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

The single vehicle pickup and delivery problem with time windows: intelligent operators for heuristic and metaheuristic algorithms

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The single vehicle pickup and delivery problem with time windows is an important practical problem, yet only a few researchers have tackled it. In this research, we compare three different approaches to the problem: a genetic algorithm, a simulated annealing approach, and a hill climbing algorithm. In all cases, we adopt a solution representation that depends on a duplicate code for both the pickup request and its delivery. We also present an intelligent neighborhood move, that is guided by the time window, aiming to overcome the difficult problem constraints efficiently. Results presented herein improve upon those that have been previously published.

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

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  • Blanton, J., Wainwright, R.: Multiple vehicle routing with time and capacity constraints using genetic algorithms. In: Proceedings of the 5th International Conference on Genetic Algorithms, pp. 452–459, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. (1993)

  • Bruggen, L.J.J.V.D., Lenstra, J., Schuur, P.: Variable-depth search for the single-vehicle pickup and delivery problem with time windows. Transp. Sci. 27(3), 298–311 (1993)

    Article  MATH  Google Scholar 

  • Desrosiers, J., Dumas, Y., Soumis, F.: A dynamic programming solution of the large-scale single vehicle dial-a-ride problem with time windows. Am. J. Math. Manag. Sci. 6, 3–4 (1986)

    Google Scholar 

  • Diana, M., Dessouky, M.: A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows. Transp. Res. Part B: Methodol. 38(6), 539–557 (2004)

    Article  Google Scholar 

  • Dorband, J., Mumford, C., Wang, P.: Developing an ace solution for two-dimensional strip packing. In: 18th International Parallel and Distributed Processing Symposium Workshop on Massively Parallel Processing, Santa Fe, New Mexico (2004)

  • Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison–Wesley, Boston (1989)

    MATH  Google Scholar 

  • Healy, P., Moll, R.: A new extension of local search applied to the dial-a-ride problem. Eur. J. Oper. Res. 83(1), 83–104 (1995)

    Article  MATH  Google Scholar 

  • Hosny, M.I., Mumford, C.L.: Single vehicle pickup and delivery with time windows: made to measure genetic encoding and operators. In: GECCO ’07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, pp. 2489–2496, New York, NY, USA. ACM Press (2007)

  • Jih, W., Hsu, Y.: Dynamic vehicle routing using hybrid genetic algorithms. In: Proceedings of the 1999 IEEE International Conference on Robotics and Automation, vol. 1, pp. 453–458, Detroit, Michigan (1999)

  • Jih, W., Hsu, Y.: A family competition genetic algorithm for the pickup and delivery problems with time window. Bull. Coll. Eng. N.T.U. 90, 89–98 (2004)

    Google Scholar 

  • Jørgensen, R.M., Larsen, J., Bergvinsdottir, K.B.: Solving the dial-a-ride problem using genetic algorithms. J. Oper. Res. Soc. 58, 1321–1331 (2007)

    Article  MATH  Google Scholar 

  • Kirkpatrick, S., Gelatt, C.D. Jr., Vecchi, M.P.: Optimization by Simulated Annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  Google Scholar 

  • Landrieu, A., Mati, Y., Binder, Z.: A tabu search heuristic for the single vehicle pickup and delivery problem with time windows. J. Intell. Manuf. 12(5), 497–508 (2001)

    Article  Google Scholar 

  • Lau, H., Liang, Z.: Pickup and delivery with time windows: algorithms and test case generation. In: Proceedings of the 13th International Conference on Tools with Artificial Intelligence, pp. 333–340 (2001)

  • Li, H., Lim, A.: A metaheuristic for the pickup and delivery problem with time windows. In: Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence, pp. 160–167, Dallas, TX, USA (2001)

  • Lu, Q., Dessouky, M.M.: A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows. Eur. J. Oper. Res. 175(2), 672–687 (2006)

    Article  MATH  Google Scholar 

  • Man, K., Tang, K., Kwong, S.: Genetic algorithms: concepts and applications [in engineering design]. Ind. Electron. IEEE Trans. 43(5), 519–534 (1996)

    Article  Google Scholar 

  • Nanry, W.P., Barnes, J.W.: Solving the pickup and delivery problem with time windows using reactive tabu search. Transp. Res. Part B: Methodol. 34(2), 107–121 (2000)

    Article  Google Scholar 

  • Psaraftis, H.: An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows. Transp. Sci. 17(3), 351–357 (1983)

    Article  Google Scholar 

  • Renaud, J., Boctor, F.F., Quenniche, J.: A heuristic for the pickup and delivery traveling salesman problem. Comput. Oper. Res. 27(9), 905–916 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  • Rutenbar, R.: Simulated annealing algorithms: an overview. Circ. Devices Mag. IEEE 5(1), 19–26 (1989)

    Article  Google Scholar 

  • Savelsbergh, M.W.P., Sol, M.: The general pickup and delivery problem. Transp. Sci. 29(1), 17–29 (1995)

    Article  MATH  Google Scholar 

  • Tam, V., Tseng, L.C.: Effective heuristics to solve pickup and delivery problems with time windows. In: Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, pp. 184–188 (2003)

  • Transport-Statistics: Road freight statistics 2005. A national statistics publication produced for the department of transport, UK (2006). www.dft.gov.uk/transtat

  • Wall, M.: Galib: A C++ library of genetic algorithm components. Mechanical Engineering Department, MIT (1996). http://lancet.mit.edu/ga

Download references

Author information

Authors and Affiliations

  1. Cardiff School of Computer Science, Cardiff University, Queen’s Buildings, 5 The Parade, Roath, Cardiff, CF24 3AA, UK

    Manar I. Hosny & Christine L. Mumford

Authors
  1. Manar I. Hosny
    View author publications

    Search author on:PubMed Google Scholar

  2. Christine L. Mumford
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Manar I. Hosny.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hosny, M.I., Mumford, C.L. The single vehicle pickup and delivery problem with time windows: intelligent operators for heuristic and metaheuristic algorithms. J Heuristics 16, 417–439 (2010). https://doi.org/10.1007/s10732-008-9083-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10732-008-9083-1

Keywords