Article

Article title HYBRID ALGORITHM FOR SOLVING VEHICLE ROUTING PROBLEMS WITH A TIME WINDOWS
Authors L.A. Gladkov, N.V. Gladkova
Section SECTION I. EVOLUTIONAL SIMULATION
Month, Year 06, 2016 @en
Index UDC 658.512.2.011.5
DOI
Abstract The article discusses a new approach to the dynamic transportation problems. The urgency and importance of addressing such problems to increase the efficiency of traffic and transport infrastructure. It is noted that of particular interest are certain classes of vehicle routing problems, in particular transport task with a time limit. The features of static and dynamic transport problems. The graphic representation of the dynamic transportation problem. A mathematical formulation of the vehicle routing problem. We define the function evaluation of the quality of the solutions obtained. The method of coding solutions for use in the genetic algorithm. Proposed new modifications crossover and mutation operators, aimed at increasing the diversity of the current population and overcome local optima. Described sequence of operations, and shows the structure of the developed algorithm. The structure and principles of the event manager, which allows you to improve the efficiency of the algorithm, through the organization of the processing of incoming orders again. Based on the analysis found that the effectiveness of these tasks necessary to develop new methods that enable the dynamic change of algorithm parameters, and modify the structure of the algorithm if necessary. An example of the structure of the vector control action on the parame-ters of the genetic algorithm by the fuzzy logic controller. the structure of the vector of the input parameters for the fuzzy logic controller is also described. We conducted a series of numerical experiments to analyze and compare the quality of the solutions, as well as to determine the best values of the control algorithm parameters. Conclusions based on the analysis of the advantages and disadvantages of the proposed algorithm.

Download PDF

Keywords Vehicle routing problems; dynamic vehicle routing problem with time windows; evolutionary calculations; hybrid intellectual methods
References 1. Kazharov A.A., Kureychik V.M. Klassifikatsiya i kriterii optimizatsii zadachi marshrutizatsii avtotransporta [Classification and criteria optimization problem of routing vehicles], Sbornik trudov VII Mezhdunarodnoy nauchno-prakticheskoy konferentsii "Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte" Pproceedings of the VII International scientific-practical conference "Integrated models and soft computing in artificial intelligence"]. Vol. 2. Moscow: Fizmatlit, 2013, pp. 879-886.
2. Emel'yanova T.S. Evristicheskie i metaevristicheskie metody resheniya dinamicheskoy transportnoy zadachi [Heuristic and metaheuristic methods for solving the dynamic transportation problem], Perspektivnye informatsionnye tekhnologii i intellektual'nye sistemy [Advanced Information Technologies and Intelligent Systems], 2007, No. 3 (31), pp. 33-43.
3. Emel'yanova T.S. Analiz metodov resheniya nelineynykh transportnykh zadach [Analysis of methods for solving nonlinear transport problems], Perspektivnye informatsionnye tekhnologii i intellektual'nye sistemy [Advanced Information Technologies and Intelligent Systems], 2007, No. 1 (29), pp. 38-49.
4. Gladkov L.A., Gladkova N.V. Reshenie dinamicheskikh transportnykh zadach na osnove gibridnykh intellektual'nykh metodov i modeley [The decision of dynamic vehicle routing problems on the basis of hybrid intellectual methods and models], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 102-107.
5. Gladkov L.A., Gladkova N.V. Osobennosti i novye podkhody k resheniyu dinamicheskikh transportnykh zadach s ogranicheniem po vremeni [Features and new approaches to the decision of dynamic vehicle routing problems with time windows], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 178-187.
6. Gladkov L.A., Gladkova N.V. Gibridnyy algoritm resheniya transportnykh zadach s ogranicheniem po vremeni [Hybrid algorithm for solving vehicle routing problems with a time windows], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6 (167), pp. 180-191.
7. Emel'yanova T.S. Geneticheskiy algoritm resheniya transportnoy zadachi s ogranicheniem po vremeni [Genetic algorithm for solving transportation problem with time limit], Perspektivnye informatsionnye tekhnologii i intellektual'nye sistemy [Advanced Information Technologies and Intelligent Systems], 2007, No. 4 (32), pp. 43-59.
8. Kureychik V.M., Emel'yanova T.S. Reshenie transportnykh zadach s ispol'zovaniem kombinirovannogo geneticheskogo algoritma [The solution of transport problems using the combined genetic algorithm], Odinnadtsataya natsional'naya konferentsiya po iskusstvennomu intellektu s mezhdunarodnym uchastiem KII-2008: Trudy konferentsii [Eleventh National conference on artificial intelligence with International participation KII-2008: Proceedings of the conference]. Vol. 1. Moscow: Fizmatlit, 2008, pp. 158-164.
9. Gladkov L.A., Kureychik V.M., Kureychik V.V., Sorokoletov P.V. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 365 p.
10. Gladkov L.A., Kureychik V.M., Kureychik V.V., Sorokoletov P.V. Bioinspirirovannye metody v optimizatsii [Bioinspired methods in optimization]. Moscow: Fizmatlit, 2009, 384 p.
11. Herrera F., Lozano M. Fuzzy Genetic Algorithms: Issues and Models. Technical Report DECSAI-98116, Department of Computer Science and A.I., University of Granada, 1999, 25 p.
12. Herrera F., Lozano M. Fuzzy Adaptive Genetic Algorithms: design, taxonomy, and future directions, Soft Computing 7 (2003), Springer-Verlag, 2003, pp. 545-562.
13. Lee M.A., Takagi H. Dynamic Control of Genetic Algorithms using Fuzzy Logic Techniques, Proceeding of 5th International Conference on Genetic Algorithms (ICGA’93), Urbana-Champaign, IL, July 17-21, 1993, pp. 76-83.
14. Nechetkie gibridnye sistemy. Teoriya i praktika [Fuzzy hybrid system. Theory and practice], under the ed. N.G. Yarushkinoy. Moscow: Fizmatlit, 2007, 208 p.
15. Yarushkina N.G. Osnovy teorii nechetkikh i gibridnykh system [Fundamentals of the theory of fuzzy and hybrid systems]. Moscow: Finansy i statistika, 2004, 320 p.
16. Hongbo Liu, Zhanguo Xu, Ajith Abraham Hybrid Fuzzy-Genetic Algorithm Approach for Crew Grouping, Proceedings of the Fifth International Conference on Intelligent Systems Design and Applications (ISDA 2005), 8-10 September 2005, Wroclaw, Poland. IEEE Computer Society 2005, pp. 332-337.
17. Gladkov L.A., Gladkova N.V. Osobennosti ispol'zovaniya nechetkikh geneticheskikh algoritmov dlya resheniya zadach optimizatsii i upravleniya [Features of use of fuzzy genetic algorithms for the decision of problems of optimisation and control], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 4 (93), pp. 130-136.
18. Gladkov L.A., Kureychik V.V., Kureychik V.M., Rodzin S.I. Osnovy teorii evolyutsionnykh vychisleniy: monografiya [Fundamentals of the theory of evolutionary computing: monograph]. Rostov-on-Don: Izd-vo YuFU, 2010.
19. Gladkov L.A., Gladkova N.V., Leiba S.N. Manufacturing Scheduling Problem Based on Fuzzy Genetic Algorithm, Proceedings of IEEE East-West Design & Test Symposium (EWDTS’2014). Kiev, Ukraine, September 26 – 29, 2014, pp. 209-213.
20. Gladkov L.A., Leiba S.N., Gladkova N.V., Legebokov A.A. Parallel Genetic Algoritm Based on Fuzzy Logic Controller for Design Problems, Advances in Intelligent Systems and Computing. Proceedings of the 5th Computer Science On-line Conference 2016 (CSOC 2016), Vol. 1: Artificial Intelligence Perspectives in Intelligent Systems. – Springer Inter-national Publishing, Switzerland, 2016, pp. 147-157.

Comments are closed.