A branch-and-bound approach for path planning of vehicles under navigation relayed by multiple stations

The optimal path planning problem for vehicles under navigation relayed by multiple stations (OPP-V-NRMS) arises when a vehicle needs to be sequentially navigated by multiple stations to its destination. This problem is a hierarchical mixed-variable constrained optimization problem consisting of determining the optimal arrangement of navigation stations, which is a combinatorial optimization problem, and planning a path based on the determined arrangement, which is a continuous-variable constrained optimization problem. A branch-and-bound approach is proposed for searching the decision tree posed by navigation stations, and a differential evolution based (DE-based) algorithm is applied to find a feasible and high-quality path for the vehicle. Computational results show that the branch-and-bound approach can find the same solution with the exhaustive enumeration approach at a much lower computational cost, and that the exhaustive enumeration approach only works on small-scale cases while the branch-and-bound approach performs satisfactorily on both small-scale and large-scale cases.