Mixed-Integer Linear Programming–Based Sensitivity Analysis in Optimization of Temporary Haul Road Layout Design for Earthmoving Operations

Abstract

To promote mixed-integer linear programming (MILP) in engineering applications, it is vitally important to address the question: To what extent is the optimum solution of MILP able to tolerate variations and changes in certain model parameters and still hold valid? This paper has formalized a generic methodology for identifying parameter stability regions for the optimum solution of MILP in order to gain insight into the applicability of the optimum solution. Previous research in regards to MILP sensitivity analysis is reviewed in depth to identify knowledge gaps. Then, we explain how to categorize input parameters into distinct classes with application implications and how to designate the probe and control classes in performing sensitivity analysis. Next, a one-dimensional line search method is proposed to analytically define the stability region for each parameter in the probe class one at a time, whereas parameters in the control class are held at optimum states. Further, the newly proposed methodology is applied to an earthmoving optimization problem formulated in MILP in an attempt to generate the temporary haul road layout design. Important aspects of a case study based on a real-world project in North Alberta, including problem definition, factor identification, data collection, sensitivity analysis, solution verification, and validation, are addressed. In conclusion, this research contributes to MILP-based sensitivity analysis and facilitates the implementation of MILP in complex civil engineering applications.