[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Neural-Tabu Search Heuristic for the Real Time Vehicle Routing Problem

  • Published:
Journal of Mathematical Modelling and Algorithms

Abstract

The Real Time Vehicle Routing Problem RTVRP is a dynamic routing problem where requests are generated dynamically during the operation horizon without any previous knowledge. Received requests need to be answered as fast as possible and then assigned to a vehicle to be served. Due to timing constraints of the RTVRP, a solving approach should give the best compromise between the cost of the provided solution and the computation time needed to find it. In this paper, we present a neural-tabu search solving scheme for the RTVRP. The developed approach is composed by two phases; The first part consists of learning and reproducing previous routing decisions using a feed forward neural network with a particular structure. The second phase is based on a tabu search heuristic that takes its initial solution from the assignment provided by the neural module. If the reaction time is still available, the tabu search module will continue ameliorating the final solution. To evaluate the proposed approach a set of problems are simulated and solved. The obtained results are compared to those given by the First Come First Served FCFS and Nearest Neighbor NN policies and also to the optimal solutions provided by the GNU Linear Programming Kit GLPK.

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+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Angeniol, B., Vaubois, G., Le Texier, J.Y.: Self-organizing feature maps and the traveling salesman problem. Neural Netw. 1, 289–293 (1988)

    Article  Google Scholar 

  2. Battiti, R., Tecchiolli, G.: The reactive tabu search. ORSA J. Comput. 6(2), 126–140 (1994)

    MATH  Google Scholar 

  3. Bertsimas, D., Van Ryzin, G.: Stochastic and dynamic vehicle routing in euclidean plan with multiple capacitated vehicles. Oper. Res. 41, 60–76 (1993)

    MathSciNet  MATH  Google Scholar 

  4. Bertsimas, D., Van Ryzin, G.: A stochastic and dynamic vehicle routing problem in the euclidian plan. Oper. Res. 44, 286–304 (1996)

    MATH  Google Scholar 

  5. Bertsimas, D., Van Ryzin, G.: A stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Appl. Probab. 25, 947–978 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  6. Burke, L.I., Ignizio, J.P.: Neural networks and operations research: an overview. Comput. Oper. Res. 19, 179–189 (1992)

    Article  MATH  Google Scholar 

  7. Cordeau, J.-F., Laporte, G., Mercier A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)

    Article  MATH  Google Scholar 

  8. Gendreau, M., Potvin, J.Y.: Dynamic Vehicle Routing. CRT Pub. no 97–38 (1997)

  9. Gendreau, M., Guertin, F., Potvin, J.Y., Taillard, E.: Parallel tabu search for real-time vehicle routing and dispatching. Transp. Sci. 33(4), 381–390 (1999)

    Article  MATH  Google Scholar 

  10. Gendreau, M., Guertin, F., Potvin, J-Y., Taillard, E.: Tabu search for real-time vehicle routing and dispatching. Technical Report CRT 96–47 (1996)

  11. Gendreau, M., Hertz, A., Laporte, G.: A tabu search heuritic for the vehicle routing problem. Manage. Sci. 40, 1276–1290 (1994)

    MATH  Google Scholar 

  12. Ghaziri, H.: Solving routing problems by a self-organizing map. In: Kohonen, T., Makisara, K., Simula, O., Kangas, J. (eds.) Artificial Neural Networks, pp. 829–834. North-Holland, Amsterdam (1991)

  13. Ghaziri, H.: Supervision in the self-organizing feature map: application to the vehicle routing problem. In: Osman, I.H., Kelly, J.P. (eds.) Meta-Heuristics: Theory & Applications, pp. 651–660. Kluwer (1996)

  14. Ghiani, G., Guerriero, F., Laporte, G., Musmanno, R.: Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. Eur. J. Oper. Res. 151(1), 1–11 (2003)

    Article  MATH  Google Scholar 

  15. Glover, F., Taillard, E., De Werra D.: A user’s guide to tabu search. Ann. Oper. Res. 41, 3–28 (1993)

    Article  MATH  Google Scholar 

  16. Grôtschel, M., Krumke, S.O., Rambau, J., Winter, T., Zimmermann, U. T.: Combinatorial Online Optimization in Real Time, Online Optimization of Large Scale Systems. Springer (2001)

  17. Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. In: Proceedings of the National Academy of Sciences 79, 2554–2558 (1982)

  18. Hopfield, J.J., Tank, D.W.: Neural computation of decisions in optimization problems. Biol. Cybern. 52, 141–152 (1985)

    MathSciNet  MATH  Google Scholar 

  19. Ichoua, S., Gendreau, G., Séguin, R.: Diversion issues in real-time vehicle dispatching. Transp. Sci. 34(4), 426–438 (2000)

    Article  MATH  Google Scholar 

  20. Ichoua, S., Gendreau, G., Potvin, J-Y.: Exploiting knowledge about future demands for real-time vehicle dispatching. Transp. Sci. 40, 211–225 (2006)

    Article  Google Scholar 

  21. Kohonen, T.: Self-organized formation of topologically correct feature maps. Biol. Cybern. 43, 59–69 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kohonen, T.: Self-Organization and Associative Memory. Springer, Berlin (1988)

    MATH  Google Scholar 

  23. Laporte, G., Semet, F.: Classical heuristics for the vehicle routing problem. Les cahiers de Gerad: G-98-54 (1998)

  24. Larsen, A.: The Dynamic Vehicle Routing Problem. Ph.D. Thesis IMM-PHD-2000-73

  25. Li, Y., Rousseau, J.M., Gendreau, M.: Real-time dispatching of public transit operations with and without bus location information. In: Computer Aided Transit Scheduling Proceedings, pp. 296–308 (1995)

  26. Looi, C.K.: Neural network methods in combinatorial optimization. Comput. Oper. Res. 19, 191–208 (1992)

    Article  MATH  Google Scholar 

  27. Lund, K., Madsen, O.B.G., Rygaard, J.M.: Vehicle Routing Problems with Varying Degrees of Dynamism. Technical Report IMM, The Departement of Matematical Modelling (1996)

  28. Madsen, O.B.G., Ravn, H.F., Rygaard, J.M.: A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities and multiple objectives. Ann. Oper. Res. 60, 193–208 (1995)

    Article  MATH  Google Scholar 

  29. Matsuyama Y.: Self-organization via competition, cooperation and categorization applied to extended vehicle routing problems. In: Proceedings of the Int. Joint Conf. on Neural Networks, pp. I-385–390. Seattle, USA (1991)

  30. Osman, I.H., Laporte, G.: Metaheuristics: a bibliography. Ann. Oper. Res. 63, 513–628 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  31. Papastouvrou, J.D.: A stochastic and dynamic routing policy using branching processes with state depending immigration. Eur. J. Oper. Res. 95(1), 167–177 (1996)

    Article  Google Scholar 

  32. Peterson, C., Soderberg, B.: Artificial neural networks. In: Reeves, C.R. (ed.) Modern Heuristic Techniques for Combinatorial Optimization, Chapter 5. Blackwell Scientific Publishers, Oxford, UK (1993)

    Google Scholar 

  33. Potvin, J.Y.: The traveling salesman problem: a neural network perspective. ORSA J. Comput. 5, 328–348 (1993)

    MATH  Google Scholar 

  34. Potvin, J.Y., Robillard, C.: Clustering for vehicle routing with a competitive neural network model. Neurocomputing 8, 125–139 (1995)

    Article  Google Scholar 

  35. Psaraftis, H.N.: Dynamic vehicle routing: status and prospects. Ann. Oper. Res. 61, 143–164 (1995)

    Article  MATH  Google Scholar 

  36. Psaraftis, H.N.: Vehicle routing: methods and studies, chapter dynamic vehicle routing problems. pp. 223–248. Elsevier Science (1988)

  37. Qili, K.Z., Ong, K.: A Reactive Method for Real Time Dynamic Vehicle Routing Problem. 12th ICTAI, Vancouver, Canada (2000)

  38. Rego, C., Roucairol, C.: A parallel tabu search algorithm using ejection chains for the vehicle routing problem. In: Osman, I.H., Kelly, J.P. (eds.) Meta-Heuristics: Theory and Applications, pp. 661–675. Kluwer, Boston (1996)

    Google Scholar 

  39. Rochat, Y., Taillard, E.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)

    Article  MATH  Google Scholar 

  40. Séguin, R., Potvin, J.Y., Gendreau, M.: Real-time decision problems: an operations research perspective. J. Oper. Res. Soc. 48, 162–174 (1997)

    Article  MATH  Google Scholar 

  41. Smith, K.A.: Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS J. Comput. 11, 15–34 (1999)

    MathSciNet  MATH  Google Scholar 

  42. Smith, K.A., Palaniswami, M., Krishnamoorthy, M.: A hybrid neural approach to combinatorial optimization. Comput. Oper. Res. 23, 597–610 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  43. Swihart, M.R., Papastouvrou, J.: A stochastic and dynamic model for the single vehicle pick-up and delivery problem. Eur. J. Oper. Res. 114, 447–464 (1999)

    Article  MATH  Google Scholar 

  44. Tagliarini, G.A., Christ, J.F., Page, E.W.: Optimization using neural networks. IEEE Trans. Comput. 40, 1347–1358 (1991)

    Article  Google Scholar 

  45. Taillard, E.: Parallel iterative search methods for vehicle routing problem. Networks 23, 661–673 (1993)

    Article  MATH  Google Scholar 

  46. Taillard, E.D., Badeau, P., Gendreau, M., Guertin, F., Potvin J.Y.: A tabu search heuristic for the vehicle routing problem with soft time windows. Transp. Sci. 31, 170–186 (1997)

    MATH  Google Scholar 

  47. Vakhutinsky, A.I., Golden, B.L.: Solving vehicle routing problems using elastic nets. In: Proceedings of the IEEE Int. Conf. On Neural Networks, pp. 4535–4540 (1994)

  48. Winter, T., Zimmermann, U.: Discrete Online and Real-time Optimization. Proceedings of the 15th IFIP World Computer (1998)

  49. Xu, J., Kelly, J.P.: A network flow-based tabu search heuristic for the vehicle routing problem. Transp. Sci. 30, 379–393 (1996)

    MATH  Google Scholar 

  50. Yang, J., Jaillet, P., Mahmassani, H.: Real-time multi-vehicle truckload pick-up and delivery problem. Transp. Sci. 38, 135–148 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LARODEC Laboratory, High Institute of Management, University of Tunis, Tunis, Tunisia

    Jaber Jemai & Khaled Mellouli

Authors
  1. Jaber Jemai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Khaled Mellouli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jaber Jemai.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jemai, J., Mellouli, K. A Neural-Tabu Search Heuristic for the Real Time Vehicle Routing Problem. J Math Model Algor 7, 161–176 (2008). https://doi.org/10.1007/s10852-008-9082-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-008-9082-0

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation