A Metric Approach for the Two-Station Single-Track Railway Scheduling Problem

T. C. Edwin Cheng; Alexander Lazarev; Darya Lemtyuzhnikova

doi:10.1016/j.ifacol.2022.10.167

A Metric Approach for the Two-Station Single-Track Railway Scheduling Problem

T. C. Edwin Cheng, Alexander Lazarev, Darya Lemtyuzhnikova

Research output: Journal article publication › Conference article › Academic research › peer-review

4 Citations (Scopus)

Abstract

We consider the instance space metric method to the two-station single-track railway scheduling problem. This method has been effectively applied to several classical NP-hard scheduling problems, but was not tested on some actual railway scheduling models. It allows to construct the solutions with absolute error in polynomial time if there are some polynomially solvable instance subclasses for the initial NP-hard problem. Considering the metrics for the problem parameters space, we develop an innovative approach to solve the particular problem in polynomial time with absolute error and make some numerical tests.

Original language	English
Pages (from-to)	2875-2880
Number of pages	6
Journal	IFAC-PapersOnLine
Volume	55
Issue number	10
DOIs	https://doi.org/10.1016/j.ifacol.2022.10.167
Publication status	Published - 2022
Event	10th IFAC Conference on Manufacturing Modelling, Management and Control, MIM 2022 - Nantes, France Duration: 22 Jun 2022 → 24 Jun 2022

Keywords

maximum lateness
metric approach
optimization
railway planing
scheduling

ASJC Scopus subject areas

Control and Systems Engineering

More information

10.1016/j.ifacol.2022.10.167

Cite this

@article{3c170bd1fb304456bda77156c1130ebc,

title = "A Metric Approach for the Two-Station Single-Track Railway Scheduling Problem",

abstract = "We consider the instance space metric method to the two-station single-track railway scheduling problem. This method has been effectively applied to several classical NP-hard scheduling problems, but was not tested on some actual railway scheduling models. It allows to construct the solutions with absolute error in polynomial time if there are some polynomially solvable instance subclasses for the initial NP-hard problem. Considering the metrics for the problem parameters space, we develop an innovative approach to solve the particular problem in polynomial time with absolute error and make some numerical tests.",

keywords = "maximum lateness, metric approach, optimization, railway planing, scheduling",

author = "{Edwin Cheng}, {T. C.} and Alexander Lazarev and Darya Lemtyuzhnikova",

note = "Publisher Copyright: Copyright {\textcopyright} 2022 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/); 10th IFAC Conference on Manufacturing Modelling, Management and Control, MIM 2022 ; Conference date: 22-06-2022 Through 24-06-2022",

year = "2022",

doi = "10.1016/j.ifacol.2022.10.167",

language = "English",

volume = "55",

pages = "2875--2880",

journal = "IFAC-PapersOnLine",

issn = "2405-8963",

publisher = "IFAC Secretariat",

number = "10",

}

TY - JOUR

T1 - A Metric Approach for the Two-Station Single-Track Railway Scheduling Problem

AU - Edwin Cheng, T. C.

AU - Lazarev, Alexander

AU - Lemtyuzhnikova, Darya

PY - 2022

Y1 - 2022

N2 - We consider the instance space metric method to the two-station single-track railway scheduling problem. This method has been effectively applied to several classical NP-hard scheduling problems, but was not tested on some actual railway scheduling models. It allows to construct the solutions with absolute error in polynomial time if there are some polynomially solvable instance subclasses for the initial NP-hard problem. Considering the metrics for the problem parameters space, we develop an innovative approach to solve the particular problem in polynomial time with absolute error and make some numerical tests.

AB - We consider the instance space metric method to the two-station single-track railway scheduling problem. This method has been effectively applied to several classical NP-hard scheduling problems, but was not tested on some actual railway scheduling models. It allows to construct the solutions with absolute error in polynomial time if there are some polynomially solvable instance subclasses for the initial NP-hard problem. Considering the metrics for the problem parameters space, we develop an innovative approach to solve the particular problem in polynomial time with absolute error and make some numerical tests.

KW - maximum lateness

KW - metric approach

KW - optimization

KW - railway planing

KW - scheduling

UR - http://www.scopus.com/inward/record.url?scp=85144553607&partnerID=8YFLogxK

U2 - 10.1016/j.ifacol.2022.10.167

DO - 10.1016/j.ifacol.2022.10.167

M3 - Conference article

AN - SCOPUS:85144553607

SN - 2405-8963

VL - 55

SP - 2875

EP - 2880

JO - IFAC-PapersOnLine

JF - IFAC-PapersOnLine

IS - 10

T2 - 10th IFAC Conference on Manufacturing Modelling, Management and Control, MIM 2022

Y2 - 22 June 2022 through 24 June 2022

ER -

A Metric Approach for the Two-Station Single-Track Railway Scheduling Problem

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this