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

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

Ning Yang (Parsons Corporation, USA), Shiaaulir Wang (Clarksville, USA) and Paul Schonfeld (University of Maryland, USA)
DOI: 10.4018/978-1-4666-9619-8.ch046
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

A Parallel Genetic Algorithm (PGA) is used for a simulation-based optimization of waterway project schedules. This PGA is designed to distribute a Genetic Algorithm application over multiple processors in order to speed up the solution search procedure for a very large combinational problem. The proposed PGA is based on a global parallel model, which is also called a master-slave model. A Message-Passing Interface (MPI) is used in developing the parallel computing program. A case study is presented, whose results show how the adaption of a simulation-based optimization algorithm to parallel computing can greatly reduce computation time. Additional techniques which are found to further improve the PGA performance include: (1) choosing an appropriate task distribution method, (2) distributing simulation replications instead of different solutions, (3) avoiding the simulation of duplicate solutions, (4) avoiding running multiple simulations simultaneously in shared-memory processors, and (5) avoiding using multiple processors which belong to different clusters (physical sub-networks).
Chapter Preview
Top

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.

Complete Chapter List

Search this Book:
Reset