000198837 001__ 198837
000198837 005__ 20181205220041.0
000198837 0247_ $$2doi$$a10.5075/epfl-thesis-6163
000198837 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis6163-8
000198837 02471 $$2nebis$$a10147850
000198837 037__ $$aTHESIS
000198837 041__ $$aeng
000198837 088__ $$a6163
000198837 245__ $$aApproximation algorithms for regret minimization in vehicle routing problems
000198837 269__ $$a2014
000198837 260__ $$aLausanne$$bEPFL$$c2014
000198837 336__ $$aTheses
000198837 502__ $$aProf. M. Troyanov (président) ; Prof. F. Eisenbrand (directeur) ; Prof. L. Sanità,  Prof. M.G. Speranza,  Prof. O.N.A. Svensson (rapporteurs)
000198837 520__ $$aIn 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.
000198837 6531_ $$aCombinatorial Optimization
000198837 6531_ $$aApproximation algorithm
000198837 6531_ $$aVehicle routing problem
000198837 6531_ $$aOrienteering
000198837 6531_ $$aSet-cover integer linear programming formulation
000198837 700__ $$0243823$$aBock, Adrian Aloysius$$g199692
000198837 720_2 $$0240331$$aEisenbrand, Friedrich$$edir.$$g183121
000198837 8564_ $$s977737$$uhttps://infoscience.epfl.ch/record/198837/files/EPFL_TH6163.pdf$$yn/a$$zn/a
000198837 909C0 $$0252111$$pDISOPT$$xU11879
000198837 909CO $$ooai:infoscience.tind.io:198837$$pDOI$$pSB$$pthesis$$pthesis-bn2018$$qDOI2
000198837 917Z8 $$x108898
000198837 917Z8 $$x108898
000198837 917Z8 $$x108898
000198837 917Z8 $$x108898
000198837 918__ $$aSB$$cMATHAA$$dEDMA
000198837 919__ $$aDISOPT
000198837 920__ $$a2014-5-28$$b2014
000198837 970__ $$a6163/THESES
000198837 973__ $$aEPFL$$sPUBLISHED
000198837 980__ $$aTHESIS