Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.10922 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918478543323136 |
|---|---|
| author | Abbasov, Majid E. Gorbunova, Anna A. |
| author_facet | Abbasov, Majid E. Gorbunova, Anna A. |
| contents | We consider the problem of finding an optimal 3D road trajectory between two points on a terrain with variable elevation. Unlike common heuristic pathfinding methods, we propose a rigorous framework based on the calculus of variations, introducing an integral cost functional that incorporates material delivery and construction expenses. The existence of a global minimizer is established via the Arzelà--Ascoli theorem. To solve the problem numerically, we develop a dynamic programming scheme and provide a formal convergence proof. We prove that the sequence of piecewise-linear solutions converges to the true optimum when the grid discretization steps follow a specific power-law relation -- specifically, when the vertical step size decays faster than the horizontal one. To enhance efficiency, we introduce a local-search modification that reduces computational complexity to nearly quadratic O(τ^{-2-ε}), where τ is the discretization step along the x-axis. Numerical experiments on 2D and 3D terrains validate the theoretical results, showing that our approach achieves accuracy comparable to the Ritz method while significantly reducing processing time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10922 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal 3D Road Alignment on Topographic Surfaces: A Convergent Dynamic Programming Approach Abbasov, Majid E. Gorbunova, Anna A. Optimization and Control 49L20, 65K10, 90C39 We consider the problem of finding an optimal 3D road trajectory between two points on a terrain with variable elevation. Unlike common heuristic pathfinding methods, we propose a rigorous framework based on the calculus of variations, introducing an integral cost functional that incorporates material delivery and construction expenses. The existence of a global minimizer is established via the Arzelà--Ascoli theorem. To solve the problem numerically, we develop a dynamic programming scheme and provide a formal convergence proof. We prove that the sequence of piecewise-linear solutions converges to the true optimum when the grid discretization steps follow a specific power-law relation -- specifically, when the vertical step size decays faster than the horizontal one. To enhance efficiency, we introduce a local-search modification that reduces computational complexity to nearly quadratic O(τ^{-2-ε}), where τ is the discretization step along the x-axis. Numerical experiments on 2D and 3D terrains validate the theoretical results, showing that our approach achieves accuracy comparable to the Ritz method while significantly reducing processing time. |
| title | Optimal 3D Road Alignment on Topographic Surfaces: A Convergent Dynamic Programming Approach |
| topic | Optimization and Control 49L20, 65K10, 90C39 |
| url | https://arxiv.org/abs/2503.10922 |