cam a22 7 4500 316991236 CHVBK 20201029052737.0 cr ## ######## 140620s2014 sz sm 00 0 eng d oai:infoscience.epfl.ch:198837 urn:nbn:ch:bel-epfl-thesis6163-8 urn 10.5075/epfl-thesis-6163 doi (SNL)991017980976803976 (NEBIS)010147850 (Sz)991017980976803976 (Sz)001871316 Sz ger rda 510 23sdnb Bock Adrian Aloysius (DE-588)1220325872 Verfasser aut Approximation algorithms for regret minimization in vehicle routing problems Adrian Aloysius Bock Lausanne 2014 1 Online-Ressource Thèse no 6163 EPF Lausanne, 2014 application/pdf 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. KOMBINATORISCHE PROBLEME (DISKRETE OPTIMIERUNG) ger (ETHUDK)000013865 ethudk LINEARE OPTIMIERUNG (OPERATIONS RESEARCH) ger (ETHUDK)000013854 ethudk WEGPLANUNG + ZEITPLANUNG (OPERATIONS RESEARCH) ger (ETHUDK)000013866 ethudk Hochschulschrift (DE-588)4113937-9 gnd-content Hochschulschrift gnd-content xehelv xediss 2017 510 snl ehelv sb 2017/26 510 snl-sb u WEGPLANUNG + ZEITPLANUNG (OPERATIONS RESEARCH) ger 519.854.2,1 nebis E1 u KOMBINATORISCHE PROBLEME (DISKRETE OPTIMIERUNG) ger 519.854.2 nebis E1 u LINEARE OPTIMIERUNG (OPERATIONS RESEARCH) ger 519.852 nebis E1 u SCHEDULING + TIMETABLING (OPERATIONS RESEARCH) eng 519.854.2,1 nebis E1 u ROUTAGE + ORDONNANCEMENT (RECHERCHE OPÉRATIONNELLE) fre 519.854.2,1 nebis E1 u COMBINATORIAL PROBLEMS (DISCRETE PROGRAMMING) eng 519.854.2 nebis E1 u PROBLÈMES COMBINATOIRES (OPTIMISATION DISCRÈTE) fre 519.854.2 nebis E1 u OPTIMISATION LINÉAIRE (RECHERCHE OPÉRATIONNELLE) fre 519.852 nebis E1 u LINEAR PROGRAMMING (OPERATIONS RESEARCH) eng 519.852 nebis E1 École polytechnique fédérale de Lausanne (DE-588)1003500-X Grad-verleihende Institution dgg SNL NB001 NB999 - chb99 - Record https://infoscience.epfl.ch/record/198837 Thesis https://infoscience.epfl.ch/record/198837/files/EPFL_TH6163.pdf URN https://nbn-resolving.org/urn/resolver.pl?urn=urn:nbn:ch:bel-epfl-thesis6163-8 http://www.e-helvetica.nb.admin.ch/directAccess?callnumber=bel-epfl-thesis6163-8 BK020353 XK020053 XK020000 1 Hochschulschrift = Thèse/Mémoire 2 CF Elektron. Daten Fernzugriff=Fichier online EPF nebis E2 e-library 2014 these nebis EC 128 E01-20140623 052 E01-20140623 NEBIS E16 E16 RH HB 16896 NEBIS E02 E02 E02SP ZTH 6163 SNL 100 1- Bock Adrian Aloysius (DE-588)1220325872 Verfasser aut SNL 710 2- École polytechnique fédérale de Lausanne (DE-588)1003500-X Grad-verleihende Institution dgg SNL 856 40 Record https://infoscience.epfl.ch/record/198837 SNL 856 40 Thesis https://infoscience.epfl.ch/record/198837/files/EPFL_TH6163.pdf SNL 856 4- URN https://nbn-resolving.org/urn/resolver.pl?urn=urn:nbn:ch:bel-epfl-thesis6163-8 SNL 856 42 http://www.e-helvetica.nb.admin.ch/directAccess?callnumber=bel-epfl-thesis6163-8 NEBIS 700 1- Bock Adrian Aloysius NEBIS 700 1- Eisenbrand Friedrich 1971- (DE-588)1089485123 Akademischer Betreuer dgs NEBIS 856 -- https://dx.doi.org/10.5075/epfl-thesis-6163 Online via EPFL E-Library E02 SWISSBIB 316991236 ORANGE 316991236