Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS

Тел.: +7 (495) 625-9241


A hybrid approach to use of external and internal memory in heuristic search for automated planning


V.I. Korablev – Post-graduate Student, Engineer, Department «Cybernetics», National Research Nuclear University «MEPhI» (Moscow)
V.A. Korneev – Student, Department «Cybernetics», National Research Nuclear University «MEPhI» (Moscow)

This article is devoted to the problem of solving dynamic vehicle routing problems with time windows.
The first section describes the mathematical formulation of the vehicle routing problem with dynamic customer requests. Solution of this kind of VRP is one of the most actual themes because logistics is probably part of every sphere of our life. Good and fast solutions of this problem reduce costs and increase profit. In this article, the description of VNS implementation can be found, the algorithm which many articles are devoted to. The uniqueness of this article is the description of VNS modifications which allow to make solutions of the VRP better.
The main ideas of the modified Variable Neighborhood Search (VNS) algorithm are described in the next section. The developed algo-rithm uses the 2 opt operator for local search, which eliminates crossed routes thereby reducing the total distance. A unique break criterion is described, which provides an optimal ratio of execution time and the quality of the solution. Time-oriented heuristic of the nearest neighborhood is used for search for an acceptable solution, which calculates the special proximity metric of the client. This metric takes into account the proximity of time windows, proximity by distance and travel time with different embedding coefficients. Particularly noteworthy is the modification of the VNS algorithm by the heuristic of the elimination of short routes, which makes it possible to reduce the number of vehicles used by an average of 20 percent.
The next section describes testing the developed method by Solomon tests. A comparison is made with the best results for distance and used vehicles mentioned in scientific articles. The effect of using heuristics for the elimination of short routes is shown. The peculiarity of the implementation of the developed algorithm is mentioned – the possibility of finding an acceptable solution among inadmissible with minimal violations of restrictions on time windows, if the permissible ones are not available, which allows increasing flexibility in the application of implementation. In addition, the implementation provides the function to automatically generate recommended temporary windows, which facilitates user experience.
In the last section, a comprehensive assessment of the quality of the solutions is carried out by considering algorithm running time, the total distance and the vehicles spent.
In conclusion, it should be noted that the developed algorithm shows the results, that are better than the best known at the moment of implementation, considering the total distance and execution time on tasks with a dimension of up to 100 customers. All the properties above make this implementation of the VNS algorithm unique in its own way.

  1. Dantzig G.B., Ramser J.H. The truck dispatching problem // Management science. 1959. T. 6. № 1. S. 80−91.
  2. Kobersi I.S., Shkurkin D.V. Primenenie geneticheskix algoritmov dlya optimizaczii transportny'x zadach // Izv. Juzhnogo federal'nogo universiteta. Texnicheskie nauki. 2012. T. 127. № 2.
  3. Emel'yanova T.S., Kurejchik V.M. Reshenie transportny'x zadach s ispol'zovaniem kombinirovannogo geneticheskogo algoritma // Trudy' XI naczional'noj konf. po iskusstvennomu intellektu s mezhdunarodny'm uchastiem KII-2008. 2008. № 3. S. 157−161.
  4. Dorigo M. Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale // Unpublished doctoral dissertation. 1992.
  5. Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem // Evolutionary Computation, IEEE Transactions on. 1997. T. 1. № 1. S. 53−66.
  6. Stützle T., Hoos H. MAX-MIN ant system and local search for the traveling salesman problem // Evolutionary Computation. 1997. IEEE International Conference on. IEEE. 1997. S. 309−314.
  7. Stützle T. et al. Parameter adaptation in ant colony optimization // Autonomous search. Springer Berlin Heidelberg. 2011. S. 191−215.
  8. Kurejchik V.M. Geneticheskie algoritmy'. Monografiya. Taganrog: TRTU. 1998.
  9. Kurejchik V.M. Gibridny'e geneticheskie algoritmy' // Izv. JuFU. Texnicheskie nauki. 2007. № 2. S. 5−12.
  10. Zaporozhecz D.Ju., Kurejchik V.V. Gibridny'j algoritm resheniya zadach transportnogo tipa // Izv. JuFU. Texnicheskie nauki. 2013. № 7 (144). S. 80−85.
  11. Gladkov L.A., Gladkova N.V. Gibridny'j algoritm resheniya transportny'x zadach s ogranicheniem po vremeni // Izv. JuFU. Texnicheskie nauki. 2015. № 6 (167). Razdel V. Novy'e informaczionny'e texnologii.
  12. Gladkov L.A., Gladkova N.V. Reshenie dinamicheskix transportny'x zadach na osnove gibridny'x intellektual'ny'x metodov i modelej // Izv. JuFU. Texnicheskie nauki. 2013. № 7 (144). S. 102−107.
  13. Fleischmann B., Gnutzmann S., Sandvob E. Dynamic vehicle routing based on online traffic information // Trans Sci. 2004. V. 38. № 4. P.420−433.
  14. Coslovich L., Pesenti R., Ukovich W. A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem // Eur J Oper Res. 2006. V. 175. № 3. P. 1605−1615.
  15. Ghannadpour S.F., Noori S., Tavakkoli-Moghaddam R. Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers’ satisfaction in supply chain management // IEEE Trans. Eng. Manage. 2013. V. 60. № 4. P. 777−790.
  16. Yingcheng Xu, Li Wang, Yuexiang Yang. Dynamic vehicle routing using an improved variable neighborhood search algorithm // Journal of Applied Mathematics. 2013. V. 13. № 1. P. 1−12.
  17. Englert M., Röglin H., Vöcking B. Worst Case and Probabilistic Analysis of the 2 opt Algorithm for the TSP // Algorithmica. 2014. V. 68. № 1. P. 190−264.
  18. Gubar E., Zubareva M. Optimization of Encashment Routes in ATM Network // Contributions to Game Theory and Management. 2015. V. 5. № 1. P. 121−127.
  19. Archetti C., Savelsbergh M.W.P., Speranza M.G. Worst-case analysis for split delivery vehicle routing problems // Transportation Science. 2006. V. 40. № 2. P. 226−234.
  20. Ling W., Luo H. An adaptive parameter control strategy for ant colony optimization // Computational Intelligence and Security, 2007 International Conference on. IEEE, 2007. P. 142−146.
  21. Archetti C., Savelsbergh M.W.P., Speranza M.G. Worst-case analysis for split delivery vehicle routing problems // Transportation Science. 2006. V. 40. № 2. P. 226−234.
  22. Zhaoquan C.A.I. et al. Ant colony optimization based on adaptive volatility rate of pheromone trail // International Journal of Communications, Network and System Sciences. 2009. V. 2. № 8. P. 792.
  23. Goldberg D.E., Deb K., Clark J.H. Accounting for noise in the sizing of populations // Whitley. 2014. Vol. 2419. P. 127−140.
  24. Ombuki B., Ross B.J., Hanshar F. Multi-objective genetic algorithms for vehicle routing problem with time windows // Applied Intelligence. 2006. V. 24. № 1. P. 17−30.
  25. Zhaoquan C.A.I. et al. Ant colony optimization based on adaptive volatility rate of pheromone trail // International Journal of Communications, Network and System Sciences. 2009. V. 2. № 8. P. 792.
  26. Eiben A.E., Hinterding R., Michalewicz Z. Parameter control in evolutionary algorithms // Evolutionary Computation, IEEE Transactions on. 1999. V. 3. № 2. P. 124−141.

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio