Jana G. Beattie
Carol L. Spelman

Meeting Name

1st Annual UMR Undergraduate Research Symposium (1991: Apr., Rolla, MO)

Abstract

This paper presents a parallel version of the Sweep Algorithm, a heuristic solution to the smgle-termma] vehicle routing problem The Sweep Algorithm uses a duster-first route-second approach in finding a near-optimal set of routes. The clusters of delivery points are formed by using the terminal as the center and moving around it m a sweeping fashion After a duster is defined, the route is found with a traveling salesperson algorithm.

The parallel version begins the sweep at different angles and performs both forward and backward sweeps. Each node handles a sweep and returns information concerning total distance traveled to the host. The host then derides which node has the best routes and requests the specific information.

The traveling salesperson algorithm is the nearest neighbor method. This starts the route at the point in the duster nearest the terminal and proceeds by visiting the nearest unvisited point. Since this procedure is called many times in the course of finding all the routes, the quick but good results that this method yields were attractive.

Also discussed are other parallel implementations of this problem and ideas for further research.

Research Category

Improving Technology Through Computer Modeling

Document Type

Presentation

Award

3rd Place

Presentation Date

April 1991

Comments

Title "Parallel Implementation of the Sweep Algorithm for Vehicle Routing" in the Table of Contents

Download

Share

COinS