A parallel implementation of the TSSP+1 decomposition for the capacity-constrained vehicle routing problem

A parallel implementation of the TSSP+1 decomposition for the capacity-constrained vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor1997126
Country: United Kingdom
Volume: 23
Issue: 7
Start Page Number: 723
End Page Number: 732
Publication Date: Jul 1996
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

Vehicle rotuing problems (VRPs) are known to be computationally intractable. The amount of time required to solve a VRP increases significantly given a modest increase in problem size. Only small VRPs may be solved exactly using existing mathematical programming techniques on single processor computers. In recent years, multiple processor computers have emerged as powerful tools for solving computationally difficult problems. Problems are divided into several smaller parts or modules that can be solved simultaneously (or in parallel) to decrease computation time. The degree of speedup depends on the particular parallelization strategy as well as the system architecture. This paper presents a parallel optimization technique for solving the basic, capacity-constrained VRP. It includes: (1) a description of a decomposition algorithm for the VRP; (2) a description of the serial algorithm and the strategy used to implement the decomposition in parallel; (3) validation of the effectiveness of the parallel implementation; and (4) performance analysis comparing the parallel and serial implementations. The parallel appraoch to the VRP significantly reduces computation time and maintains solution quality.

Reviews

Required fields are marked *. Your email address will not be published.