Tech Report CS-92-26

Package Routing in Transportation Networks with Fixed Vehicle Schedules: Formulation, Complexity Results and Approximation Algorithms

Lloyd Greenwald and Thomas Dean

June 1992


We consider a special case of a general problem involving the deployment of vehicles to transport packages in transportation networks. In this special case, the schedules of the vehicles are fixed and packages are routed by transferring them between vehicles as these vehicles make stops according to their fixed schedules. We show that this problem is hard and explore approximation algorithms for its solution. In particular, we cast this problem as a multicommodity flow problem with a mixed integerlinear program formulation. We then apply combinatorial optimization techniques based on solving the relaxed linear programming formulation of the problem to obtain provable feasibility and expected performance guarantees, where performance is measured in terms of the sum of the time in transit over all packages. We investigate the sensitivity of the performance guarantees to certain scaling factors and other limitations of this technique.

(complete text in pdf or gzipped postscript)