A multi-road quasi network flow model for the vertical alignment optimization of a road network

ABSTRACT

Minimizing earthwork costs is crucial in the optimization of vertical alignment. In this article, the previous quasi network flow model for the vertical alignment optimization of a single road is extended to a multi-road network. A ‘one-at-a-time’ method is first examined to solve the optimization problem and it is noted that this method is effectively what is currently used in practice. Two academic test problems are used to demonstrate that this method is not optimal. This leads to the development of three novel methods to solve the optimization problem: no-flow, with-flow and divide-and-conquer. It is noted that the with-flow method guarantees global optimality. All methods are compared on two real-world case studies. On small road networks, the with-flow method decreases costs by 7.4%, and achieves a 20 times speedup over the one-at-a-time method. On long road networks, the divide-and-conquer method is faster than all other methods without any notable cost difference. However, the divide-and-conquer method is an heuristic and cannot guarantee that it returns a global minimum.

KEYWORDS:

• Road network optimization
• vertical alignment
• mixed integer linear programming
• quasi network

Acknowledgments

Part of the computation in this research was carried out using a software library provided by Softree Technical System Inc.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

Data for the academic tests (Section 4.2) are available by contacting the corresponding author. Data for the real-world tests (Section 4.3) are only available for academic research purposes and requires permission of the authors' industrial partner.

Notes

1 https://www150.statcan.gc.ca/n1/daily-quotidien/220524/dq220524a-eng

Additional information

Funding

This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) [Collaborative Research and Development Grant #CRDPJ 479316-15 sponsored by Softree Technical Systems Inc.]. Part of the research was performed in the Computer-Aided Convex Analysis (CA${}^2$) laboratory funded by a Leaders Opportunity Fund [LOF, John R. Evans Leaders Fund, Funding for research infrastructure] from the Canada Foundation for Innovation (CFI) and by the British Columbia Knowledge Development Fund (BCKDF).