TIME-OPTIMAL ROUTING IN DYNAMIC ENVIRONMENTS WITH  SOFT OBSTACLES: A GEOMETRIC-OPTICS APPROACH

Phạm Thị Liên; Trần Tuấn Việt; Dương Thị Quy

doi:10.34238/tnu-jst.13664

TIME-OPTIMAL ROUTING IN DYNAMIC ENVIRONMENTS WITH SOFT OBSTACLES: A GEOMETRIC-OPTICS APPROACH

About this article

Received: 23/09/25 Revised: 06/11/25 Published: 06/11/25

Authors

1. Pham Thi Lien, TNU - University of Information and Communication Technology
2. Tran Tuan Viet, TNU - University of Information and Communication Technology
3. Duong Thi Quy , TNU - University of Information and Communication Technology

Abstract

The transportation routing problem in environments with dynamically changing characteristics has attracted research interest for many years. Formulating and solving the optimal path-finding problem is a practical necessity, especially as delivery costs continue to rise and often approach the value of the goods. This study minimizes delivery time rather than travel distance. To build an application model for the routing problem, we adopt the geometric-optics method proposed by A. L. Kazakov and A. A. Lempert (2011), based on the principle of light propagation in an optically inhomogeneous medium. Our algorithm constructs an optimal route in environments with both static and moving obstacles, particularly when obstacles possess soft influence regions—that is, the space around an obstacle is not completely blocked but incurs increasing impedance as one approaches the obstacle’s center. This influence is modeled as a distance-dependent increase, reflecting changing travel conditions within the obstructed area. Several computational test models were conducted, demonstrating the effectiveness of the modeling tools and the proposed algorithm in adapting to complex dynamic environments and nonlinear obstacle structures.

Keywords

Routing problems; Optimization; Optical geometry methods; Optimal path; Eikonal equations

Full Text:

PDF (Tiếng Việt)

References

[1] M. Huptych and S. Rock, “Real-time path planning in dynamic environments for unmanned aerial vehicles using the curve-shortening flow method,” International Journal of Advanced Robotic Systems, vol. 18, no. 1, pp. 1–16, January-February 2021.

[2] E. I. Veremei and M. V. Sotnikova, “Optimal Routing Based on Weather Forecast,” International Journal of Open Information Technologies, vol. 4, no. 3, pp. 55–61, 2016.

[3] M. E. Khaili, “Path planning in a dynamic environment,” International Journal of Advanced Computer Science and Applications, vol. 5, no. 8, pp. 86–92, 2014.

[4] A. V. Sarapulov, “Methods for solving the problem of constructing a trajectory for an unmanned aerial vehicle in a dynamic environment,” Rocket and Space Technology, vol. 1, no. 2, pp. 92–99, 2017.

[5] A. Vemula, K. Muelling, and J. Oh, “Path planning in dynamic environments with adaptive dimensionality,” Proceedings of the International Symposium on Combinatorial Search, 2016, doi: 10.1609/socs.v7i1.18386.

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

[7] W. Zhu, D. Jia, H. Wan, T. Yang, C. Hu, K. Qin, and X. Cui, “Waypoint graph based fast pathfinding in dynamic environment,” International Journal of Distributed Sensor Networks, vol. 11, no. 8, 2015, Art. no. 238727.

[8] M.-K. Ng, Y.-W. Chong, K.-M. Ko, Y.-H. Park, and Y.-BLeau, “Adaptive path finding algorithm in dynamic environment for warehouse robot,” Neural Computing and Applications, vol. 32, pp. 13155–13171, 2020.

[9] I. V. Bychkov, M. Yu. Kenzin, and N. N. Maksimkin, “A Two-Level Evolutionary Approach to Routing a Group of Underwater Robots under Periodic Rotation of the Composition,” Proceedings of SPIIRAS, vol. 18, no. 2, pp. 267–301, 2019.

[10] S. Ulyanov, I. Bychkov, and N. Maksimkin, “Event-based path-planning and path-following in unknown environments for underactuated autonomous underwater vehicles,” Applied Sciences, vol. 10, no. 21, 2020, Art. no. 7894.

[11] A. Kazakov and A. Lempert, “An approach to optimization in transport logistics,” Automation and Remote Control, vol. 72, no. 7, pp. 1398–1404, 2011.

[12] A. L. Kazakov and A. A. Lempert, “On the route construction in changing environments using solutions of the Eikonal equation,” Izvestia of the Institute of Mathematics and Informatics of Udmurt State University, no. 58, pp. 1–14, 2021.

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

DOI: https://doi.org/10.34238/tnu-jst.13664

Refbacks

There are currently no refbacks.



Remember me