Title :
Parallel implementation of branch and bound algorithm for solving vehicle routing problem on NOWs
Author :
Lau, K.K. ; Kumar, M.J. ; Achuthan, N.R.
Author_Institution :
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
Keywords :
operations research; optimisation; parallel algorithms; transportation; tree searching; Networks of Workstations; VRP; branch and bound algorithm; load balancing; operational research; optimisation; parallel branch and bound; real time; super-linear speedup; vehicle routing problem; Computer science; Load management; Logistics; Mathematics; Polynomials; Routing; Search methods; Statistics; Vehicle dynamics; Workstations;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1997. (I-SPAN '97) Proceedings., Third International Symposium on
Conference_Location :
Taipei
Print_ISBN :
0-8186-8259-6
DOI :
10.1109/ISPAN.1997.645104
