Parallel Tabu Search and the Multiobjective Vehicle Routing Problem with Time Windows

Author

Beham, Andreas

Author_Institution

Inst. for Formal Models & Verification, Johannes Kepler Univ., Linz

fYear

2007

fDate

26-30 March 2007

Firstpage

1

Lastpage

8

Abstract

In this paper the author presents three approaches to parallel tabu search, applied to several instances of the capacitated vehicle routing problem with time windows (CVRPTW). Attention in this work was given to keep the parallel implementations simple. The parallel algorithms are of two kinds: two of them are parallel with respect to functional decomposition and one approach is a collaborative multisearch TS. The implementation builds upon a framework called distributed meta-heuristics or DEME for short. Tests were performed on an SGI Origin 3800 supercomputer at the Johannes Kepler University of Linz, Austria.

Keywords

optimisation; parallel algorithms; search problems; transportation; vehicles; capacitated vehicle routing problem; collaborative multisearch; functional decomposition; multiobjective optimization; parallel algorithm; tabu search; time window; Capacity planning; Collaborative work; Parallel algorithms; Performance evaluation; Routing; Runtime; Scattering; Supercomputers; Testing; Vehicles; multiobjective; parallel; tabu search; vehicle routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International

Conference_Location

Long Beach, CA

Print_ISBN

1-4244-0910-1

Electronic_ISBN

1-4244-0910-1

Type

conf

DOI

10.1109/IPDPS.2007.370431

Filename

4228159