198837
20181007231310.0
10.5075/epfl-thesis-6163
doi
urn:nbn:ch:bel-epfl-thesis6163-8
urn
10147850
nebis
THESIS_LIB
eng
6163
Approximation algorithms for regret minimization in vehicle routing problems
Lausanne
2014
EPFL
2014
Theses
Prof. M. Troyanov (prÃ©sident) ; Prof. F. Eisenbrand (directeur) ; Prof. L. SanitÃ , Prof. M.G. Speranza, Prof. O.N.A. Svensson (rapporteurs)
In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such as logistics, robotics, or distribution systems. For the first problem class, the goal is to visit as many locations in a network as possible subject to timing or cost constraints. For the second problem class, a given set of locations is to be visited using a minimum-cost set of routes under some constraints. Due to the relevance of both problem classes for public transportation, a secondary objective must be taken into account beyond a low operation cost: namely, it is crucial to design routes that optimize customer satisfaction in order to encourage customers to use the service. Our measure of choice is the regret of a customer, that is the time comparison of the chosen route with the shortest path to a destination. From the first problem class, we investigate variants and extensions of the Orienteering problem that asks to find a short walk maximizing the profit obtained from visiting distinct locations. We give approximation algorithms for variants in which the walk has to respect constraints on the regret of the visited vertices. Additionally, we describe a framework to extend approximation algorithms for Orienteering problems to consider also a second budget constraint, namely node demands, that have to be satisfied in order to collect the profit. We obtain polynomial time approximation schemes for the Capacitated Orienteering problem on trees and Euclidean metrics. Furthermore, we study variants of the School Bus problem (SBP). In SBP, a given set of locations is to be connected to a destination node with both low operation cost and a low maximum regret. We note that the Orienteering problem can be seen as the pricing problem for SBP and it often appears as subroutine in algorithms for SBP. For tree-shaped networks, we describe algorithms with a small constant approximation factor and complement them by showing hardness of approximation results. We give an overview of the known results in arbitrary networks and we prove that a general variant cannot be approximated unless P = NP. Finally, we describe an integer programming approach to solve School Bus problems in practice and present an improved bus schedule for a private school in the lake Geneva region.
Combinatorial Optimization
Approximation algorithm
Vehicle routing problem
Orienteering
Set-cover integer linear programming formulation
Bock, Adrian Aloysius
199692
243823
Eisenbrand, Friedrich
dir.
183121
240331
n/a
977737
n/a
http://infoscience.epfl.ch/record/198837/files/EPFL_TH6163.pdf
DISOPT
252111
U11879
oai:infoscience.tind.io:198837
SB
DOI
thesis
thesis-bn2018
DOI2
108898
108898
108898
108898
SB
MATHAA
EDMA
DISOPT
2014-5-28
2014
6163/THESES
EPFL
PUBLISHED
THESIS