Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2008 | public
Book Section - Chapter

On a capacitated multivehicle routing problem


The Vehicle Routing Problem (VRP) is a discrete optimization problem with high industrial relevance and high computational complexity. The problem has been extensively studied since it was introduced by Dantzig and Ramser. In this paper, we present a version of the VRP motivated by mobile sensor networks which we call the Capacitated Multivehicle Routing Problem (CMVRP). Our objective is to determine the minimum amount of energy required to serve all jobs, which takes into account both the service requirement and the travel overhead. We present a constant factor approximation algorithm for the off-line case and a distributed algorithm for the on-line problem that uses only a constant factor more energy than the off-line solution.

Additional Information

© 2008 ACM. Supported in part by NSF Award CCF-0515342.

Additional details

August 19, 2023
October 23, 2023