Multi-haul quasi network flow model for vertical alignment optimization

ABSTRACT

The vertical alignment optimization problem for road design aims to generate a vertical alignment of a new road with a minimum cost, while satisfying safety and design constraints. A new model called multi-haul quasi network flow (MH-QNF) for vertical alignment optimization is presented with the goal of improving the accuracy and reliability of previous mixed integer linear programming models. The performance of the new model is compared with two state-of-the-art models in the field: the complete transportation graph (CTG) and the quasi network flow (QNF) models. The numerical results show that, within a 1% relative error, the proposed model is robust and solves more than 93% of test problems compared to 82% for the CTG and none for the QNF. Moreover, the MH-QNF model solves the problems approximately eight times faster than the CTG model.

KEYWORDS:

• Vertical alignment
• road design optimization
• mixed integer linear programming model
• earthwork allocation
• variable hauling costs

Acknowledgments

The authors acknowledge the original ideas and concepts of Dr Donovan Hare, which contributed to the quasi network flow model.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. The use of three haul types is very typical in road design, often consisting of free haul, over haul, and end haul; the haul types were labelled short, middle and long to emphasize that the hauling types do not have to be these three—nor does the number of haul types have to be three.

2. Special ordered set (SOS) variables are used in a technique of mixed integer linear programming for dealing with sets of ordered integer variables where a fixed number of consecutive variables must take the value one and all other variables must be zero. Their use in this model is linked to how side slopes are modelled, which is not necessary to understand for the remainder of this article—see Hare et al. (2014) for more information.

Additional information

Funding

This work was supported by a Collaborative Research and Development (CRD) grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) [Grant #CRDPJ 411318-10], which was sponsored by Softree Technical Systems Inc. This work was also supported by NSERC Discovery Grants: [Grant #355571-2013] (Hare) and [Grant #298145-2013] (Lucet). Part of the research was performed in the Computer-Aided Convex Analysis (CA2) laboratory funded by a Leaders Opportunity Fund (LOF) from the Canada Foundation for Innovation (CFI) and by a British Columbia Knowledge Development Fund (BCKDF).