Package routing in transportation networks with fixed vehicle schedules

We consider a special case of the general problem involving the routing of packages among vehicles 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. Since this problem is NP-complete, we explore approximation algorithms for its solution. In particular, we cast this problem as a multicommodity flow problem with a mixed integer/linear program formulation. We then apply combinatorial optimization techniques based on solving the relaxed linear programming formulation of the problem to obtain a solution with provable constraint violation bounds 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.