Parallel implementation of branch and bound algorithm for solving vehicle routing problem on NOWs

K.K. Lau; M.J. Kumar; N.R. Achuthan

doi:10.1109/ISPAN.1997.645104

Parallel Architectures, Algorithms, and Networks, International Symposium on

Parallel implementation of branch and bound algorithm for solving vehicle routing problem on NOWs

Year: 1997, Pages: 247

DOI Bookmark: 10.1109/ISPAN.1997.645104

Authors

K.K. Lau, Dept. of Comput. Sci., Curtin Univ. of Technol., Perth, WA, Australia
M.J. Kumar, Dept. of Comput. Sci., Curtin Univ. of Technol., Perth, WA, Australia
N.R. Achuthan, Dept. of Comput. Sci., Curtin Univ. of Technol., Perth, WA, Australia

Abstract

This paper proposes a parallel branch and bound algorithm designed for solving the Vehicle Routing Problem (VRP) on NOWs (Networks of Workstations). Our objective is to minimize the execution time by considering parallel implementation to find an exact solution to the VRP in real time. Our experimental studies reveal that the proposed parallel branch and bound algorithm can achieve super-linear speedup for large problem sizes. Dynamic load balancing techniques for solving the VRP on NOWs are also discussed.

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!