On the route construction in changing environments using solutions of the eikonal equation

A. L. Kazakov ; A. A. Lempert

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 58 (2021), pp. 59-72.

Résumé

The article deals with the vehicle routing problem in an environment with dynamically changing properties. The problem is relevant in current conditions when the delivery cost has a steady upward trend and is often comparable to the cost of the product itself. A central feature of the study is that the optimality criterion is the minimum delivery time, but not the distance traveled. The optical-geometric approach developed by the authors, based on the analogy between the propagation of light in an optically inhomogeneous medium and the minimization of the integral functional, is used as a research tool. We use exact and approximate solutions of the eikonal equations to describe wave fronts. Two original numerical algorithms for route construction are proposed and implemented as software. A computational experiment is performed that justified the effectiveness of the proposed model-algorithmic tools.

Détail

Keywords: vehicle routing problem, optimization, optical-geometric approach, computational algorithm.
Mots-clés : eikonal equation

Bibliographie

[1] Gutin G., Punnen A., The traveling salesman problem and its variations, Springer, Boston, 2007 | DOI | Zbl

[2] Toth P., Vigo D., Vehicle routing: problems, methods, and applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014 | DOI | Zbl

[3] Gimadi E. Kh., Khachai M. Yu., Extreme problems on sets of permutations, UMC UPI, Yekaterinburg, 2016

[4] Chentsov A. G., Chentsov P. A., “To the question of optimization of the starting point in the routing problem with restrictions”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 55 (2020), 135–154 (in Russian) | DOI | Zbl

[5] Beresneva E., Avdoshin S., “Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution”, Proceedings of the Institute for System Programming of the RAS, 30:3 (2018), 233–250 | DOI

[6] Atyabi A., Powers D. M. W., “Review of classical and heuristic-based navigation and path planning approaches”, International Journal of Advancements in Computing Technology, 5 (2013), 1–14

[7] Yang L., Qi J., Song D., Xiao J., Han J., Xia Y., “Survey of robot 3D path planning algorithms”, Journal of Control Science and Engineering, 2016 (2016), 7426913 | DOI | Zbl

[8] Injarapu A. S. H. H. V., Gawre S. K., “A survey of autonomous mobile robot path planning approaches”, International Conference on Recent Innovations in Signal processing and Embedded Systems (RISE), 2017, 624–628 | DOI

[9] Youakim D., Ridao P., “Motion planning survey for autonomous mobile manipulators underwater manipulator case study”, Robotics and Autonomous Systems, 107 (2018), 20–44 | DOI

[10] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numerische mathematik, 1:1 (1959), 269–271 | DOI | Zbl

[11] Floyd R. W., “Algorithm 97: Shortest path”, Communications of the ACM, 5:6 (1962), 345 | DOI

[12] Warshall S., “A theorem on boolean matrices”, Journal of the ACM, 9:1 (1962), 11–12 | DOI | Zbl

[13] Matthews J., “Basic A* pathfinding made simple”, AI Game Programming Wisdom, Charles River Media, Boston, 2002, 105–113

[14] Stentz A., “Optimal and efficient path planning for partially-known environments”, Proceedings of the 1994 IEEE International Conference on Robotics and Automation, 1994, 3310–3317 | DOI

[15] Kunz T., Reiser U., Stilman M., Verl A., “Real-time path planning for a robot arm in changing environments”, 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010, 5906–5911 | DOI

[16] Veremei E. I., Sotnikova M. V., “Optimal routing based on weather forecast”, International Journal of Open Information Technologies, 4:3 (2016), 55–61 (in Russian)

[17] Shin Y. W., Abebe M., Noh Y., Lee S., Lee I., Kim D., Bae J., Kim K. C., “Near-optimal weather routing by using improved A* algorithm”, Applied Sciences, 10:17 (2020), 6010 | DOI

[18] Pennino S., Gaglione S., Innac A., Piscopo V., Scamardella A., “Development of a new ship adaptive weather routing model based on seakeeping analysis and optimization”, Journal of Marine Science and Engineering, 8:4 (2020), 270 | DOI

[19] El Khaili M., “Path planning in a dynamic environment”, International Journal of Advanced Computer Science and Applications, 5:8 (2014), 86–92 | DOI

[20] Sarapulov A. V., “Methods for solving the problem of constructing a trajectory for an unmanned aerial vehicle in a dynamic environment”, Raketno-kosmicheskaya Tekhnika, 1:2(10) (2017), 92–99 (in Russian)

[21] Vemula A., Muelling K., Oh J., Path planning in dynamic environments with adaptive dimensionality, 2016, arXiv: 1605.06853 [cs.RO] | Zbl

[22] Gochev K., Cohen B., Butzke J., Safonova A., Likhachev M., “Path planning with adaptive dimensionality”, The Fourth International Symposium on Combinatorial Search (SoCS-2011), 2011 https://repository.upenn.edu/hms/175 | Zbl

[23] Jia D., Hu C., Qin K., Cui X., “Planar waypoint generation and path finding in dynamic environment”, International Conference on Identification, Information and Knowledge in the Internet of Things, 2014, 206–211 | DOI

[24] Zhu W., Jia D., Wan H., Yang T., Hu C., Qin K., Cui X., “Waypoint graph based fast pathfinding in dynamic environment”, International Journal of Distributed Sensor Networks, 11:8 (2015), 238727 | DOI

[25] Ng M.-K., Chong Y.-W., Ko K.-m., Park Y.-H., Leau Y.-B., “Adaptive path finding algorithm in dynamic environment for warehouse robot”, Neural Computing and Applications, 32 (2020), 13155–13171 | DOI

[26] Masehian E., Katebi Y., “Robot motion planning in dynamic environments with moving obstacles and target”, World Academy of Science, Engineering and Technology, 29 (2007), 107–112

[27] Du Toit N. E., Burdick J. W., “Robot motion planning in dynamic, uncertain environments”, IEEE Transactions on Robotics, 28:1 (2012), 101–115 | DOI

[28] Abiyev R. H., Akkaya N., Aytac E., “Navigation of mobile robot in dynamic environments”, 2012 IEEE International Conference on Computer Science and Automation Engineering (CSAE), 2012, 480–484 | DOI

[29] Gilimyanov R. F., Rapoport L. B., “Path deformation method for robot motion planning problems in the presence of obstacles”, Automation and Remote Control, 74:12 (2013), 2163–2172 | DOI

[30] Bychkov I., Kenzin M., Maksimkin N., “Two-level evolutionary approach to persistent surveillance for multiple underwater vehicles with energy constraints”, SPIIRAS Proceedings, 18:2 (2019), 267–301 (in Russian) | DOI

[31] Ulyanov S., Bychkov I., Maksimkin N., “Event-based path-planning and path-following in unknown environments for underactuated autonomous underwater vehicles”, Applied Sciences, 10:21 (2020), 7894 | DOI

[32] Geng K., Chulin N. A., “Algorithm guidance for movement with possibility of quadcopters avoiding obstacles and tracking planned route based on the normal acceleration controlling”, Problemy Sovremennoi Nauki i Obrazovaniya, 2016, no. 31(73), 6–28 (in Russian)

[33] Kazakov A. L., Lempert A. A., “An approach to optimization in transport logistics”, Automation and Remote Control, 72:7 (2011), 1398–1404 | DOI | Zbl

[34] Feynman R. P., Leighton R. B., Sands M., Feynman lectures on physics, v. 3, Quantum mechanics, Addison Wesley, 1971

[35] Cassel K. W., Variational methods with applications in science and engineering, Cambridge University Press, Cambridge, 2013 | Zbl

[36] Borovskikh A. V., “The two-dimensional eikonal equation”, Siberian Mathematical Journal, 47:5 (2006), 813–834 | DOI | Zbl

[37] Borovskikh A. V., “Eikonal equation for anisotropic media”, Journal of Mathematical Sciences, 197 (2014), 248–289 | DOI | Zbl

[38] Kabanikhin S. I., Krivorotko O. I., “Numerical solution eikonal equation”, Sibirskie Èlektronnye Matematicheskie Izvestiya, 10 (2013), 28–34 (in Russian)