Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/308110 
Year of Publication: 
2023
Citation: 
[Journal:] Operational Research [ISSN:] 1866-1505 [Volume:] 23 [Issue:] 3 [Article No.:] 49 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2023
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
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.
Subjects: 
Seat reservation
Maximum flow problem
Bipartite matching
NP-hardness
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.