Mixed Integer Linear Programming for Optimal Road Network Design

Optimal road network design is a fundamental problem in infrastructure planning, requiring decisions on which links to construct, upgrade, or rehabilitate to minimise cost while satisfying connectivity, capacity, and equity constraints. This paper presents a comprehensive mixed integer linear programming (MILP) framework for the optimal design of road networks, incorporating binary link-selection variables, continuous flow allocation, multi-commodity demand satisfaction, and multi-objective optimisation extensions. The model is formulated on a directed graph with candidate links characterised by construction costs, capacities, travel times, and social accessibility weights. A Lagrangian relaxation decomposition strategy and a branch-and-bound algorithm augmented with Gomory cutting planes are employed to solve large-scale instances efficiently. The model is validated against two classical benchmarks from the literature and applied to a realistic case study representing the Juba–Malakal road corridor in South Sudan, a 512-kilometre freight and humanitarian supply route traversing floodplains, contested territory, and degraded paving. Results demonstrate that the MILP formulation achieves a 35% cost reduction relative to a greedy heuristic while improving the accessibility index by 28 percentage points for underserved settlements. Multi-objective extensions reveal meaningful trade-offs between economic efficiency, social equity, and environmental impact through a Pareto-frontier analysis. Global sensitivity analysis confirms that budget ceiling and construction cost coefficients are the dominant parameters governing optimal solution quality. The framework provides a rigorous, scalable tool for transport planners, particularly in data-scarce, resource-constrained developin