Gao, Xiaojie (2008) On a capacitated multivehicle routing problem. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-10292007-212511
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 a VRP, we are given a number of customers with known delivery requirements and locations (assumed to be vertices in a network). A fleet of vehicles with limited capacity is available. The objective is to design routes and customer assignments to minimize the total time or distance traveled to serve the demands. Because of its practical significance, this problem has been widely studied. In this thesis, we present a version of the VRP motivated by mobile sensor networks which we call the Capacitated Multivehicle Routing Problem (CMVRP). In our framework, there are multiple geographically disperse vehicles each equipped with a limited energy supply. The vehicle consumes energy as it moves around and it also consumes energy while serving jobs. This situation models a network of mobile sensors where locomotion and computation all drain the limited capacity battery onboard. 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. Furthermore, we study the on-line problem where job demands arrive sequentially and present a distributed algorithm that serves all jobs using only a constant factor more energy than the off-line solution.
|Item Type:||Thesis (Dissertation (Ph.D.))|
|Subject Keywords:||capacitated multivehicle routing problem; diffusing computation; linear programming; load balancing; resource allocation; transportation problem|
|Degree Grantor:||California Institute of Technology|
|Division:||Engineering and Applied Science|
|Major Option:||Computer Science|
|Thesis Availability:||Public (worldwide access)|
|Defense Date:||3 August 2007|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||05 Dec 2007|
|Last Modified:||16 May 2016 18:51|
- Final Version
See Usage Policy.
Repository Staff Only: item control page