RICH VEHICLE ROUTING PROBLEM FOR THE MULTI-ROBOT ENVIRONMENTAL MONITORING
Abstract
The use of coordinated groups of autonomous vehicles seems to be the most promising tech-nology that allows providing operational coverage of hard-to-reach big-scaled regions. At the same time, the task allocation and path-planning problem inevitably arise, as each vehicle in the group must be associated with a series of survey tasks in different areas of the region. The con-struction of a feasible and effective group route is a problem of high computational complexity even for the simple classical formulations with one type of constraint. The paper considers the dynamic routing problem for the group of autonomous vehicles when performing multi-attribute environmental monitoring. The group task here is the well-timed observation of a given set of ob-jects according to the given schedule and specified set of requirements. These requirements may come in various combinations of spatial, temporal or functional constraints. Such routing prob-lems, which combines a whole range of restrictions and requirements of various nature, are pri-marily classified as rich or multi-attribute routing problems. These extended formulations aimed at more accurate real-world problems modeling nowadays are both insufficiently studied and of great scientific research interest. We propose using decentralized hybrid evolutionary approach for the efficient generation of feasible group routes. The proposed approach includes a number of specialized heuristics, advanced local search procedures, and additional solution improvement schemes. Dynamic adjustment of the algorithm’s internal parameters in real time provides the maximum efficiency of the computational procedure both for each specific set of conditions and at each stage of the calculation. The proposed scheme of the evolutionary algorithm demonstrates the high quality results on a large set of test problems, including problems with a high degree of еру objects set heterogeneity.
References
2. Dunbabin M., Marques L. Robots for environmental monitoring: Significant advancements and applications, IEEE Robotics and Automation Magazine, 2012, Vol. 19, No. 1, pp. 24-39.
3. Cissé M., Yalçındağ S., Kergosien Y., etc. OR problems related to Home Health Care: A re-view of relevant routing and scheduling problems, Operations Research for Health Care, 2017, Vol. 13-14, pp. 1-22.
4. Hartl R.F., Hasle G., Janssens G.K. Special Issue on Rich Vehicle Routing Problems, Central European Journal of Operations Research, 2006, Vol. 14, No. 2, pp. 103-104.
5. Caceres Cruz J., Arias P., Guimarans D., Riera D., Juan A. Rich Vehicle Routing Problem: Survey, ACM Computing Surveys, 2014, Vol. 47, pp. 1-28.
6. Drucker N., Penn M., Strichman O. Cyclic Routing of Unmanned Air Vehicles, AUVSI (Asso-ciation for Unmanned Vehicle Systems International), 2010.
7. Drucker N. Cyclic Routing of Unmanned Aerial Vehicles, Ph.D. thesis, Israel Institute of Technology, 2014.
8. Drucker N., Ho H.-M., Ouaknine J., Penn M., Strichman O. Cyclic Routing of Unmanned Air Vehicles, Journal of Computer and System Sciences, 2019, Vol. 103, pp. 18-45.
9. Ho H.-M., Ouaknine J. The cyclic-routing UAV problem is PSPACE-complete, International Con-ference on Foundations of Software Science and Computation Structures, 2015, pp. 328-342.
10. Smith S.L., Rus D. Multi-robot monitoring in dynamic environments with guaranteed currency of observations, 49th IEEE Conference on Decision and Control, 2010, pp. 514-521.
11. Stump E., Michael N. Multi-robot persistent surveillance planning as a Vehicle Routing Prob-lem, 2011 IEEE International Conference on Automation Science and Engineering, 2011, pp. 569-575.
12. Fargeas J. L., Hyun B., Kabamba P., Girard A. Persistent visitation under fuel constraints, 15th meeting of the EURO Working Group on Transportation (EGWT 2012), 2012, pp. 1037-1046.
13. Kenzin M., Bychkov I., Maksimkin, N. Hybrid evolutionary approach to multi-objective mis-sion planning for group of underwater robots, Mathematical Modeling of Technological Pro-cesses, Communications in Computer and Information Science, 2015, Vol. 549, pp. 73-84.
14. Bychkov I.V., Kenzin M.Yu., Maksimkin N.N. Dvukhurovnevyy evolyutsionnyy podkhod k marshrutizatsii gruppy podvodnykh robotov v usloviyakh periodicheskoy rotatsii sostava [A two-level evolutionary approach to routing a group of underwater robots in the conditions of periodic rotation of the composition], Trudy SPIIRAN [SPIIRAS Proceedings], 2019, No. 2 (18), pp. 267-301.
15. Braysy O., Dullaert W., Gendreau M. Evolutionary Algorithms for the Vehicle Routing Prob-lem with Time Windows, Journal of Heuristics, 2004, Vol. 10, No. 6, pp. 587-611.
16. Laporte G., Ropke S., Vidal T. Chapter 4: Heuristics for the Vehicle Routing Problem, Vehicle Routing, 2014, pp. 87-116.
17. Koc C., Bektas T., Jabali O., Laporte G. Thirty years of heterogeneous vehicle routing, Euro-pean Journal of Operational Research, 2016, Vol. 249, No. 1, pp. 1-21.
18. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 1987, Vol. 35, pp. 254-265.
19. Vidal T., Crainic T.G., Gendreau M., Prins C. A hybrid genetic algorithm with adaptive diver-sity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research, 2013, Vol. 40, No. 1, pp. 475-489.
20. Yong M. Solving vehicle routing problem with time windows with hybrid evolutionary algo-rithm, In proceeding of Intelligent Systems (GCIS), 2010 Second WRI Global Congress on, 2010, Vol. 1, pp. 335-339.
21. Or I. Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking – Northwestern University, Evanston, Illinois, 1976.
