On A Capacitated Multivehicle Routing Problem

Citation

Gao, Xiaojie (2008) On A Capacitated Multivehicle Routing Problem. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/3Y9X-EW47. https://resolver.caltech.edu/CaltechETD:etd-10292007-212511

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 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.

Thesis Files