Linear Programming Model and Online Algorithm for Customer-Centric Train Calendar Generation. (21st June 2021)

• Record Type: Journal Article
• Authors: Bosi, Tommaso; D'Ariano, Andrea
• Other Names: Hassannayebi Erfan Academic Editor.
• Is Part Of: Journal of advanced transportation. Volume 2021(2021)
• Publication Date: 2021-06-21
• Subjects: Transportation -- Periodicals; 388.05
• DOI: 10.1155/2021/4664010
• Languages: English
• ISSNs: 0197-6729

Abstract

Abstract : An important objective for train operating companies is to let users, especially commuters, directly query the ICT system about trains' availability calendar, based on an online approach, and give them clear and brief information, expressed through "intelligent" phrases instead of bit maps. This paper provides a linear programming model of this problem and a fast and flexible heuristic algorithm to create descriptive sentences from train calendars. The algorithmic method, based on the "Divide and Conquer" approach, takes the calendar period queried in its whole and divides it into subsets, which are successively processed one by one. The dominant limitation of previous methods is their strong dependence on the size and complexity of instances. On the contrary, our computational findings show that the proposed online algorithm has a very limited and constant computation time, even when increasing the problem complexity, keeping its processing time between 0 and 16 ms, while producing good quality solutions that differ by an average surplus of 0.13 subsentences compared to benchmark state-of-art solutions.