000198837 001__ 198837 000198837 005__ 20190316235916.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$$pthesis-bn2018$$pDOI$$pSB$$pthesis$$qDOI2$$qGLOBAL_SET 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