A Caltech Library Service

On A Capacitated Multivehicle Routing Problem


Gao, Xiaojie (2008) On A Capacitated Multivehicle Routing Problem. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/3Y9X-EW47.


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)
Research Advisor(s):
  • Schulman, Leonard J.
Thesis Committee:
  • Unknown, Unknown
Defense Date:3 August 2007
Record Number:CaltechETD:etd-10292007-212511
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4307
Deposited By: Imported from ETD-db
Deposited On:05 Dec 2007
Last Modified:05 Jan 2021 22:51

Thesis Files

PDF (thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page