liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
Publications (10 of 27) Show all publications
Yu, L., Häll, C. H., Peterson, A. & Schmidt, C. (2023). A MILP Model for Rescheduling Freight Trains under an Unexpected Marshalling-Yard Closure. In: Rob Goverde, Francesco Corman, Ivan Belošević, Sanjin Milinković (Ed.), Book of Abstracts: . Paper presented at 10th International Conference on Railway Operations Modelling and Analysis (ICROMA), Belgrade, Serbia, April 25th – 28th, 2023 (pp. 68-68). The Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia
Open this publication in new window or tab >>A MILP Model for Rescheduling Freight Trains under an Unexpected Marshalling-Yard Closure
2023 (English)In: Book of Abstracts / [ed] Rob Goverde, Francesco Corman, Ivan Belošević, Sanjin Milinković, The Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia , 2023, p. 68-68Conference paper, Oral presentation with published abstract (Other academic)
Abstract [en]

This study is about rescheduling freight trains to reduce the eff ects of major interruptions. In this paper, we consider that the interruption is an unexpected marshallingyard closure. We develop a macroscopic Mixed-Integer Linear Programming (MILP)model to reschedule railway timetables. One important principle is that we simultaneously reschedule several trains, instead of one-by-one. Furthermore, we consider arescheduling strategy of letting trains wait on the way when the destination yard havea closure. The model considers stopping restrictions and the capacity of each segmentand station. The order of the trains aff ected by the interruption is not fi xed. We presentexperimental results of three diff erent cases, which are all based on artifi cial data.

Place, publisher, year, edition, pages
The Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia, 2023
Keywords
Railway timetable rescheduling; Major interruption; Mixed-integer linear programming
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-194846 (URN)978-86-7395-467-7 (ISBN)
Conference
10th International Conference on Railway Operations Modelling and Analysis (ICROMA), Belgrade, Serbia, April 25th – 28th, 2023
Available from: 2023-06-12 Created: 2023-06-12 Last updated: 2023-12-01
Yu, L., Häll, C. H., Peterson, A. & Schmidt, C. (2023). A MILP model for rescheduling freight trains under an unexpected marshalling-yard closure. In: : . Paper presented at 10th International Seminar on Railway Operations Modelling and Analysis RailBelgrade 2023, Belgrade, Serbia, April 25–28, 2023. , Article ID 51.
Open this publication in new window or tab >>A MILP model for rescheduling freight trains under an unexpected marshalling-yard closure
2023 (English)Conference paper, Oral presentation with published abstract (Other academic)
Abstract [en]

This study is about rescheduling freight trains to reduce the effects of major interruptions. In this paper, we consider that the interruption is an unexpected marshalling-yard closure. We develop a macroscopic Mixed-Integer Linear Programming (MILP) model to reschedule railway timetables. One important principle is that we simultaneously reschedule several trains, instead of one-by-one. Furthermore, we consider a rescheduling strategy of letting trains wait on the way when the destination yard have a closure. The model considers stopping restrictions and the capacity of each segment and station. The order of the trains affected by the interruption is not fixed. We present experimental results of three different cases, which are all based on artificial data.

Keywords
Railway timetable rescheduling; Major interruption; Mixed-integer linear programming
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-194871 (URN)
Conference
10th International Seminar on Railway Operations Modelling and Analysis RailBelgrade 2023, Belgrade, Serbia, April 25–28, 2023
Funder
Swedish Transport Administration
Available from: 2023-06-12 Created: 2023-06-12 Last updated: 2023-12-01Bibliographically approved
Nilsson, B. & Schmidt, C. (2023). k-Transmitter Watchman Routes. In: WALCOM: Algorithms and Computation: . Paper presented at 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023 (pp. 202-213). Springer, 13973
Open this publication in new window or tab >>k-Transmitter Watchman Routes
2023 (English)In: WALCOM: Algorithms and Computation, Springer , 2023, Vol. 13973, p. 202-213Conference paper, Published paper (Refereed)
Abstract [en]

We consider the watchman route problem for a k-transmitter watchman: standing at point p in a polygon P, the watchman can see if intersects P’s boundary at most k times—q is k-visible to p. Traveling along the k-transmitter watchman route, either all points in P or a discrete set of points must be k-visible to the watchman. We aim for minimizing the length of the k-transmitter watchman route. We show that even in simple polygons the shortest k-transmitter watchman route problem for a discrete set of points is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the k-transmitter watchman route problem for a given starting point and with approximation ratio (with). 

Place, publisher, year, edition, pages
Springer, 2023
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13973
Keywords
Approximation algorithm, k-Transmitter, k-Transmitter watchman route, NP-completeness, NP-Hardness, Watchman route, Transmitters, Discrete sets, NP Complete, Polylogarithmic approximation, Simple polygon, Watchman Route Problem, Approximation algorithms
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-194429 (URN)10.1007/978-3-031-27051-2_18 (DOI)2-s2.0-85151057723 (Scopus ID)978-3-031-27051-2 (ISBN)978-3-031-27050-5 (ISBN)
Conference
17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023
Note

Funding agencies: Supported by grants 2018-04001 (Nya paradigmer för autonom obemannad flygledning) and 2021-03810 (Illuminate: bevisbart goda algoritmer för bevakningsproblem) from the Swedish Research Council (Vetenskapsrådet).

Available from: 2023-06-07 Created: 2023-06-07 Last updated: 2023-06-07
Zahir, R., Schmidt, C. & Lidén, T. (2023). Shift Scheduling for Train Dispatchers. In: Rob Goverde, Francesco Corman, Ivan Belošević, Sanjin Milinković (Ed.), Book of Abstracts: . Paper presented at 10th International Conference on Railway Operations Modelling and Analysis (ICROMA), Belgrade, Serbia, April 25th – 28th, 2023 (pp. 120-120). The Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia
Open this publication in new window or tab >>Shift Scheduling for Train Dispatchers
2023 (English)In: Book of Abstracts / [ed] Rob Goverde, Francesco Corman, Ivan Belošević, Sanjin Milinković, The Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia , 2023, p. 120-120Conference paper, Oral presentation with published abstract (Other academic)
Abstract [en]

Train dispatchers monitor and control train traffi c from a dispatching center, which isresponsible for a certain region in the railway network. This region is divided into subareas, where each train dispatcher controls one or several subareas at any time. Giventhe high safety concerns of their profession, dispatchers’ working shifts should fulfi lseveral legal and operational constraints, such as bounds on the length of shifts andon the resting periods between shifts. To construct shift schedules for train dispatchers is a complex and time-consuming process that is currently done manually. In thispaper, we present an optimization framework to automate this process, based on amodel for single-day shifts. Here, we focus on the objective of minimizing the numberof dispatchers as a baseline for future objectives. We present experimental results forreal-world sized data (number of geographical areas and train movements in the orderof magnitude as for one dispatching center in Sweden, covering the southern partof the country). We study the impact on the run time for diff erent input parameters,namely: the total number of geographical areas, the maximum number of geographical areas that can be assigned to a dispatcher in any period, changes in adjacencybetween the geographical areas, and the number of geographical areas that eachdispatcher is qualifi ed to monitor. The run time for the instances is between 19 and305 seconds

Place, publisher, year, edition, pages
The Faculty of Transport and Traffic Engineering, University of Belgrade, Serbia, 2023
Keywords
Integer Programming; Shift scheduling; Railway dispatching; Area combination
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-194790 (URN)978-86-7395-467-7 (ISBN)
Conference
10th International Conference on Railway Operations Modelling and Analysis (ICROMA), Belgrade, Serbia, April 25th – 28th, 2023
Available from: 2023-06-12 Created: 2023-06-12 Last updated: 2023-06-12
Krohn, E., Nilsson, B. J. & Schmidt, C. (2022). Opposing Half Guards. In: 34th Canadian Conference on Computational Geometry: . Paper presented at 34th Canadian Conference on Computational Geometry (CCCG 2022), 25-27 August 2022, Toronto, Canada.
Open this publication in new window or tab >>Opposing Half Guards
2022 (English)In: 34th Canadian Conference on Computational Geometry, 2022Conference paper, Published paper (Refereed)
Abstract [en]

We study the art gallery problem for opposing halfguards: guards that can either see to their left or to theirright only. We present art gallery theorems, show thatthe problem is NP-hard in monotone polygons, presentapproximation algorithms for spiral and staircase poly-gons, and show that the location of half guards in 2-guardable polygons is not restricted to extensions.

National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-188013 (URN)
Conference
34th Canadian Conference on Computational Geometry (CCCG 2022), 25-27 August 2022, Toronto, Canada
Funder
Swedish Research Council, 2021-03810Swedish Research Council, 2018-0400
Available from: 2022-09-01 Created: 2022-09-01 Last updated: 2022-09-08Bibliographically approved
Akitaya, H., Ballinger, B., Demaine, E., Hull, T. & Schmidt, C. (2021). Folding Points to a Point and Lines to a Line. In: : . Paper presented at 33rd Canadian Conference on Computational Geometry, August 10-12, 2021.
Open this publication in new window or tab >>Folding Points to a Point and Lines to a Line
Show others...
2021 (English)Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-179298 (URN)
Conference
33rd Canadian Conference on Computational Geometry, August 10-12, 2021
Available from: 2021-09-16 Created: 2021-09-16 Last updated: 2021-11-12Bibliographically approved
Aichholzer, O., Akitaya, H., Cheung, K., Demaine, E., Demaine, M., Fekete, S. P., . . . Schmidt, C. (2021). Folding Polyominoes with Holes into a Cube. Computational geometry, 93, Article ID 101700.
Open this publication in new window or tab >>Folding Polyominoes with Holes into a Cube
Show others...
2021 (English)In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 93, article id 101700Article in journal (Refereed) Published
Abstract [en]

When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.

Place, publisher, year, edition, pages
Elsevier, 2021
Keywords
FoldingOrigami foldingCubePolyomino with holesNon-simple polyomino
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-169198 (URN)10.1016/j.comgeo.2020.101700 (DOI)000579185100004 ()2-s2.0-85089476554 (Scopus ID)
Note

Funding agencies: NSFNational Science Foundation (NSF) [CCF-1422311, 1423615]; Wittgenstein Prize, Austrian Science Fund (FWF)Austrian Science Fund (FWF) [Z 342-N31]

Available from: 2020-09-11 Created: 2020-09-11 Last updated: 2020-11-01Bibliographically approved
Ljunggren, F., Persson, K., Peterson, A. & Schmidt, C. (2021). Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path. Public Transport, 13, 597-623
Open this publication in new window or tab >>Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path
2021 (English)In: Public Transport, ISSN 1866-749X, E-ISSN 1613-7159, Vol. 13, p. 597-623Article in journal (Refereed) Published
Abstract [en]

We present an algorithm to insert a train path in an existing railway timetable close to operation, when we want to affect the existing (passenger) traffic as little as possible. Thus, we consider all other trains as fixed, and aim for a resulting train path that maximizes the bottleneck robustness, that is, a train path that maximizes the temporal distance to neighboring trains in the timetable. Our algorithm is based on a graph formulation of the problem and uses a variant of Dijkstra’s algorithm. We present an extensive experimental evaluation of our algorithm for the Swedish railway stretch from Malmö to Hallsberg. Moreover, we analyze the size of our constructed graph.

Place, publisher, year, edition, pages
Springer, 2021
Keywords
Railway timetabling; Robust train path; Bottleneck train path; Network algorithm; Freight transportation
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-170317 (URN)10.1007/s12469-020-00253-x (DOI)000573189200001 ()2-s2.0-85091503222 (Scopus ID)
Projects
Shift2Rail
Funder
EU, Horizon 2020, 730813; 777402
Note

Funding agency: Linköping University

Available from: 2020-10-09 Created: 2020-10-09 Last updated: 2022-10-28Bibliographically approved
Sáez, R., Prats, X., Polishchuk, T., Polishchuk, V. & Schmidt, C. (2020). Automation for Separation with CDOs: Dynamic Aircraft Arrival Routes. Journal of Air Transportation, 28(4), 144-154
Open this publication in new window or tab >>Automation for Separation with CDOs: Dynamic Aircraft Arrival Routes
Show others...
2020 (English)In: Journal of Air Transportation, ISSN 2380-9450, Vol. 28, no 4, p. 144-154Article in journal (Refereed) Published
Abstract [en]

We present a mixed-integer programming (MIP) approach to compute aircraft arrival routes in a terminal maneuvering area (TMA) that guarantee temporal separation of all aircraft arriving within a given time period, where the aircraft are flying according to the optimal continuous descent operation (CDO) speed profile with idle thrust. The arrival routes form a merge tree that satisfies several operational constraints, e.g., all merge points are spatially separated. We detail how the CDO speed profiles for different route lengths are computed. Experimental results are presented for calculation of fully automated CDO-enabled arrival routes during one hour of operation on a busy day at Stockholm TMA.

Place, publisher, year, edition, pages
AIAA International, 2020
Keywords
Continuous Descent Operations, Temporal Separation, Fuel-efficient Arrivals, Integer Programming
National Category
Aerospace Engineering
Identifiers
urn:nbn:se:liu:diva-169117 (URN)10.2514/1.D0176 (DOI)2-s2.0-85092417849 (Scopus ID)
Available from: 2020-09-09 Created: 2020-09-09 Last updated: 2022-01-18Bibliographically approved
Polishchuk, T., Polishchuk, V., Schmidt, C., Saéz, R., Prats, X., Hardell, H. & Smetanová, L. (2020). How to Achieve CDOs for All Aircraft: Automated Separation in TMAs: Enabling Flexible Entry Times and Accounting for Wake Turbulence Categories. In: : . Paper presented at SESAR Innovation Days 2020, December 7-10, 2020.
Open this publication in new window or tab >>How to Achieve CDOs for All Aircraft: Automated Separation in TMAs: Enabling Flexible Entry Times and Accounting for Wake Turbulence Categories
Show others...
2020 (English)Conference paper, Published paper (Refereed)
Abstract [en]

This work presents an enhanced optimization framework for fully automated scheduling of energy-efficient continuous-descent arrivals with guaranteed separation in the Terminal Maneuvering Area (TMA). On the example of a real heavy-traffic scenario at Stockholm Arlanda airport, we demonstrate that our approach enables scheduling of all planned arrivals during one hour of operation as continuous descents, by allowing flexible time of arrival to entry points within a range of ± 5 minutes. This provides significant savings in the time aircraft spend inside the TMA and a reduced fuel consumption. In addition, we integrate different aircraft wake turbulence categories that enable category-specific separation criteria. 

Keywords
Separation, MIP, CDO, Sequencing, Pressure
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:liu:diva-173982 (URN)
Conference
SESAR Innovation Days 2020, December 7-10, 2020
Available from: 2021-03-12 Created: 2021-03-12 Last updated: 2021-03-19Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-2548-5756

Search in DiVA

Show all publications