Optimal Traffic Relief Road Design Using Bilevel Programming and Greedy–Seeded Simulated Annealing: A Case Study of Kinshasa

The city of Kinshasa faces severe traffic congestion, requiring strategic enhancements to its transport infrastructure capacity. Although a comprehensive transport master plan has been proposed by the Japanese International Cooperation Agency (JICA) report its implementation requires substantial financial investment, which presents a significant challenge for the resource-constrained environment of the Democratic Republic of Congo. This research proposes an indicative optimisation-based network augmentation strategy that accounts for traveller equilibrium behaviour, the primary origin–destination demand patterns, and the underlying network structure. The study formulates the problem as a bilevel Transport Network Design Problem (TNDP) under a construction length budget constraint. Greedy-Simulated Annealing and Greedy-Tabu Search are proposed as the recommended computational search approaches, as they achieved the highest travel time reductions in the experimental study while also demonstrating stable and repeatable solution performance compared with other classical metaheuristic methods commonly used in TNDP research. Greedy Simulated Annealing and Greedy-Tabu Search are proposed as the recommended computational search approaches, as they achieved the highest travel time reductions in the experimental study while also demonstrating stable and repeatable solution performance compared with other classical metaheuristic methods commonly used in TNDP research. The computational experiments indicate a 30% reduction in total travel time, accompanied by a substantial decrease in highly congested links from 52.94% in the baseline network to 3.45% in the optimised design and nearly threefold improvement in edge betweenness centrality for a 100 Km constrained budget. The study further provides recommended new link constructions, together with alternative network redesign solutions that achieve comparable performance improvements.