Premium
Package routing in transportation networks with fixed vehicle schedules
Author(s) -
Greenwald Lloyd,
Dean Thomas
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199601)27:1<81::aid-net7>3.0.co;2-a
Subject(s) - mathematical optimization , routing (electronic design automation) , flow network , linear programming , computer science , vehicle routing problem , integer programming , multi commodity flow problem , transportation theory , constraint (computer aided design) , sensitivity (control systems) , fixed cost , mathematics , computer network , engineering , geometry , electronic engineering , accounting , business
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. © 1996 John Wiley & Sons, Inc.