Train stop scheduling problem: An exact approach using valid inequalities and polar duality

Faiz Hamid and Yogesh K. Agarwal

European Journal of Operational Research, 2024, vol. 313, issue 1, 207-224

Abstract: Consider the problem of minimizing the number of train stops on a particular rail line. The objective is to assign passengers of each origin-destination pair to different trains in such a way that train capacity and passenger demand constraints are satisfied with minimal stoppages. The literature refers to this problem as the train stop scheduling problem. The problem has been extensively studied for decades, yet an exact solution approach has not been proposed. This paper proposes several valid inequalities to strengthen the mixed-integer programming formulation and solve the problem exactly in a reasonable amount of CPU time. The concept of polar duality has been utilized to find more complex valid inequalities which may be hard to find otherwise. Despite the problem’s high practical relevance, valid inequalities for the problem have not yet been studied in the literature. An aggregation procedure has been proposed to solve large size problem instances exactly. Computational study demonstrate the efficacy of the proposed valid inequalities.

Keywords: Integer programming; Valid inequality; Polar duality; Rail transportation; Train stop planning (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723005611
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:313:y:2024:i:1:p:207-224

DOI: 10.1016/j.ejor.2023.07.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().