Solving the Transport Infrastructure Investment Projects Selection and Scheduling as a Multiple Knapsack Problem Using Genetic Algorithms

The development of transport infrastructure is a key element of economic growth, social connectivity, and sustainable development. Many countries have historically underinvested in transport infrastructure, necessitating more efficient strategic planning in transport infrastructure investment projects implementation. This article addresses the selecting and scheduling of transport infrastructure projects, specifically within the context of drawing available resources from pre-allocated funds within a multi-annual budget investment program. The current decision-making process is largely based on expert judgment, lacking quantitative decision support methods. The authors propose a genetic algorithm as a decision-support tool that frames the problem as an NP-hard 0-1 multiple knapsack problem. The proposed genetic algorithm is unique for its matrix-encoded chromosomes, specially designed genetic operators, and a customized repair operator, which is implemented to address the large number of invalid chromosomes generated during the GA computation. The goal is to maximize the impact of allocated funds over a seven-year programming period, while respecting constraints specified by the funding authorities. In computational experiments, proposed GA is compared to an exact solution and is proved to be efficient in terms of quality of obtained solutions and computational time, highlighting its potential for enhancing strategic decision-making in transport infrastructure development.