Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14468
For citation please use:
Main Title: Approximation Algorithms for Capacitated Location Routing
Author(s): Harks, Tobias
König, Felix G.
Matuschke, Jannik
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15695
http://dx.doi.org/10.14279/depositonce-14468
License: http://rightsstatements.org/vocab/InC/1.0/
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, and besides location routing we also obtain approximation algorithms for multi-depot 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.
Subject(s): approximation algorithm
location routing
vehicle routing
facility location
cross-docking
logistics
Issue Date: 2010
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2010, 10
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-010-2010.pdf
Format: Adobe PDF | Size: 229.4 kB
DownloadShow Preview
Thumbnail
Report-010-2010.ps
Format: Postscript | Size: 443.22 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.