A Mathematical Model for the Coach Trip with Shuttle Service Problem

;

URN urn:nbn:de:gbv:705-opus-31501
URL
Dokumentart: ResearchPaper
Institut: Institut für Informatik
Schriftenreihe: Research paper / Institut für Informatik, Helmut-Schmidt-Universität
Bandnummer: 2016-2
ISBN: 2198-3968
Sprache: Englisch
Erstellungsjahr: 2016
Publikationsdatum:
SWD-Schlagwörter: Optimierung , Routing
Freie Schlagwörter (Englisch): Coach Trip with Shuttle Service Problem , Computational Complexity , CPLEX , Routing , Transfers , VeRoLog Solver Challenge 2015 , CTSSP
DDC-Sachgruppe: Wirtschaft

Kurzfassung auf Englisch:

In this work we consider the Coach Trip with Shuttle Service Problem (CTSSP), which is a routing problem where passengers have to be transported from bus stops to a central hub with a fleet of coaches and shuttles. The capacity of each vehicle must not be exceeded and for each group of passengers waiting at a bus stop there is a maximal travel time that must not be exceeded while travelling to the hub. Shuttles can use bus stops as transfer points to drop their passengers from which they have to be picked up by a coach. Coaches must end their trip at the hub while shuttles can stop at any bus stop. The goal is to minimize costs. The costs consist of travelling costs of the used vehicles plus fixed costs for the usage of the shuttles. We prove the computational complexity of the problem and present a novel mathematical model for the CTSSP. This model is implemented in CPLEX and the optimal solution of the "example" instance of the VeRoLog Solver Challenge 2015 is shown.

Hinweis zum Urheberrecht

Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:

Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.

Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.