3D constrained Hybrid A*: Improved vehicle path planning algorithm for cost-effective road alignment design

Optimizing construction costs in road alignment design is essential. Coordinating precise horizontal, vertical, and cross-sectional designs ensures optimization accuracy but increases the problem complexity, leading most existing studies to adopt various simplifications in these designs to maintain solvability. To address this issue, this paper extends the Hybrid A*, an advanced plane vehicle path planning algorithm, into three dimensions to coordinate these designs effectively. The extended algorithm decomposes road alignments into smoothly connected continuous 3D vectors, inherently preserving precise horizontal, vertical, and cross-section geometric information while automatically incorporating horizontal, vertical, and horizontal-vertical spatial constraints. Validation on two mountainous road design cases shows the proposed algorithm, 3D constrained Hybrid A*, effectively produces road alignments within minutes and provides accurate construction cost estimations, with relative errors less than 1% verified by commercial software. This work offers a new perspective on automated road alignment design using smoothly connected 3D vectors and global search strategy.