Approximation Algorithms for Capacitated Location Routing

Tobias Harks (), Felix G König () and Jannik Matuschke ()
Additional contact information
Tobias Harks: School of Business and Economics, Maastricht University, 6200 MD, The Netherlands
Felix G König: TomTom International BV, 12435 Berlin, Germany
Jannik Matuschke: Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany

Transportation Science, 2013, vol. 47, issue 1, 3-22

Abstract: An approximation algorithm for an optimization problem runs in polynomial time for all instances and is guaranteed to deliver solutions with bounded optimality gap. We derive such algorithms for different variants of capacitated location routing , an important generalization of vehicle routing where the cost of opening the depots from which vehicles operate is taken into account. Our results originate from combining algorithms and lower bounds for different relaxations of the original problem; along with location routing we also obtain approximation algorithms for multidepot capacitated vehicle routing by this framework. Moreover, we extend our results to further generalizations of both problems, including a prize-collecting variant, a group version, and a variant where cross-docking is allowed. We finally present a computational study of our approximation algorithm for capacitated location routing on benchmark instances and large-scale randomly generated instances. Our study reveals that the quality of the computed solutions is much closer to optimality than the provable approximation factor.

Keywords: capacitated location routing; vehicle routing; approximation algorithms; cross-docking (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0423 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:47:y:2013:i:1:p:3-22

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().