Mixed Integer Linear Programming for Optimal Road Network Design

Full Text

African Journal of Applied Mathematics: Foundations for Engineering Systems | Vol. 1 , No. 4 , 202 6 AFRICAN JOURNAL OF APPLIED MATHEMATICS: FOUNDATIONS FOR ENGINEERING SYSTEMS Vol. 1 , No. 4 , pp. 1–22, 202 6 DOI: 10. XXXXX /AJMFES.2025.042 Received: Jan uary 202 6 | Revised: January 202 6 | Accepted: Feb 202 6 | Published: March 202 6 Mixed Integer Linear Programming for Optimal Road Network Design Aduot Madit Anhiem Department of Civil Engineering, Universiti Teknologi PETRONAS, Seri Iskandar 32610, Perak, Malaysia Correspondence: aduot.madit2022@gmail.com — ◆ ◆ ◆ — Abstract 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 developing-country contexts. Keywords: mixed integer linear programming; road network design; branch-and-bound; Lagrangian relaxation; Gomory cuts; multi-objective optimisation; Pareto frontier; network flow; transport infrastructure; South Sudan. — ◆ ◆ ◆ — 1. INTRODUCTION The planning and design of road networks constitutes one of the most consequential and computationally demanding challenges in infrastructure engineering. Decision-makers must simultaneously determine which potential road links to construct or upgrade, how traffic flows are routed across the resulting network, and how limited capital budgets are allocated across competing projects spanning multiple years and jurisdictions. The scale, combinatorial complexity, and multi-stakeholder nature of these decisions render intuitive or manual approaches fundamentally inadequate for large networks, creating a compelling need for rigorous mathematical programming methodologies. Mixed integer linear programming (MILP) has emerged over the past four decades as the dominant mathematical framework for road network design, primarily because it can represent binary link-selection decisions—construct or do not construct a given road segment—within a coherent linear objective and constraint structure that guarantees globally optimal or near-optimal solutions under well-defined algorithmic procedures (Magnanti and Wong, 1984). Unlike heuristic or metaheuristic approaches such as genetic algorithms or simulated annealing, MILP-based methods provide certifiable optimality bounds and facilitate systematic sensitivity analysis with respect to uncertain parameters—capabilities of particular value to public-sector decision-makers who must defend infrastructure investment choices to oversight bodies and affected communities. The road network design problem (RNDP) has been extensively studied in the operations research and transportation science literature since the seminal contributions of Beckmann et al. (1956) and the subsequent introduction of fixed-charge network design formulations by Balinski (1961). The fundamental tension in the RNDP lies between investment cost minimisation and service quality maximisation: constructing more links reduces travel times and improves accessibility but increases capital expenditure. In practice, additional constraints relating to minimum connectivity, environmental preservation areas, land acquisition, and social equity further enrich the problem structure, often demanding multi-objective formulations that navigate the Pareto frontier between competing objectives (Friesz et al., 1992). Despite a rich academic literature on RNDP methodologies, the practical application of MILP-based road network optimisation in sub-Saharan Africa has been severely limited. Transport planning in the region has historically relied on ad hoc prioritisation, donor-driven project lists, and simplified cost-benefit analyses that fail to exploit network interdependencies and multi-commodity flow dynamics (Gwilliam, 2011). South Sudan represents an extreme case: a nation with one of the lowest road density figures globally (0.04 km per km²), where road network decisions directly govern access to food, healthcare, and economic markets for millions of isolated rural communities (World Bank, 2021). The Juba–Malakal corridor, which serves as both the primary inland trade route and a critical humanitarian supply line, exemplifies the high-stakes character of network design decisions in this context. The objectives of this paper are threefold: (i) to formulate a comprehensive MILP model for the road network design problem incorporating binary link selection, multi-commodity flow, capacity constraints, and multi-objective extensions; (ii) to implement and evaluate solution algorithms—specifically branch-and-bound with Gomory cutting planes and Lagrangian relaxation—across a range of problem sizes; and (iii) to apply the framework to the Juba–Malakal corridor case study, comparing MILP-optimal designs against greedy heuristic baselines on cost, accessibility, and benefit–cost criteria. The remainder of the paper is structured as follows: Section 2 reviews the relevant literature; Section 3 presents the mathematical formulation; Section 4 describes solution methodology; Section 5 validates the model; Section 6 presents results and discussion; Section 7 analyses sensitivity and multi-objective trade-offs; Section 8 presents the case study; and Section 9 concludes. Figure 1. Illustrative road network design comparison: (a) heuristic 11-link design at $80M total cost; (b) MILP-optimal 9-link design at $52M, achieving 35% cost savings while fully serving all demand nodes. Node symbols: squares = source, circles = demand, triangles = transit. 2. LITERATURE REVIEW 2.1 Classical Network Design Formulations The fixed-charge network design problem (FCNDP), which underlies most road network design formulations, was formalised by Balinski (1961) and subsequently extended to multi-commodity settings by Magnanti and Wong (1984), who also provided the first comprehensive review of polyhedral approaches to network design. The FCNDP introduces binary variables yₑ ∈ {0,1} for each candidate edge e, multiplied by a fixed cost fₑ that is incurred whenever the edge is included in the network. Variable costs cₑ per unit flow on edge e complete the cost structure. Magnanti and Wong demonstrated that the LP relaxation of the FCNDP is generally weak—the integrality gap can be arbitrarily large—motivating the development of valid inequalities, lifting procedures, and decomposition strategies to tighten the formulation. 2.2 Multi-Commodity Flow Extensions Real road networks carry multiple distinct traffic commodities—passenger vehicles, freight, agricultural produce, humanitarian supplies—whose flows must be jointly optimised subject to shared link capacity constraints. The multi-commodity flow (MCF) formulation models each commodity k ∈ K with its own set of origin-destination flow variables xₑᵏ and demand dₖ, coupled to the binary design variables through coupling constraints that enforce capacity limits only on open links (Crainic, 2000). The MCF formulation substantially increases problem size: for a network with |E| edges, |K| commodities, and |V| nodes, the LP relaxation has O(|E||K|) continuous variables and O(|V||K|) flow conservation constraints. Efficient solution therefore demands column generation, Dantzig-Wolfe decomposition, or Benders decomposition (Costa, 2005). 2.3 Branch-and-Bound and Cutting Plane Methods Branch-and-bound (B&B) remains the workhorse algorithm for exact MILP solution, explored systematically since the work of Land and Doig (1960). Modern implementations within solvers such as CPLEX and Gurobi incorporate automatic presolve, cut generation, primal heuristics, and node selection strategies that collectively reduce the B&B tree by orders of magnitude compared with naive branching (Achterberg and Wunderling, 2013). Gomory cutting planes, derived from the fractional LP relaxation solution via the Chvatal-Gomory procedure, are particularly effective for network design problems, tightening the LP bound and reducing the number of B&B nodes by 40–80% in benchmark instances (Nemhauser and Wolsey, 1988). Lift-and-project cuts and flow cover inequalities provide further tightening for MCF-based formulations. 2.4 Lagrangian Relaxation and Decomposition Lagrangian relaxation (LR) dualises complicating constraints—typically the coupling capacity or budget constraints—into the objective function using multipliers λ, decomposing the relaxed problem into independent sub-problems amenable to efficient solution (Fisher, 1981). The LR bound provides a valid lower bound for the MILP, and the optimal dual multipliers guide primal solution recovery through LR heuristics. For road network design, LR of the capacity coupling constraints yields an independent binary shortest-path sub-problem per commodity, solvable in O( |E| log |V|) time (Benders and Van Nunen, 1983). Subgradient optimisation updates the multipliers iteratively until the duality gap falls below a prescribed tolerance. 2.5 Multi-Objective Optimisation Infrastructure network design is inherently multi-objective, balancing economic efficiency (minimise cost), social equity (maximise accessibility for underserved populations), and environmental impact (minimise ecological footprint) (Miettinen, 1999). Weighted-sum scalarisation converts the multi-objective problem into a sequence of single-objective MILPs parameterised by weight vectors, tracing the Pareto frontier through successive solves. The ε-constraint method, which optimises one objective while bounding the others, is preferable for generating well-distributed Pareto solutions and can be implemented within existing B&B solvers without modification (Mavrotas, 2009). For road network design in developing countries, equity-weighted accessibility metrics—which assign higher weights to links serving isolated or low-income communities—have been advocated by Loureiro and Ralston (1996) and more recently by Banerjee et al. (2020). 2.6 Applications in Developing-Country Contexts The application of MILP methods to road network design in sub-Saharan Africa remains nascent. Early work by Harral and Faiz (1988) established benefit-cost frameworks for African road investment without formal integer programming. Gwilliam (2011) reviewed transport policy failures in the region, attributing poor outcomes partly to ad hoc project selection. More recent studies by Muñoz-Villamizar et al. (2021) applied facility location MILP models to humanitarian logistics in conflict-affected zones, demonstrating 22–38% cost reductions relative to heuristic baseline plans. Specific MILP-based road network optimisation for South Sudan has not previously been reported in the peer-reviewed literature, representing the primary novelty contribution of the present work. 3. MATHEMATICAL FORMULATION 3.1 Problem Definition and Graph Structure Let G = (V, E) denote a directed graph where V = {1, 2, …, n} is the set of nodes representing settlements, junctions, or terminals, and E ⊆ V × V is the set of candidates directed links. Each link e = (i, j) ∈ E is characterised by a fixed construction or upgrading cost fₑ ($ million), a unit variable transport cost cₑ ($/tonne·km), a capacity uₑ (tonnes/day), a length lₑ (km), and a binary indicator of existing status aₑ ∈ {0, 1}. Let K denote the set of origin-destination commodity pairs, where each commodity k ∈ K has origin oₖ, destination dₖ, and demand volume dₖ (tonnes/day). 3.2 Decision Variables Two classes of decision variables are defined: (i) binary link-selection variables yₑ ∈ {0, 1} for each candidate link e ∈ E, where yₑ = 1 indicates that link e is constructed or upgraded and included in the network design; and (ii) continuous flow variables xₑᵏ ≥ 0 representing the volume of commodity k ∈ K routed through link e ∈ E. Additionally, binary phase variables yₑᵗ ∈ {0, 1} are introduced for multi-period extensions to capture the scheduling of link construction across planning horizon T. 3.3 Objective Function The primary objective minimises the total lifecycle network cost, comprising fixed construction costs and discounted variable transport costs over the planning horizon: (1) In the multi-objective extension, the accessibility objective is formulated as the weighted coverage of demand nodes, where wᵢ is the social vulnerability weight of node i: (2) The environmental objective minimises land disturbance, proxied by total construction length weighted by ecological sensitivity coefficients sₑ: (3) 3.4 Constraints The MILP model is subject to the following constraints. Flow conservation at each node i ∈ V for each commodity k ∈ K enforces the Kirchhoff law: Σₑ∈ δ + i xₑᵏ - Σₑ∈ δ - i xₑᵏ = bᵢᵏ ∀ i ∈ V, k ∈ K (4) where bᵢᵏ = dₖ if i = oₖ, bᵢᵏ = −dₖ if i = dₖ, and bᵢᵏ = 0 otherwise. Link capacity constraints restrict total multi-commodity flow through each link to its design capacity, which is zero for unselected links: Σₖ∈K xₑᵏ ≤ uₑ yₑ ∀ e ∈ E (5) Budget constraints bound the total construction expenditure within each planning period t: Σₑ∈E fₑ yₑᵗ ≤ Bᵗ ∀ t ∈ T (6) Logical constraints ensure that an existing link (aₑ = 1) remains open and that a selected link is built in exactly one phase: yₑ ≥ aₑ ∀ e ∈ E (7) Σₜ∈T yₑᵗ = yₑ ∀ e ∈ E (8) Binary and non-negativity requirements complete the formulation: yₑ, yₑᵗ ∈ {0, 1} ∀ e ∈ E, t ∈ T (9) xₑᵏ ≥ 0 ∀ e ∈ E, k ∈ K (10) 3.5 Valid Inequalities To strengthen the LP relaxation, three classes of valid inequalities are added to the formulation. First, connectivity cuts ensure that every demand node is reachable from at least one source: for each subset S ⊂ V containing at least one demand node but no source, the cut-set inequality enforces Σₑ∈δ(S) yₑ ≥ 1. Second, flow-cover inequalities derived from the capacity coupling constraints (5) are lifted to provide tighter bounds on partial link selections. Third, Gomory fractional cuts are generated dynamically during branch-and-bound from the optimal LP relaxation tableaux, reducing the integrality gap by an average of 42% in the test instances considered. 4. SOLUTION METHODOLOGY 4.1 LP Relaxation and Integrality Gap The LP relaxation of the MILP is obtained by replacing the integrality constraint (9) with 0 ≤ yₑ ≤ 1. The LP relaxation is solved using the simplex method or interior-point methods, providing a lower bound ZLP ≤ Z* for the optimal integer objective Z*. The integrality gap, defined as (Z* − ZLP) / Z*, quantifies the difficulty of the instance: gaps exceeding 10% signal the need for enhanced cut generation or decomposition. For the benchmark instances considered, LP relaxation gaps range from 0.0% for small networks (n ≤ 20) to 18.2% for large instances (n = 200), motivating the algorithmic enhancements described below. 4.2 Branch-and-Bound with Cutting Planes The branch-and-bound algorithm maintains a search tree of sub-problems, each defined by fixing subsets of binary variables. At each node, the LP relaxation is solved; if the relaxation is infeasible or its bound exceeds the current best integer solution (incumbent), the node is pruned. Otherwise, a fractional binary variable yₑ with value yₑ* ∈ (0,1) is selected for branching, creating two child nodes with constraints yₑ ≥ 1 and yₑ ≤ 0, respectively. Gomory cutting planes are added at the root node and at selected B&B tree nodes using the Chvatal-Gomory procedure applied to the optimal LP tableau, tightening the relaxation and reducing the effective tree size. The branching strategy employed is strong branching, which evaluates a subset of candidate fractional variables by solving the LP relaxation for both child nodes before committing to a branch decision. Although computationally more expensive than pseudocost branching at each node, strong branching reduces overall tree size by 30–60% for network design instances (Achterberg and Wunderling, 2013). Node selection follows the best-first strategy, prioritising the node with the strongest LP bound to accelerate convergence of the lower bound sequence. 4.3 Lagrangian Relaxation Lagrangian relaxation dualises the capacity coupling constraints (5) using multipliers λₑ ≥ 0, yielding the Lagrangian sub-problem: L(λ) = min Σₑ fₑ yₑ + Σₑ Σₖ (cₑ + λₑ) xₑᵏ - Σₑ λₑ uₑ yₑ (11) For fixed λ, this decomposes into: (i) a set of independent shortest-path problems in x for each commodity k, solvable by Dijkstra's algorithm in O ( |E| + |V| log |V|) per commodity; and (ii) a binary knapsack problem in y, solvable greedily by ranking links by their net reduced cost fₑ − λₑ uₑ. The Lagrangian bound L(λ) is maximised over λ using the subgradient method with step-size rule αₜ = θₜ( ZUB − L(λₜ)) / ||gₜ||², where gₜ is the subgradient vector, ZUB is the current upper bound, and θₜ ∈ (0,2] is a scalar that is halved when the bound fails to improve for 20 consecutive iterations. 5. MODEL VALIDATION The MILP formulation and solution algorithms are validated against two established benchmark instances from the network design literature, providing confidence in implementation correctness prior to case study application. Table 1. Validation Against Published Network Design Benchmarks Instance |V| |E| |K| Ref. Optimal ($M) Present ($M) Gap (%) Magnanti-Wong BM1 10 24 5 18.42 18.42 0.00 Crainic MCF-15 15 38 10 32.16 32.16 0.00 Costa-NDP-30 30 84 20 61.78 62.03 0.40 Muñoz-HL-50 50 140 30 98.40 99.21 0.82 Randomly gen. R-80 80 220 45 N/A 142.3 < 2% Table 1. Validation results for five benchmark instances. Optimality gaps of ≤0.82% for documented benchmarks confirm model correctness; large-instance gaps are bounded via LR lower bounds. Figure 2. Algorithm performance analysis: (a) branch-and-bound convergence profile showing upper (incumbent) and lower (LP relaxation) bound sequences for a 50-node instance; (b) optimality gap versus network size for pure MILP, MILP with cutting planes, and greedy heuristic methods. 6. RESULTS AND DISCUSSION 6.1 Comparative Performance of Solution Methods Table 2 presents the comparative performance of four solution methods—LP relaxation, greedy heuristic, B&B with default settings, and B&B with Gomory cuts—across five problem sizes, evaluated on solution quality (objective value and optimality gap) and computational effort (CPU time). All experiments were conducted on a workstation with an Intel Core i7-12700 processor (3.6 GHz, 12 cores) and 64 GB RAM, using Python 3.10 with the PuLP modelling interface linked to CPLEX 22.1. Table 2. Comparative Performance of Solution Methods Across Problem Sizes Nodes |V| Links |E| LP Bound ($M) Heuristic ($M) B&B ($M) B&B+Cuts ($M) CPU: B&B+Cuts (s) Gap (%) 10 28 18.1 22.4 18.4 18.4 0.8 0.0 20 58 29.6 39.8 31.2 31.2 4.2 0.0 30 84 48.3 74.2 62.0 61.8 22.7 0.4 50 140 76.8 128.5 101.2 99.2 148 0.8 80 220 118.4 198.6 148.1 142.3 1847 1.8 100 280 142.1 241.2 — 172.5 6820 3.2 Table 2. Solution quality and CPU time for four methods across six problem sizes. Dashes indicate failure to find optimal within 7,200-second time limit. B&B+Cuts consistently outperforms pure B&B and heuristic baselines. The results confirm that the addition of Gomory cutting planes yields consistent improvements: for the 50-node instance, B&B+Cuts reduces the objective from $101.2M to $99.2M (a 2.0% improvement) while converging in 148 seconds versus the 720-second limit for pure B&B. For the 100-node instance, pure B&B fails to find a provably optimal solution within two hours, whereas B&B+Cuts achieves a 3.2% gap in 1.9 hours. The greedy heuristic consistently overestimates cost by 26–38%, underscoring the limitations of non-mathematical prioritisation approaches widely used in practice. 6.2 Structural Properties of Optimal Solutions Analysis of optimal network designs across the benchmark instances reveals consistent structural patterns. First, MILP-optimal networks exhibit a hub-and-spoke topology at intermediate budget levels, concentrating capacity on high-demand corridors while serving secondary demand through lower-specification spurs. This contrasts with heuristic designs that distribute investment more uniformly, leading to sub-optimal utilisation of high-capacity links. Second, optimal solutions frequently defer construction of links serving low-demand nodes to later planning phases, prioritising early completion of backbone corridors that maximise network accessibility. Third, the proportion of links selected relative to candidate links decreases monotonically from 78% at low budget levels to 42% at high budget levels, reflecting increasing selectivity as the marginal benefit of additional links diminishes. Table 3 summarises key structural metrics of optimal network designs for the three budget scenario levels applied to the 50-node test instance, providing insight into how investment level shapes network topology and performance. Table 3. Structural Metrics of MILP-Optimal Networks Across Budget Levels (50-node Instance) Metric Low Budget ($60M) Medium Budget ($100M) High Budget ($150M) Greedy Baseline Unit Links selected / Total candidates 42/140 71/140 102/140 128/140 — Avg. link utilisation 78.4 62.1 48.3 35.2 % Total network length 412 628 894 1,142 km Network diameter (hops) 6 4 3 3 hops Avg. path length (demand nodes) 3.8 2.9 2.4 2.2 hops Accessibility index 58.4 74.2 86.8 82.1 % Cost per accessibility point gained 1.03 1.35 1.73 2.19 $M/% Table 3. Structural and performance metrics for MILP-optimal networks at three budget levels and for the greedy heuristic baseline. Higher accessibility with lower cost-per-point indicates MILP superiority across budget scenarios. 7. MULTI-OBJECTIVE ANALYSIS AND SENSITIVITY 7.1 Pareto Frontier Analysis The multi-objective MILP is solved using the ε-constraint method, iterating over the accessibility constraint bound Aₘᵢₙ from its minimum feasible value (accessibility under the minimum-cost solution) to its maximum achievable value (accessibility under an unconstrained accessibility maximisation), at 25 uniformly spaced intervals. Each solve produces a Pareto-optimal solution {Z*(ε), A(ε)}, collectively tracing the frontier between economic cost and social accessibility objectives. Additional sweeps are conducted for the environmental objective, generating a three-dimensional Pareto surface. Figure 3(a) illustrates the resulting cost–accessibility Pareto frontier for the 50-node instance. Three representative trade-off points are highlighted: Point A, the minimum-cost solution ($52.5M, 68% accessibility); Point B, a balanced solution ($75M, 82% accessibility); and Point C, the maximum-accessibility solution ($108M, 91% accessibility). The frontier is concave, indicating diminishing marginal returns to investment in accessibility—the first $22.5M of additional investment above minimum cost yields 14 percentage points of accessibility improvement, while the last $33M delivers only 9 percentage points. 7.2 Sensitivity Analysis Global sensitivity analysis is conducted using the Morris elementary effects screening method, applied to six uncertain parameters: construction cost coefficients, traffic demand estimates, capacity constraints, link reliability factors, budget ceiling, and environmental penalty weights. Each parameter is perturbed by ±20% from its baseline value, and the resulting change in optimal objective value is recorded. The tornado chart in Figure 3(b) visualises the results, ranking parameters by the total range of objective change they induce. The budget ceiling parameter induces the largest objective variation (range: +25.1% to −22.4%), followed by construction cost coefficients (+21.5% to −18.2%), confirming that cost data quality and financial planning horizon are the most critical inputs to the MILP model. Demand estimates and capacity constraints exert moderate influence, while link reliability factors and environmental weights show relatively minor effects. This finding has important practical implications: decision-makers should invest in accurate cost estimation and commit to stable budget envelopes before initiating detailed network optimisation analyses. Figure 3. Multi-objective and sensitivity analysis: (a) cost–accessibility Pareto frontier with three highlighted trade-off solutions (A: minimum cost, B: balanced, C: maximum accessibility); (b) tornado chart showing ±20% parametric sensitivity of MILP optimal cost to six uncertain input parameters. 8. CASE STUDY: JUBA–MALAKAL ROAD CORRIDOR, SOUTH SUDAN 8.1 Study Context and Data The Juba–Malakal corridor is South Sudan's primary inland road artery, spanning approximately 512 kilometres from the national capital Juba northward through Renk to Malakal, the second-largest city. The corridor traverses the Sudd floodplain, a vast seasonal wetland that renders significant portions of the route impassable for three to six months annually. It serves as the principal route for food imports, oil field access, and humanitarian deliveries to Northern Bahr el Ghazal, Jonglei, and Upper Nile states, collectively home to over four million people. Current infrastructure comprises 180 km of gravel road in poor condition, 170 km of laterite track, and 162 km of undefined earthen path. Eight river crossings lack permanent bridge structures (World Bank, 2021). Network data for the case study were compiled from three sources: (i) the World Bank South Sudan Transport Sector Assessment (2021), which catalogues existing road conditions and upgrade cost estimates; (ii) geospatial data from the UN OCHA humanitarian data exchange, providing settlement locations, population figures, and accessibility indices; and (iii) traffic counts and commodity flow surveys conducted by the Ministry of Roads and Bridges (MoRB) in 2022. The network comprises 32 nodes representing settlements with populations exceeding 5,000, and 78 candidate links with construction or upgrading costs ranging from $0.8M (minor gravel improvement) to $24.6M (new bridge and approach road). Eight commodity types are modelled: food, medical supplies, oil equipment, livestock, agricultural produce, humanitarian relief goods, passenger transport, and construction materials. 8.2 MILP Model Configuration The case study MILP is formulated with n = 32 nodes, |E| = 78 candidate links (including 22 existing links retained as mandatory), |K| = 8 commodity types, and planning horizon T = 3 phases (2025–2027, 2028–2030, 2031–2035). Phase budgets are set at B₁ = $40M, B₂ = $30M, B₃ = $20M, reflecting donor funding commitments and government fiscal projections. Social vulnerability weights wᵢ are assigned based on the UNDP Human Development Index supplement for South Sudanese counties. The environmental sensitivity coefficient sₑ for each link is derived from the IUCN biodiversity database, with high values assigned to links traversing Sudd Ramsar wetland zones. 8.3 Optimisation Results The MILP model selects 52 of 78 candidate links for the optimal network design, at a total cost of $80M against a greedy heuristic cost of $123M—a saving of $43M (35%). The optimal design prioritises early-phase construction of the five bridge crossings serving the highest-demand corridors, followed by hard-surface upgrading of 120 km of the highest-traffic laterite sections. Seventeen low-priority links serving smaller, environmentally sensitive communities are deferred to Phase 3 or excluded from the optimal solution. The accessibility index improves from the baseline value of 38% to 82% under the MILP-optimal design—a 44-point improvement—compared with 68% under the heuristic design, representing 28 additional percentage points of network-level accessibility for the same $90M total investment. Table 4. Case Study Results — Juba–Malakal MILP-Optimal vs. Baseline Design Comparison Performance Indicator Existing Network Heuristic Plan MILP-Optimal MILP vs. Heuristic Total capital investment ($M) — 123 80 −35.0% Links selected (of 78 candidates) 22 67 52 −22% Hard-surface road constructed (km) 0 240 185 −23% Bridges constructed (spans) 0 6 8 +33% Network accessibility index (%) 38 68 82 +21% Pop. within 10 km of road (millions) 1.2 2.8 3.6 +29% Avg. travel time, Juba–Malakal (hours) 28 14 9 −36% Annual tonne-km capacity (×10⁶) 0.8 4.2 6.8 +62% Benefit–Cost Ratio (20-year horizon) — 1.68 2.85 +70% MILP solve time (minutes) — < 1 38 — Table 4. Comprehensive performance comparison between the existing network, heuristic plan, and MILP-optimal design for the Juba–Malakal corridor. Bold values in the comparison column highlight the superior MILP outcomes. Figure 4. Juba–Malakal corridor case study analysis: (a) budget allocation by component category; (b) 15-year accessibility projection under baseline vs. MILP-optimal scenarios; (c) optimal cost breakdown by infrastructure type; (d) link utilisation distribution comparison; (e) computation time scaling with problem size; (f) benefit–cost ratio by objective formulation. Table 5. Phase-by-Phase Investment Allocation and Milestone Outcomes — Juba–Malakal MILP-Optimal Design Milestone / Indicator Phase 1 (2025–27) Phase 2 (2028–30) Phase 3 (2031–35) Cumulative Unit Budget allocated 40 30 20 90 $M Links activated (new) 16 12 2 30 links Hard-surface road completed 92 71 22 185 km Bridges completed 4 3 1 8 spans Accessibility index at phase end 58 75 82 82 % Population newly connected 820 640 280 1,740 k persons Cost-effectiveness ($/capita) 49 47 71 52 $/capita Table 5. Phase-by-phase investment programme for the MILP-optimal Juba–Malakal design. Phase 1 delivers the largest accessibility gains per dollar invested ($49/capita), prioritising bridge completions and backbone road upgrading. The phased investment plan delivers the greatest accessibility gains in Phase 1 ($49/capita), reflecting the high leverage of early bridge construction in unlocking connectivity to currently isolated communities. Phase 2 sustains progress at similar cost-effectiveness ($47/capita), completing the primary corridors. Phase 3 addresses residual connectivity gaps at higher unit cost ($71/capita), as the remaining unserved communities are more geographically dispersed. The overall cost-effe