Parallel genetic algorithms for selection and scheduling of interdependent transportation projects

The selection and scheduling of interdependent transportation projects remain challenging tasks in theoretical research as well as in real world applications. The major difficulties in solving this problem include the complex interdependence among projects, dynamic network flows resulting from network changes and computational burdens. To deal with such difficulties, an effort is made here to develop parallel genetic algorithms (PGAs) and apply them to the project selection and scheduling problem.; Since deterministic models and probabilistic queuing models may not be realistic enough to capture the interactions within a complex and congested transportation system, the study takes advantage of simulation methods to evaluate the system cost for alternative project implementations. A microscopic simulation model for an inland waterway model, WATSIM, was developed for analyzing on the performance of the developed PGA approach.; When incorporating realistic budget constraints, the selection and scheduling of transportation projects can be expressed as a combinatorial optimization problem of finding the project implementation sequence that minimizes the total system cost over the analysis period. A PGA algorithm based on an island model has been developed to optimize sequences for the difficult combinatorial optimization problem. For the developed PGA algorithm, a specific method is proposed to partition the whole solution space based on the rankings of projects. When the project selection and scheduling problem is a stochastic problem, additional simulation replications are applied to each subpopulation to select statistically “good” emigrants for migration to other subpopulations.; The PGA approach has been applied to solve the project selection and scheduling problem on both an urban highway network and an inland waterway network. On the urban highway network, a traffic assignment model has been used to generate network flows for experiments. For the inland waterway network, the newly developed WATSIM model is applied to generate tow flows on waterways and evaluate the different combinations of projects. Other heuristic approaches including the “Swap” algorithm, Simulated Annealing and a conventional GA are also tested for comparisons. Experimental analyses show that the proposed PGA approach can generate better solutions than the other heuristic approaches tested. The analyses of results show that the PGA approach is promising for solving stochastic problems.