Paper Info
Title
On a capacitated multivehicle routing problem
Abstract
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.
Year
DOI
Venue
2008
10.1145/1400751.1400776
PODC
Keywords
Field
DocType
constant factor,vehicle routing problem,off-line case,constant factor approximation algorithm,off-line solution,capacitated multivehicle routing problem,high computational complexity,on-line problem,high industrial relevance,capacitated multivehicle,discrete optimization problem,linear programming,resource allocation,linear program,transportation problem,computational complexity,discrete optimization
Approximation algorithm,Vehicle routing problem,Mathematical optimization,Computer science,Destination-Sequenced Distance Vector routing,Transportation theory,Distributed algorithm,Linear programming,Cutting stock problem,Distributed computing,Computational complexity theory
Conference
Citations 
PageRank 
References 
0
0.34
14
Authors
2
Name
Order
Citations
PageRank
Xiaojie Gao1151.76
Leonard J. Schulman21328136.88