liu.seSök publikationer i DiVA
Ändra sökning
Avgränsa sökresultatet
12 1 - 50 av 51
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Filtser, Omrit
    et al.
    Open Univ Israel, Israel.
    Krohn, Erik
    Univ Wisconsin Oshkosh, WI USA.
    Nilsson, Bengt J.
    Malmo Univ, Sweden.
    Rieck, Christian
    TU Braunschweig, Germany.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Guarding Polyominoes Under k-Hop Visibility2024Ingår i: LATIN 2024: THEORETICAL INFORMATICS, PT I, SPRINGER INTERNATIONAL PUBLISHING AG , 2024, Vol. 14578, s. 288-302Konferensbidrag (Refereegranskat)
    Abstract [en]

    We study the ART GALLERY Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from PLANAR MONOTONE 3SAT, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 x 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3 x 3 block of cells) for all k is an element of N.

  • 2.
    Yu, Liyun
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Häll, Carl Henrik
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A MILP Model for Rescheduling Freight Trains under an Unexpected Marshalling-Yard Closure2023Ingår i: 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, s. 68-68Konferensbidrag (Övrigt vetenskapligt)
    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.

  • 3.
    Yu, Liyun
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Häll, Carl Henrik
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A MILP model for rescheduling freight trains under an unexpected marshalling-yard closure2023Konferensbidrag (Övrigt vetenskapligt)
    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.

  • 4.
    Lemetti, Anastasia
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Meyer, Lothar
    Air Nav Serv Sweden LFV, Res & Innovat, Norrkoping, Sweden.
    Peukert, Maximilian
    Air Nav Serv Sweden LFV, Res & Innovat, Norrkoping, Sweden.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Discrete-Fourier-Transform-Based Evaluation of Physiological Measures as Workload Indicators2023Ingår i: 2023 IEEE/AIAA 42ND DIGITAL AVIONICS SYSTEMS CONFERENCE, DASC, IEEE , 2023Konferensbidrag (Refereegranskat)
    Abstract [en]

    We propose a new approach to evaluate ocular measurements of air traffic controllers (ATCOs) as potential workload and fatigue indicators. We employ the Fast Fourier transform (FFT) to test our assumption that humans respond to increasing fatigue with harmonic oscillations in the eye movement, while they respond to increasingly high workload with disruptions to these harmonic oscillations. The FFT yields the frequency spectrum and we suggest to use the center of gravity of this spectrum to capture the variations. We give a proof-of concept study to evaluate our approach and we were able to verify our hypotheses in some cases, in particular, we identify the fixation duration as a promising indicator of changes in workload.

  • 5.
    Nilsson, Bengt
    et al.
    Department of Computer Science and Media Technology, Malmö University, Malmö, Sweden.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    k-Transmitter Watchman Routes2023Ingår i: WALCOM: Algorithms and Computation, Springer , 2023, Vol. 13973, s. 202-213Konferensbidrag (Refereegranskat)
    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). 

  • 6.
    Erlandson, William
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. Keolis Sverige AB, Sweden.
    Häll, Carl Henrik
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Meta-Heuristic for inserting a robust train path in a non-cyclic timetable2023Ingår i: Transportation planning and technology (Print), ISSN 0308-1060, E-ISSN 1029-0354, Vol. 46, nr 7, s. 842-863Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Many freight trains depart Swedish marshalling yards before or after their planned departure times. Today, a deviating departure time is allowed if no conflicting train path can be found a few stations ahead. This increases the risk that the train might be delayed to its destination and cause delays to other trains. We present a meta-heuristic that modifies a timetable by adding a train path (for our freight train) and, if necessary, adjusting surrounding train paths. The aim of the insertion of the additional train path and the adjustments of the existing ones is to obtain a large bottleneck robustness, that is, the largest possible minimal temporal distance to any other train in the timetable. We provide experimental results for a Swedish railway stretch with a non-cyclic timetable and heterogeneous traffic. We show that we quickly add a train path, while improving the robustness of the timetable.

    Ladda ner fulltext (pdf)
    fulltext
  • 7.
    Demaine, Erik D.
    et al.
    MIT, MA 02139 USA.
    Löffler, Maarten
    Univ Utrecht, Netherlands.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Rectangular Spiral Galaxies are still hard2023Ingår i: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 110, artikel-id 101949Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers, the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is 180 degrees rotationally symmetric about its center. We show that this puzzle is NP-complete, ASP-complete, and #P-complete even if (a) all solutions to the puzzle have rectangles for polyominoes; or (b) the polyominoes are required to be rectangles and all solutions to the puzzle have just 1 x 1, 1 x 3, and 3 x 1 rectangles. The proof for the latter variant also implies NP/ASP/#P-completeness of finding a noncrossing perfect matching in distance-2 grid graphs where edges connect vertices of Euclidean distance 2. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exists a set of galaxies that exactly cover a given shape.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

    Ladda ner fulltext (pdf)
    fulltext
  • 8.
    Zahir, Rabii
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Lidén, Tomas
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Shift Scheduling for Train Dispatchers2023Ingår i: 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, s. 120-120Konferensbidrag (Övrigt vetenskapligt)
    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

  • 9.
    Hernández Romero, Eulalia
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Josefsson, Billy
    Air Nav Serv Sweden LFV, Sweden.
    Lemetti, Anastasia
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Integrating weather impact in air traffic controller shift scheduling in remote and conventional towers2022Ingår i: EURO Journal on Transportation and Logistics, ISSN 2192-4376, E-ISSN 2192-4384, Vol. 11Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Weather affects the work of air traffic controllers, however, for staff scheduling in Remote Tower Centers (RTCs) it has not been taken into account. We study the impact of various weather phenomena on air traffic controller (ATCO) taskload through structured interviews with ATCOs. We deduce taskload-driven impact factors and the corresponding thresholds for the intensity of the weather phenomena at several Swedish airports. To account for the uncertainty in the weather prediction, we obtain probabilistic weather data from Ensemble Prediction Systems (EPSs). Then we adjust our prior Mixed Integer Programming (MIP) model for RTC staff scheduling to account for uncertain impactful weather occurrences and yield a distribution for the necessary number of ATCOs for RTC staff scheduling. Our framework can be used for conventional towers as well. We quantify the impact of weather by comparing the number of controllers necessary to operate at five Swedish airports from a remote tower during two example days in 2020, with and without taking weather events into account. In our calculations we use historical weather and flight data to show that ignoring weather impact may lead to significant understaffing at a RTC.

    Ladda ner fulltext (pdf)
    fulltext
  • 10.
    Meyer, Lothar
    et al.
    LFV.
    Maximilian, Peukert
    LFV.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Investigating Ocular and Head-Yaw Measures as Indicators for Workload and Fatigue under Varying Taskload Conditions2022Konferensbidrag (Refereegranskat)
  • 11.
    Krohn, Erik
    et al.
    Department of Computer Science, University of Wisconsin, Oshkosh, Oshkosh, WI, USA.
    Nilsson, Bengt J
    Department of Computer Science and Media Technology, Malmö University, Sweden.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Opposing Half Guards2022Ingår i: 34th Canadian Conference on Computational Geometry, 2022Konferensbidrag (Refereegranskat)
    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.

  • 12.
    Saez, Raul
    et al.
    Tech Univ Catalonia UPC BarcelonaTech, Spain.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Hardell, Henrik
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. Luftfartsverket LFV, Sweden.
    Smetanová, Lucie
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Prats, Xavier
    Tech Univ Catalonia UPC BarcelonaTech, Spain.
    Automated sequencing and merging with dynamic aircraft arrival routes and speed management for continuous descent operations2021Ingår i: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 132, artikel-id 103402Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper, we present a novel methodology to manage arrival traffic in terminal airspace. We define two areas around the airport, aiming to efficiently schedule incoming traffic. A four-dimensional (4D) trajectory negotiation/synchronization process between the air traffic control officer (ATCO) and the aircraft is performed in the pre-sequencing area, while the aircraft are still in the en-route phase of flight. On the other hand, in the dynamic-trajectories area, the ATCO, with the help of a ground support tool, generates dynamic arrival routes that automatically adapt to the current traffic demand. These arrival routes allow the aircraft to fly neutral continuous descent operations (CDOs, descents with idle thrust and no speed-brakes usage) and to ensure a separation throughout the arrival procedure. We choose a mixed-integer-programming approach to generate the arrival routes, while we formulate and solve an optimal control problem to generate a set of candidate CDOs per aircraft. Results show that, with a sufficient look-ahead time, it is possible to assign a required time of arrival (RTA) within each aircraft-arrival time window that would allow to efficiently schedule traffic even in the most challenging and dense scenarios. Besides improving efficiency of current operations in terminal airspace, the methodology presented in this paper could become a technical enabler towards an extended arrival manager (E-AMAN) with extended capabilities and, ultimately, to a fully deployed trajectory based operations (TBO) environment.

    Ladda ner fulltext (pdf)
    fulltext
  • 13.
    Sáez, Rául
    et al.
    Department of Physics - Aerospace Engineering Division, Technical University of Catalonia (UPC) - BarcelonaTech, Castelldefels, Barcelona, Spain.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Hardell, Henrik
    Linköpings universitet, Tekniska fakulteten. Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Procedure Design Unit, Luftfartsverket (LFV), Norrköping, Sweden.
    Smetanová, Lucie
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Prats, Xavier
    Department of Physics - Aerospace Engineering Division, Technical University of Catalonia (UPC) - BarcelonaTech, Castelldefels, Barcelona, Spain.
    Automated Sequencing and Merging with Dynamic Aircraft Arrival Routes and Speed Management for Continuous Descent Operations2021Ingår i: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 132, artikel-id 103402Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper, we present a novel methodology to manage arrival traffic in terminal airspace. We define two areas around the airport, aiming to efficiently schedule incoming traffic. A four-dimensional (4D) trajectory negotiation/synchronization process between the air traffic control officer (ATCO) and the aircraft is performed in the pre-sequencing area, while the aircraft are still in the en-route phase of flight. On the other hand, in the dynamic-trajectories area, the ATCO, with the help of a ground support tool, generates dynamic arrival routes that automatically adapt to the current traffic demand. These arrival routes allow the aircraft to fly neutral continuous descent operations (CDOs, descents with idle thrust and no speed-brakes usage) and to ensure a separation throughout the arrival procedure. We choose a mixed-integer-programming approach to generate the arrival routes, while we formulate and solve an optimal control problem to generate a set of candidate CDOs per aircraft. Results show that, with a sufficient look-ahead time, it is possible to assign a required time of arrival (RTA) within each aircraft-arrival time window that would allow to efficiently schedule traffic even in the most challenging and dense scenarios. Besides improving efficiency of current operations in terminal airspace, the methodology presented in this paper could become a technical enabler towards an extended arrival manager (E-AMAN) with extended capabilities and, ultimately, to a fully deployed trajectory based operations (TBO) environment.

  • 14.
    Akitaya, Hugo
    et al.
    Department of Computer Science, University of Massachusetts Lowell, Lowell, Massachusetts, United States.
    Ballinger, Brad
    Humbolt State University, Arcata, California, United States.
    Demaine, Erik
    Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, United States.
    Hull, Thomas
    Department of Mathematics, Western New England University, Springfield, Massachusetts, United States.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Folding Points to a Point and Lines to a Line2021Konferensbidrag (Refereegranskat)
  • 15.
    Aichholzer, Oswin
    et al.
    Institute for Software Technology, Graz University of Technology, Austria.
    Akitaya, Hugo
    School of Computer Science, Carleton University, Canada.
    Cheung, Kenny
    NASA Ames Research Center, United States of America.
    Demaine, Erik
    CSAIL, Massachusetts Institute of Technology, United States of America.
    Demaine, Martin
    CSAIL, Massachusetts Institute of Technology, United States of America.
    Fekete, Sándor P.
    Department of Computer Science, TU Braunschweig, Germany.
    Kleist, Linda
    Department of Computer Science, TU Braunschweig, Germany.
    Kostitsyna, Irina
    Mathematics and Computer Science Department, TU Eindhoven, Netherlands.
    Löffler, Maarten
    Department of Information and Computing Science, Universiteit Utrecht, Netherlands.
    Masárová, Zuzana
    IST Austria, Klosterneuburg, Austria.
    Mundilova, Klara
    CSAIL, Massachusetts Institute of Technology, United States of America.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Folding Polyominoes with Holes into a Cube2021Ingår i: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 93, artikel-id 101700Artikel i tidskrift (Refereegranskat)
    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.

  • 16.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Guarding Polyominoes under k-Hop Visibility or Minimum k-Dominating Sets in Grid Graphs2021Konferensbidrag (Övrigt vetenskapligt)
  • 17.
    Erlandson, William
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Häll, Carl Henrik
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Meta-Heuristic for Inserting a Robust Train Path in a Non-Cyclic Timetable2021Konferensbidrag (Övrigt vetenskapligt)
  • 18.
    Ljunggren, Fredrik
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Persson, Kristian
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Railway timetabling: a maximum bottleneck path algorithm for finding an additional train path2021Ingår i: Public Transport, ISSN 1866-749X, E-ISSN 1613-7159, Vol. 13, s. 597-623Artikel i tidskrift (Refereegranskat)
    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.

    Ladda ner fulltext (pdf)
    fulltext
  • 19.
    Sáez, Raul
    et al.
    Technical University of Catalonia, Castelldefels, Spain.
    Prats, Xavier
    Technical University of Catalonia, Castelldefels, Spain.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Automation for Separation with CDOs: Dynamic Aircraft Arrival Routes2020Ingår i: Journal of Air Transportation, ISSN 2380-9450, Vol. 28, nr 4, s. 144-154Artikel i tidskrift (Refereegranskat)
    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.

  • 20.
    Polishchuk, Tatiana
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Saéz, Raúl
    Department of Physics - Aerospace division Technical University of Catalonia (UPC) Castelldefels, Barcelona, Spain.
    Prats, Xavier
    Department of Physics - Aerospace division Technical University of Catalonia (UPC) Castelldefels, Barcelona, Spain.
    Hardell, Henrik
    Linköpings universitet, Tekniska fakulteten. Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Procedure Design Unit, Luftfartsverket (LFV), Norrkoping, Sweden.
    Smetanová, Lucie
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. Czech Technical University, Prague, Czech Republic.
    How to Achieve CDOs for All Aircraft: Automated Separation in TMAs: Enabling Flexible Entry Times and Accounting for Wake Turbulence Categories2020Konferensbidrag (Refereegranskat)
    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. 

  • 21.
    Polishchuk, Tatiana
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Lemetti, Anastasia
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Josefsson, Billy
    LFV.
    Integrating Weather Impact in RTC Staff Scheduling2020Konferensbidrag (Refereegranskat)
    Ladda ner fulltext (pdf)
    fulltext
  • 22.
    Polishchuk, Valentin
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Special Issue on the 33rd European Workshop on Computational Geometry, Guest Editors Foreword2020Ingår i: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 87, artikel-id UNSP 101590Artikel i tidskrift (Övrigt vetenskapligt)
    Abstract [en]

    n/a

  • 23.
    Josefsson, Billy
    et al.
    LFV.
    Meyer, Lothar
    LFV.
    Peukert, Maximilian
    LFV.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Validation of Controller Workload Predictors at Convenonal and Remote Towers2020Konferensbidrag (Refereegranskat)
  • 24.
    Andersson Granberg, Tobias
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A framework for integrated terminal airspace design2019Ingår i: Aeronautical Journal, ISSN 0001-9240, Vol. 123, nr 1263, s. 567-585Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Route planning and airspace sectorisation are two central tasks in air traffic management. Traditionally, the routing and sectorisation problems were considered separately, with aircraft trajectories serving as input to the sectorisation problem and, reciprocally, sectors being part of the input to the path finding algorithms. In this paper we propose a simultaneous design of routes and sectors for a transition airspace. We compare two approaches for this integrated design: one based on mixed integer programming, and one Voronoi-based model that separates potential "hotspots" of controller activity resulting from the terminal routes. We apply our two approaches to the design of Stockholm Terminal Maneuvering Area.

  • 25.
    Josefsson, Billy
    et al.
    ATCO, Manager, Automation and Human Performance, LFV Research and Innovation, Norrköping, Sweden.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A Step Towards Remote Tower Center Deployment: Optimizing Staff Scheduling2019Ingår i: Journal of Air Transportation, E-ISSN 2380-9450, Vol. 27, nr 3Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Remote tower service is one of the technological and operational solutions delivered for deployment by the Single European Sky Air Traffic Management Research Program. This new concept fundamentally changes how operators provide air traffic services as it becomes possible to control several airports from a single remote center. In such settings, an air traffic controller works at a so-called multiple position in the remote center; that is, he/she handles two or more airports from one remote tower module, that is, the controller working position. In this paper, an optimization framework is presented for traffic management at five Swedish airports that were chosen for remote operation using a remote tower center designed to serve a number of airports. The problems experienced with real airport schedules are highlighted, and optimal assignments of the airports to the remote tower modules are presented. Both scheduled traffic and special (nonscheduled) traffic at these five airports are considered.

  • 26.
    Daescu, Ovidiu
    et al.
    University of Texas at Dallas, Richardson, TX, USA.
    Friedrichs, Stephan
    Max Planck Institute for Informatics, Saarbrücken, Germany; Saarbrücken Graduate School of Computer Science, Saarbrücken, Germany.
    Malik, Hemant
    University of Texas at Dallas, Richardson, TX, USA.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Altitude Terrain Guarding and Guarding Uni-Monotone Polygons2019Ingår i: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 84, s. 22-35Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We present an optimal, linear-time algorithm for the following version of terrain guarding: given a 1.5D terrain and a horizontal line, place the minimum number of guards on the line to see all of the terrain. We prove that the cardinality of the minimum guard set coincides with the cardinality of a maximum number of “witnesses”, i.e., terrain points, no two of which can be seen by a single guard. We show that our results also apply to the Art Gallery problem in “monotone mountains”, i.e., x-monotone polygons with a single edge as one of the boundary chains. This means that any monotone mountain is “perfect” (its guarding number is the same as its witness number); we thus establish the first non-trivial class of perfect polygons.

    Ladda ner fulltext (pdf)
    fulltext
  • 27.
    Peterson, Anders
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Applying Geometric Thick Paths to Compute the Maximum Number of Additional Train Paths in a Railway Timetable2019Konferensbidrag (Refereegranskat)
  • 28.
    Sáez, Raul
    et al.
    UPC Barcelona.
    Prats, Xavier
    UPC Barcelona.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Automation for Separation with CDOs: Dynamic Aircraft Arrival Routes2019Konferensbidrag (Refereegranskat)
  • 29.
    Peterson, Anders
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Wahlborg, Magnus
    Railway Traffic and sale, Trafikverket, Borlänge.
    Häll, Carl Henrik
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Kordnejad, Behzad
    Transportplanering, Royal Institute of Technology (KTH), Stockholm, Sweden.
    Warg, Jennifer
    Transportplanering, Royal Institute of Technology (KTH), Stockholm, Sweden.
    Johansson, Ingrid
    Transportplanering, Royal Institute of Technology (KTH), Stockholm, Sweden.
    Joborn, Martin
    Systems Engineering, RISE Research Institutes of Sweden, Göteborg, Sweden.
    Gestrelius, Sara
    Systems Engineering, RISE Research Institutes of Sweden, Göteborg, Sweden.
    Törnquist Krasemann, Johanna
    Department of Computer Science, Blekinge tekniska högskola, Karlskrona, Sweden.
    Josyula, Sai Prashanth
    Department of Computer Science, Blekinge tekniska högskola, Karlskrona, Sweden.
    Palmqvist, Carl-William
    Transport Systems and Logistics, Lund University, Sweden.
    Lidén, Tomas
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. Swedish National Road and Transport Research Institute (VTI), Linköping, Sweden.
    Deliverable D 3.1: Analysis of the gap between daily timetable and operational traffic2019Rapport (Övrigt vetenskapligt)
    Abstract [en]

    Fr8Rail II/Work-Package 3 Real-time network management and improved methods for timetable planning addresses the problem to improve capacity and punctuality in the railway system by developing concepts and methods for tactical planning and operational traffic. In this report the state-of-the-art has been summarised.

    The aim of the project is to:

    • Propose concepts and methods that improve the annual and short-term timetable planning.
    • Demonstrate how the proposed timetable planning concepts improve the prerequisites for real-time network management.
    • Develop methods and tools that can reduce inefficiencies in real time network management.

    An important aspect is to improve the coordination between yards/terminals and the line network, and between Infrastructure Manager, Yard Managers, and freight Rail Undertakings.

    We motivate our research by the current situation in Sweden, which is characterised by low on-time performance for freight trains, dense and heterogenous traffic on the major railway lines, and a rigid annual timetabling process, which is non-suitable for short-term changes. We believe that better tools for network planning and management on tactical and operational level can help to connect planning and operational processes.

    Aiming for improvements of the operational traffic, there is a need for systematic development of methods applied at several planning horizons, based on both simulation and optimization techniques. Close to operation fast methods are needed, for example, based on meta-heuristics.

    The maintenance planning process and improvement potential have been described. This is a new piece of the puzzle and it is important to close the gap between timetable planning and operational traffic. The different planning processes at the Infrastructure Manager, the Rail Undertakings and the Maintenance Contractors should be aligned.

    When developing new approaches for computational decision-support tools for real-time network management, it is important — but very challenging — to evaluate and benchmark with existing software tools. We also observe that the research stream on computational decision-support and algorithm development for railway traffic management has not yet been sufficiently merged with the corresponding research stream focusing on aspects of human computer interaction.

    Ladda ner fulltext (pdf)
    fulltext
  • 30.
    Aichholzer, Oswin
    et al.
    Graz University of Technology.
    Akitaya, Hugo
    Tufts University.
    Cheung, Kenny
    NASA Ames Research Center.
    Demaine, Erik
    Massachusetts Institute of Technology.
    Demaine, Martin
    Massachusetts Institute of Technology.
    Fekete, Sándor
    TU Braunschweig.
    Kleist, Linda
    TU Braunschweig.
    Kostitsyna, Irina
    TU Eindhoven.
    Löffler, Maarten
    Universiteit Utrecht.
    Masárová, Zuzana
    IST Austria.
    Mundilova, Klara
    Massachusetts Institute of Technology.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Folding Polyominoes with Holes into a Cube2019Konferensbidrag (Refereegranskat)
  • 31.
    Andersson Granberg, Tobias
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Integer Programming-Based Airspace Sectorization for Terminal Maneuvering Areas with Convex Sectors2019Ingår i: Journal of Air Transportation, E-ISSN 2380-9450, Vol. 27, nr 4Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper an airspace sectorization framework for terminal maneuvering areas based on mixed integer programming is presented. It incorporates an airspace complexity representation, as well as various constraints on the sectors’ geometry, for example, the requirement that points demanding increased attention from air traffic controllers should lie in the sector’s interior to allow for enough time to resolve possible conflicts. The method can enforce convex sectors. In contrast to earlier integer/constraint programming approaches, which used synthesis methods with variables per elementary airspace piece that were glued together to form sectors, the integer programming formulation uses a variable per potential edge on the sector boundary. It is also the first step toward an integrated design of routes, the resulting complexity, and a sectorization. This paper presents results for Stockholm Arlanda airport and compares the integer programming results to convex sectorizations obtained by enumerating all possible topologies for a given number of sectors. This yields a proof-of-concept for the application of this highly flexible approach to terminal maneuvering areas.

    Ladda ner fulltext (pdf)
    fulltext
  • 32.
    Dahlberg, Joen
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Andersson Granberg, Tobias
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Sedov, Leonid
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Capacity-Driven Automatic Design of Dynamic Aircraft Arrival Routes2018Ingår i: 2018 IEEE/AIAA 37TH DIGITAL AVIONICS SYSTEMS CONFERENCE (DASC), IEEE , 2018, s. 1194-1202Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present a Mixed-Integer Programming framework for the design of aircraft arrival routes in a Terminal Maneuvering Area (TMA) that guarantee temporal separation of aircraft. The output routes constitute operationally feasible merge trees, and guarantee that the overall traffic pattern in the TMA can be monitored by air traffic controllers; in particular, we ensure that all aircraft on the arrival routes are separated in time and all merge points are spatially separated. We present a proof of concept of our approach, and demonstrate its feasibility by experiments for arrival routes during one hour at Stockholm TMA.

  • 33.
    Cannon, Sarah
    et al.
    College of Computing, Georgia Institute of Technology, Atlanta, USA.
    Fai, Thomas
    Paulson School of Engineering and Applied Sciences, Harvard University, MA, USA.
    Iwerks, Justin
    Mathematics Department, The Spence School, NY, USA.
    Leopold, Undine
    Mathematics Department, Technische Universität Chemnitz, Germany.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Combinatorics and complexity of guarding polygons with edge and point 2-transmitters2018Ingår i: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 68, s. 89-100Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We consider a generalization of the classical Art Gallery Problem, where instead of a light source, the guards, called k-transmitters, model a wireless device with a signal that can pass through at most k walls. We show it is NP-hard to compute a minimum cover of point 2-transmitters, point k-transmitters, and edge 2-transmitters in a simple polygon. The point 2-transmitter result extends to orthogonal polygons. In addition, we give necessity and sufficiency results for the number of edge 2-transmitters in general, monotone, orthogonal monotone, and orthogonal polygons.

  • 34.
    Wahlborg, Magnus
    et al.
    Swedish Transport Administration (Trafikverket), Borlänge, Sweden.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Gruosso, Lucia
    Ansaldo STS, Genova, Italy.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Jalili, Leila
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    D3.1 – Final pre-study for an improved methodology for timetable planning including state-of-the-art and future work plan2018Rapport (Övrigt vetenskapligt)
    Abstract [en]

    In ARCC project work package 3, research and innovation activities have been done to identify areas with a need for improved timetable planning methods and outline how new methods can be developed and implemented.

    Improved timetable planning scope were described and there was an activity to connect to other relevant Shift2Rail projects. An workshop was organised in Stockholm 2018-05-29.

    State of the art in practice was described for timetable planning in Sweden, UIC 406 method and Ansaldo STS Traffic management systems. Also state of the art in algorithms was described.

    Future work plan research needs areas are:

    1. Understanding of various goals for timetabling and how they co-variate

    2. Residual capacity

    3. Connection and coordination of the planning processes

    4. Connection and coordination of the yard/terminal planning and network planning

    5. Integration of freight trains into the timetable, focusing on short-term and ad-hoc

    6. Integration of maintenance scheduling and timetabling, at all planning stages

    7. Improved decision support for handeling of deviations from timetable in operations

    8. Features of planning tools, and implementation of automatized timetabling

    Ladda ner fulltext (pdf)
    fulltext
  • 35.
    Josefsson, Billy
    et al.
    Air Navigation Services of Sweden (LFV), Research & Innovation, Norrköping, Sweden.
    Jakobi, Joern
    Institute of Flight Guidance German Aerospace Center (DLR), Braunschweig, Germany.
    Papenfuss, Anne
    Institute of Flight Guidance German Aerospace Center (DLR), Braunschweig, Germany.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Sedov, Leonid
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Identification of Complexity Factors for Remote Towers2018Ingår i: SESAR Innovation Days, SESAR Joint Undertaking , 2018, artikel-id 157125Konferensbidrag (Refereegranskat)
    Abstract [en]

    An implementation of the Remote Tower concept comes with the challenge of optimizing staff resources subject to safety requirements. To distinguish safe from unsafe assignments, the quantification of tower controller workload—which is not a new problem—needs to be reconsidered in the setting of a remote tower environment. We plan to identify the remote operation specific complexity factors, which will be the basis of finding measures that have a high correlation to these factors that together describe the workload. In this paper, we analyze simulation data for these complexity factors. In the simulation different controllers rated the workload while monitoring multiple airports (either with simultaneously visible screens, or switching between the displays). We focus on complexity factors that stem from the interplay of Tower and Ground Control. The resulting list of the most significant complexity factors gives a base for our future quantification of remote tower controller workload. © 2018, SESAR Joint Undertaking. All rights reserved.

  • 36.
    Ljunggren, Fredrik
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. Trafikverket.
    Persson, Kristian
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. Sweco.
    Peterson, Anders
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Maximum Robust Train Path for an Additional Train Inserted in an Existing Railway Timetable2018Konferensbidrag (Övrigt vetenskapligt)
    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. 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.

  • 37.
    Andersson Granberg, Tobias
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A Framework for Integrated Terminal Airspace Design2017Konferensbidrag (Refereegranskat)
  • 38.
    Andersson Granberg, Tobias
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A Novel MIP-based Airspace Sectorization for TMAs2017Ingår i: 12th USA/Europe Air Traffic Management R and D Seminar, EUROCONTROL , 2017Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present a MIP-based airspace sectorization framework for Terminal Maneuvering Areas (TMAs). It incorporates an airspace complexity representation, as well as various constraints on the sectors' geometry, e.g., the requirement that points that demand increased attention from air traffic controllers should lie in the sector's interior to allow for enough time to resolve possible conflicts. In contrast to earlier integer/constraint programming approaches, which used synthesis methods with variables per elementary airspace piece that were glued together to form sectors, our IP formulation uses a variable per potential edge on the sector boundary. It is also the first step towards an integrated design of routes, the resulting complexity, and a sectorization. We present results for Stockholm TMA.

  • 39.
    Josefsson, Billy
    et al.
    LFV Research & Innovation, Sweden.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    A Step Towards Remote Tower Center Deployment: Optimizing Staff Scheduling2017Ingår i: 11th USA/Europe Air Traffic Management Research and Development Seminar 2015: Proceedings, The European Organisation for the Safety of Air Navigation , 2017Konferensbidrag (Refereegranskat)
    Abstract [en]

    —Remote Tower Service (RTSs) is one of the technological and operational solutions delivered for deployment by the Single European Sky ATM Research (SESAR) Programme. This new concept fundamentally changes how operators provide Air Traffic Services, as it becomes possible to control several airports from a single remote center. In such settings an air traffic controller works at a so-called “multiple position” in the remote center, that is, he/she handles two or more airports from one Remote Tower Module (RTM), i.e the controller working position. In this paper, we present an optimization framework for the traffic management at five Swedish airports that were chosen for remote operation using a Remote Tower Center designed to serve a number of airports. We highlight the problems experienced with real airport schedules, and present optimal assignments of the airports to the RTMs. We consider both scheduled traffic and special (non-scheduled) traffic at these five airports.

  • 40.
    Ernestus, Maximilian
    et al.
    TU Braunschweig, Germany.
    Friedrichs, Stephan
    Max Planck Institute Informat, Germany; Saarbrucken Grad School Comp Science, Germany.
    Hemmer, Michael
    TU Braunschweig, Germany.
    Kokemueller, Jan
    TU Braunschweig, Germany.
    Kroeller, Alexander
    TU Braunschweig, Germany.
    Moeini, Mahdi
    Technical University of Kaiserslautern, Germany.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Algorithms for art gallery illumination2017Ingår i: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 68, nr 1, s. 23-45Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The art gallery problem (AGP) is one of the classical problems in computational geometry. It asks for the minimum number of guards required to achieve visibility coverage of a given polygon. The AGP is well-known to be NP-hard even in restricted cases. In this paper, we consider the AGP with fading (AGPF): A polygonal region is to be illuminated with light sources such that every point is illuminated with at least a global threshold, light intensity decreases over distance, and we seek to minimize the total energy consumption. Choosing fading exponents of zero, one, and two are equivalent to the AGP, laser scanner applications, and natural light, respectively. We present complexity results as well as a negative solvability result. Still, we propose two practical algorithms for AGPF with fixed light positions (e.g. vertex guards) independent of the fading exponent, which we demonstrate to work well in practice. One is based on a discrete approximation, the other on non-linear programming by means of simplex-partitioning strategies. The former approach yields a fully polynomial-time approximation scheme for the AGPF with fixed light positions. The latter approach obtains better results in our experimental evaluation.

    Ladda ner fulltext (pdf)
    fulltext
  • 41.
    Fekete, Sándor P.
    et al.
    Department of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Haas, Andreas
    Department of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Hemmer, Michael
    Department of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Hoffmann, Michael
    Department of Computer Science, ETH Zürich, Zürich, Switzerland.
    Kostitsyna, Irina
    Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands.
    Krupke, Dominik
    Department of Computer Science, TU Braunschweig, Braunschweig, GermanyDepartment of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Maurer, Florian
    Department of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Mitchell, Joseph S.B.
    Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA.
    Schmidt, Arne
    Department of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Troegel, Julian
    Department of Computer Science, TU Braunschweig, Braunschweig, Germany.
    Computing Nonsimple Polygons of Minimum Perimeter2017Ingår i: Journal of Computational Geometry, E-ISSN 1920-180X, Vol. 8, nr 1Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We consider the Minimum Perimeter Polygon Problem (MP3): for a given set V of points in the plane, find a polygon P with holes that has vertex set V , such that the total boundary length is smallest possible. The MP3 can be considered a natural geometric generalization of the Traveling Salesman Problem (TSP), which asks for a simple polygon with minimum perimeter. Just like the TSP, the MP3 occurs naturally in the context of curve reconstruction. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MP3. On the positive side, we provide constant-factor approximation algorithms. In addition to algorithms with theoretical worst-case guarantess, we provide practical methods for computing provably optimal solutions for relatively large instances, based on integer programming. An additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that restricting the set of connections between points to edges of the Delaunay triangulation yields results that are on average within 0.5% of the optimum for large classes of benchmark instances. 

  • 42.
    Schmidt, Christiane
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Andersson Granberg, Tobias
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    CONVEX SECTORIZATION-A NOVEL INTEGER PROGRAMMING APPROACH2017Ingår i: 2017 INTEGRATED COMMUNICATIONS, NAVIGATION AND SURVEILLANCE CONFERENCE (ICNS), IEEE , 2017Konferensbidrag (Övrigt vetenskapligt)
    Abstract [en]

    We present a MIP-based airspace sectorization framework for Terminal Maneuvering Areas that can enforce convex sectors. The approach integrates an airspace complexity representation, and the resulting sectorizations have a balanced taskload. We present results for Stockholm TMA; and compare our results to convex sectorizations obtained by enumerating all possible topologies for a given number of sectors.

  • 43.
    Schmidt, Christiane
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Andersson Granberg, Tobias
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Convex Sectorization--a Novel Integer Programming Approach2017Ingår i: 2017 INTEGRATED COMMUNICATIONS, NAVIGATION AND SURVEILLANCE CONFERENCE (ICNS), IEEE, 2017Konferensbidrag (Refereegranskat)
    Abstract [en]

    The powerpoint presentation is about review of sectorization method that balances sector task load through extension by convex sectors, the results for Stockholm TMA. Also provides the comparison to convex sectorizations obtained by enumerating all possible topoligies for the given #sectors with highly flexible approach and fine-grained view on the TMA.

  • 44.
    Josefsson, Billy
    et al.
    LFV Research & Innovation, Stockholm, Sweden.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Scheduling Air Traffic Controllers at the Remote Tower Center2017Ingår i: Digital Avionics Systems Conference (DASC), 2017 IEEE/AIAA 36th, IEEE, 2017Konferensbidrag (Refereegranskat)
    Abstract [en]

    Remote Tower Service (RTS) is one of the technological and operational solutions delivered for deployment by the Single European Sky ATM Research (SESAR) Programme. This new concept fundamentally changes how operators provide Air Traffic Services, as it becomes possible to control several airports from a single remote center. In such settings an air traffic controller works at a so-called “multiple position” at the Remote Tower Center (RTC), which means that he/she can handle two or more airports from one Remote Tower Module (controller working position). In this paper, we present an optimization framework designed for automation of staff planning at the RTC. We highlight the problems experienced with real airport flight schedules, and present optimal shift assignments for five Swedish airports that were chosen for remote operation.

  • 45.
    Dahlberg, Joen
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Stakeholder Cooperation for Improved Predictability and Lower Cost Remote Services2017Konferensbidrag (Refereegranskat)
  • 46.
    Andersson Granberg, Tobias
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Automatic Design of Aircraft Arrival Routes with Limited Turning Angle2016Ingår i: 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) / [ed] Marc Goerigk and Renato Werneck, Dagstuhl, Germany, 2016, Vol. 54, s. 9:1-9:13Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present an application of Integer Programming to the design of arrival routes for aircraft in a Terminal Maneuvering Area (TMA). We generate operationally feasible merge trees of curvature-constrained routes, using two optimization criteria: (1) total length of the tree, and (2) distance flown along the tree paths. The output routes guarantee that the overall traffic pattern in the TMA can be monitored by air traffic controllers; in particular, we keep merge points for arriving aircraft well separated, and we exclude conflicts between arriving and departing aircraft. We demonstrate the feasibility of our method by experimenting with arrival routes for a runway at Arlanda airport in the Stockholm TMA. Our approach can easily be extended in several ways, e.g., to ensure that the routes avoid no-fly zones.

    Ladda ner fulltext (pdf)
    Automatic Design of Aircraft Arrival Routes with Limited Turning Angle
  • 47.
    Fekete, Sandor P.
    et al.
    TU Braunschweig, Germany.
    Haas, Andreas
    TU Braunschweig, Germany.
    Hemmer, Michael
    TU Braunschweig, Germany.
    Hoffmann, Michael
    Swiss Federal Institute Technology, Switzerland.
    Kostitsyna, Irina
    TU Eindhoven, Netherlands.
    Krupke, Dominik
    TU Braunschweig, Germany.
    Maurer, Florian
    TU Braunschweig, Germany.
    Mitchell, Joseph S. B.
    SUNY Stony Brook, NY 11794 USA.
    Schmidt, Arne
    TU Braunschweig, Germany.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Troegel, Julian
    TU Braunschweig, Germany.
    Computing Nonsimple Polygons of Minimum Perimeter2016Ingår i: EXPERIMENTAL ALGORITHMS, SEA 2016, SPRINGER INT PUBLISHING AG , 2016, Vol. 9685, s. 134-149Konferensbidrag (Refereegranskat)
    Abstract [en]

    We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.

  • 48.
    Andersson Granberg, Tobias
    et al.
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Axelsson, Peter
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Petersson, Jonas
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Tatiana
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Polishchuk, Valentin
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Configuration and Planning of the Remote TowerModules in a Remote Tower Center2016Konferensbidrag (Refereegranskat)
    Abstract [en]

    Today, many small aerodromes struggle withfinancial difficulties, and a large cost is air traffic control.Remote tower centers, which remotely provide air traffic servicesto aerodromes, can help reduce this cost. Each center maycontain a number of remote tower modules, where each moduleis manned by a controller that can handle one or moreaerodromes. In this paper we present the remote tower centerconcept and develop a model that optimizes the assignment ofairports to the remote tower modules. Computational results fora possible scenario based on real data for Swedish airports arepresented.

    Ladda ner fulltext (pdf)
    fulltext
  • 49.
    Burke, Kyle
    et al.
    Plymouth State University, NH, USA.
    Demaine, Erik D.
    Massachusetts Institute of Technology, MA, USA.
    Gregg, Harrison
    Bard Coll Simons Rock, MA, USA.
    Hearn, Robert A.
    Portola Valley, CA USA.
    Hesterberg, Adam
    Massachusetts Institute of Technology, MA, USA.
    Hoffmann, Michael
    Swiss Federal Institute Technology, Switzerland.
    Ito, Hiro
    The University of Electro-Communications, Chofu, Japan.
    Kostitsyna, Irina
    University of Iibre Bruxelles, Belgium.
    Leonard, Jody
    Bard Coll Simons Rock, MA, USA.
    Loeffler, Maarten
    University of Utrecht, Netherlands.
    Santiago, Aaron
    Bard Coll Simons Rock, MA, USA.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. University of Elect Communicat, Japan.
    Uehara, Ryuhei
    Japan Adv Institute Science and Technology, Japan.
    Uno, Yushi
    Osaka Prefecture University, Japan.
    Williams, Aaron
    Bard Coll Simons Rock, MA, USA.
    Single-Player and Two-Player Buttons & Scissors Games2016Ingår i: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 / [ed] Akiyama, J., Ito, H., Sakai, T., Uno, Y., SPRINGER INT PUBLISHING AG , 2016, Vol. 9943, s. 60-72Konferensbidrag (Refereegranskat)
    Abstract [en]

    We study the computational complexity of the Buttons amp; Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C = 2 colors but polytime solvable for C = 1. Similarly the game is NP-complete if every color is used by at most F = 4 buttons but polytime solvable for F amp;lt;= 3. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.

  • 50.
    Friedrichs, Stephan
    et al.
    Max Planck Institute for Informatics, Germany; Saarbrucken Graduate School of Computer Science, Germany.
    Hemmer, Michael
    TU Braunschweig, IBR, Algorithms Group, Braunschweig, Germany.
    King, James
    D-Wave Systems, Burnaby, Canada.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS2016Ingår i: Journal of Computational Geometry, E-ISSN 1920-180X, Vol. 7, nr 1, s. 256-284Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an xx-monotone chain of line segments in R2 (the terrain TT), and ask for the minimum number of guards (located anywhere on TT) required to guard all of TT. We construct guard candidate and witness sets G,W⊂T of polynomial size such that any feasible (optimal) guard cover G∗⊆Gfor WW is also feasible (optimal) for the continuous TGP. This discretization allows us to: (1) settle NP-completeness for the continuous TGP; (2) provide a Polynomial Time Approximation Scheme (PTAS) for the continuous TGP using the PTAS for the discrete TGP by Gibson et al.; (3) formulate the continuous TGP as an Integer Linear Program (IP). Furthermore, we propose several filtering techniques reducing the size of our discretization, allowing us to devise an efficient IP-based algorithm that reliably provides optimal guard placements for terrains with up to 10^6 vertices within minutes on a standard desktop computer.

    Ladda ner fulltext (pdf)
    fulltext
12 1 - 50 av 51
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf