Simulation-Based Scheduling of Waterway Projects Using a Parallel Genetic Algorithm

Introduction

Providing an efficient and economic way to transport bulk commodities (e.g., petroleum and coal), the inland waterways of the United States move about 630 million tons of cargo valued at over $73 billion annually. Along 12,000 miles of navigable waterways operated by the U.S. Army Corps of Engineers (USACE), over 200 lock sites allow towboats to “stair-step” their way through stretches of water of different levels. Locks with insufficient capacity can delay towboats for hours or even days. Therefore, the maintenance and expansion of lock capacities can drastically improve waterways’ ability to move goods more quickly and more cheaply.

Given a number of proposed waterway capacity expansion or maintenance projects, decision makers have to evaluate, select and schedule these projects over a multi-year period to make effective use of limited budgets. This becomes a large and complex combinational optimization problem (Martinelli & Schonfeld, 1995) partly because the projects are interrelated, i.e. their effects (such as queuing delays) depend on which other projects are built and when. Thus, capacity expansion at one location may shift the bottlenecks elsewhere and may also generate new traffic. To solve the problem, a simulation-based optimization model (SIMOPT) has been developed at the University of Maryland (Wang & Schonfeld, 2005). SIMOPT evaluates waterway network performance through a microscopic simulation model and employs a genetic algorithm to optimize the project selection and scheduling.

Although the use of heuristic optimization algorithms can significantly reduce the temporal complexity of the solution search process, the latter remains time-consuming when objective functions are evaluated through computer simulation. For speeding up the optimization process, a promising approach is to distribute the computations of the objective functions over multiple processors, computers, or workstation networks. This eliminates the need to re-program the optimization model in parallel computing languages.

This paper seeks to demonstrate that adapting the genetic algorithm for parallel computing is a superior way for accelerating the simulation-based optimization process. In addition, we present several techniques and design characteristics that can further improve the effectiveness of the parallel genetic algorithm (PGA) especially when is applied in the optimization via simulation.

The paper is organized as follows. The “Literature Review” section surveys recent studies on simulation-based optimization and parallel computing. The waterway improvement projects scheduling problem is presented in detail in the “Problem Statement” section, followed by a description of the proposed PGA in the “Parallel Genetic Algorithm” Section. The “Numerical Experiments” section demonstrates an application of the methodology in a numerical example. Conclusions and extensions are presented in the last section.