Advanced optimization methods for road construction

道路建设是支持高效公路网的重要组成部分。优质公路的成本高达每公里2000万美元，而林业公路的成本从每公里1000美元到100万美元不等。在保持安全标准的同时降低道路建设成本是非常可取的。道路设计也变得越来越复杂。它现在必须考虑到对环境的影响，减轻自然灾害或人为灾害的影响。无论是在加拿大还是在任何发达国家，降低道路建设成本都可能在控制未来预算和保持生活质量方面发挥重要作用。 道路设计问题通常分为三个子问题。首先，平面路线考虑潜在道路选址的卫星视图，选择几个道路备选方案，并确定该道路内的确切路径。下一步，垂直路线考虑开挖或填平哪个山丘，以建造一条在满足安全和法规约束的同时通过水平路线的道路。最后，地球移动问题考虑了要移动多少材料才能实现目标的垂直对准。我们的目标是将当前的大部分手动过程自动化，以节省设计工程师在计算任务上的时间，这样(S)他就可以专注于考虑尽可能多的约束条件。 我们计划完全自动化整个道路设计过程，从走廊选择到土方移动决策。我们的方法侧重于改进求解垂直对齐模型的计算时间，以便我们可以执行广泛的搜索以寻找最便宜的水平对齐。我们将在现有模型中加入更多功能，以更准确地反映建筑过程。虽然目前最先进的优化解算器无法解决完整的问题，但最新的优化算法加上仔细的近似将提供更精确的道路设计，允许工程师考虑更广泛的替代路径，并提供对解决方案的健壮性的洞察。由此产生的模型和算法将在商业道路设计软件中实现和部署，并广泛应用。

Road construction represents a significant portion of supporting an efficient road network. Highway quality roads cost as much as $20 million per km while forestry roads costs from $1,000 to $1 million per km. Reducing road construction costs while maintaining safety standards is very desirable. Road design has also become increasingly more complex. It now has to take into account environmental impact, mitigation of the impact of natural or man-made disasters. Reducing road construction costs may play a major role in controlling future budgets and maintaining quality of life, both in Canada and in any developed country. The road design problem is usually split into three subproblems. First, the horizontal alignment considers a satellite view of the potential road site, selects a handful of corridor alternatives, and determines the exact path within that corridor. Next the vertical alignment considers which hill to cut or ravine to fill to build a road that goes through the horizontal alignment while satisfying safety and regulation constraints. Finally, the earth moving problem considers how much material to move to realize the target vertical alignment. Our goal is to automate much of the current manual process to save design engineers time on computational tasks so (s)he can concentrate on considering as many constraints as possible. We plan to fully automate the full road design process from corridor selection to earthmove decisions. Our approach focuses on improving computation time to solve the vertical alignment model so we can perform an extensive search for the cheapest horizontal alignment. We will incorporate additional features into current models to more precisely reflect the building process. While the complete problem is out of reach of current state-of-the-art optimization solvers, the latest optimization algorithms coupled with carefully approximation will provide much chearper road designs, allow engineers to consider a wider range of alternative paths, and provide insight into the robustness of the solution. The resulting models and algorithms will be implemented and deployed in a commercial road design software, and made widely available.