Article

Article title HYBRID ALGORITHM FOR SOLVING VEHICLE ROUTING PROBLEMS WITH A TIME WINDOWS
Authors L.A. Gladkov, N.V. Gladkova
Section SECTION V. NEW INFORMATION TECHNOLOGIES
Month, Year 06, 2015 @en
Index UDC 658.512.2.011.5
DOI
Abstract The article deals with new approaches to solving vehicle routing. The urgency and importance of addressing such problems to increase the efficiency and the development of transport infrastructure in the regions. It is noted that some special interest classes vehicle routing problems, in particular transport problem with a time limit. The mathematical formulation of the problem of routing vehicles in terms of graph theory. We define the function evaluation of the quality of the solutions obtained. Formulated and written in the form of mathematical expressions limit considered optimization problem. The technique of coding solutions for use in the genetic algorithm. Proposed new versions of crossover and mutation operators to increase the diversity of the current population and overcome local optima. The structure of the algorithm. Based on the analysis found that the effectiveness of these tasks necessary to develop new methods that enable the dynamic change of the parameters of the algorithm and, if necessary, to modify the structure of the algorithm. New approaches to the construction of hybrid methods of solution based on a combination of genetic research methods and mathematical models and fuzzy linguistic variables. The principle of action and shows the mechanism of the fuzzy logic controller. Examples of the control action on the parameters of the genetic algorithm from the fuzzy logic controller. We carried out a series of numerical experiments to analyze and compare the quality of the decisions with the results known test cases (benchmark). Based on the analysis conclusions about 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. 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.
2. 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.
3. Kazharov A.A., Kureychik V.M. Klassifikatsiya i kriterii optimizatsii zadachi marshru-tizatsii avtotransporta [Classification and criteria optimization problem of routing vehicles], Sbornik trudov VII Mezhdunarodnoy nauchno-prakticheskoy konferentsii "Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte" [Proceedings of the VII International scientific-practical conference "Integrated models and soft computations in artificial intelligence"]. Vol. 2. Moscow: Fizmatlit, 2013, pp. 879-886.
4. Emel'yanova T.S. Evristicheskie i metaevristicheskie metody resheniya dinamicheskoy transportnoy zadachi [Heuristic and metaheuristic methods for solving dynamic transport problems], Perspektivnye informatsionnye tekhnologii i intellektual'nye sistemy [Perspective Information Technologies and Intelligent Systems], 2007, No. 3 (31), pp. 33-43.
5. 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 [Perspective Information Technologies and Intelligent Systems], 2007, No. 1 (29), pp. 38-49.
6. Emel'yanova T.S. Geneticheskiy algoritm resheniya transportnoy zadachi s ogranicheniem po vremeni [Genetic algorithm for solving transportation problem with time restriction], Perspektivnye informatsionnye tekhnologii i intellektual'nye sistemy [Perspective Information Technologies and Intelligent Systems], 2007, No. 4 (32), pp. 43-59.
7. Kureychik V.M., Emel'yanova T.S. Reshenie transportnykh zadach s ispol'zovaniem kombinirovannogo geneticheskogo algoritma [The solution of transport problems using a 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 CAI-2008. Proceedings of the conference]. Vol. 1. Moscow: Fizmatlit, 2008, pp. 158-164.
8. 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.
9. 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.
10. Herrera F., Lozano M. Fuzzy Adaptive Genetic Algorithms: design, taxonomy, and future directions, Soft Computing, 2003, No. 7, pp. 545-562.
11. 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.
12. Gladkov L.A. Reshenie zadach i optimizatsii resheniy na osnove nechetkikh geneticheskikh algoritmov i mnogoagentnykh podkhodov [Solving problems and optimizing solutions based on fuzzy genetic algorithms and multi-agent approaches], Izvestiya TRTU [Izvestiya TSURe], 2006, No. 8 (63), pp. 83-88.
13. Gladkov L.A. Osobennosti razrabotki i nastroyki nechetkogo logicheskogo kontrollera [The design and tuning of fuzzy logic controller], Intellektual'nye sistemy. Kollektivnaya monografiya [An intelligent system. Collective monograph]. Issue 6. Rostov-on-Don: Izd-vo YuFU, 2013, pp. 262-279.
14. 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.
15. Batyrshin I.Z., Nedosekin A.O. i dr. Nechetkie gibridnye sistemy. Teoriya i praktika [Fuzzy hybrid system. Theory and practice], Under ed. N.G. Yarushkinoy. Moscow: Fizmatlit, 2007, 208 p.
16. Yarushkina N.G. Osnovy teorii nechetkikh i gibridnykh system [Basic theory of fuzzy and hybrid systems]. Moscow: Finansy i statistika, 2004, 320 p. 17. 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.
18. Gladkov L.A., Kureychik V.V., Kureychik V.M., Rodzin S.I. Osnovy teorii evolyutsionnykh vychisleniy. Monografiya [Basic theory of evolutionary computation. 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., Gladkova N.V., Leiba S.N. Electronic Computing Equipment Schemes Elements Placement Based on Hybrid Intelligence Approach, Intelligent Systems in Cybernetics and Automation Theory. Proceedings of the 4th Computer Science On-line Conference 2015 (CSOC2015), Vol. 2: Intelligent Systems in Cybernetics and Automation Theory. “Advances in
Intelligent Systems and Computing”, Vol. 348, Springer International Publishing Switzerland, 2015, pp. 35-45.

Comments are closed.