Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/308110 
Autor:innen: 
Erscheinungsjahr: 
2023
Quellenangabe: 
[Journal:] Operational Research [ISSN:] 1866-1505 [Volume:] 23 [Issue:] 3 [Article No.:] 49 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2023
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
This paper introduces a novel optimisation problem motivated by the real-world application of transferring between trains. The driving idea is to minimise the walking distances of all transferring passengers by optimising the assignment of passengers to railcarriages in the seat reservation process. The focus of this work is on formalising and modelling the problem, which has not been studied before. It aims to provide a framework for future considerations. We present three versions of the problem with increasing difficulty: one-train-one-station, one-train-many-stations, and a general problem with multiple trains and stations. Since the simplest version of the problem is a pure assignment problem in the form of minimum-cost bipartite matching, our problem modelling and algorithmic solution approach remain closely related to maxflow problems as they represent a proven method for assignment problems. However, even the one-train-many-stations problem cannot be solved by transforming it into a standard maximum-flow problem. The main result shown is the NP-hardness of the general problem.
Schlagwörter: 
Seat reservation
Maximum flow problem
Bipartite matching
NP-hardness
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.