A set covering approach for multi-depot train driver scheduling

Masoud Yaghini (), Mohammad Karimi () and Mohadeseh Rahbar ()
Additional contact information
Masoud Yaghini: School of Railway Engineering, Iran University of Science and Technology
Mohammad Karimi: School of Railway Engineering, Iran University of Science and Technology
Mohadeseh Rahbar: School of Railway Engineering, Iran University of Science and Technology

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 7, 636-654

Abstract: Abstract The set covering problem (SCP), which has many practical applications, is one of the fundamental combinatorial problems. In this paper, a new neighborhood structure is proposed for solving this problem. In this structure, a linear programming (LP) model is generated by relaxing binary constraints, removing a selected column, and adding some inequalities. Then, a sub integer programming model, by joining the LP model solution and the incumbent solution, is created and its solution is considered as a neighbourhood solution. The neighbourhood structure can be implemented in various metaheuristics. This paper presents a matheuristic by combining a tabu search metaheuristic and the proposed neighbourhood structure. The matheuristic begins with an initial feasible solution. The initial solution is generated using a proposed heuristic method. The parameters of the matheuristic are tuned by a three-step method based on design of experiments. To evaluate the efficiency and effectiveness of the proposed algorithm, several standard test problems are used. The experimental results show the high performance of the proposed algorithm. Finally, a mathematical model based on the SCP is used to formulate the train driver scheduling (TDS) in Iranian railways. The TDS is performed in two phases, i.e., duty generation to build all feasible duties, and duty optimization to assign the best possible duty to each train. The breadth-first algorithm is applied to make duties. The generated duty optimization problem has about one million duties. For solving this huge model, the proposed matheuristic is used. The algorithm is successfully applied to solve the TDS in Iranian railways and the results are reported.

Keywords: Set covering problem; LP-based neighborhoods; Matheuristic; Tabu search; Design of experiment; Train drive scheduling; Iranian railways (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9612-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-013-9612-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9612-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().