Prioritizing Interrelated Road Projects Using Metaheuristics

Abstract

Projects are considered interrelated when their benefits or costs depend on which other projects are implemented. The timing of such projects may also complicate their analysis. Selection and scheduling of interrelated projects is a challenging optimization problem that has many applications in various fields, including economics, operations research, business, management, and transportation. The goal is to determine which projects should be selected and when they should be funded in order to minimize the total system cost over a planning horizon. Finding the optimal solution for such problems often requires extensive evaluation of possible solutions because of the complex nature and noisy surface of their solution space. This paper applies three metaheuristic algorithms including a genetic algorithm (GA), simulated annealing (SA), and Tabu search (TS) in seeking efficient and consistent solutions to the selection and scheduling problem. These approaches are applied to a special case of link capacity expansion projects to showcase their functionality and compare their performance. The paper’s main contributions are to (1) compare three metaheuristics for this problem in terms of solution quality, computation time, and consistency; (2) consider explicitly the supplier costs as well as user costs in the formulated objective function; and (3) enhance some simplifying assumptions from previous studies by recognizing that candidate projects may not remain economically justifiable throughout the analyzed period. It is found that a GA yields the most consistent solution with the least total cost while SA and TS approaches excel in terms of computation time.