Parallel parametric combinatorial search : its application to runway scheduling
Cover title
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Technical Report |
| Published: |
Cambridge, Mass. : Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, Flight Transportation Laboratory, [1987]
2012
|
| Online Access: | http://hdl.handle.net/1721.1/68055 |
| _version_ | 1811095500807471104 |
|---|---|
| author | Trivizas, Dionyssios Anastasios |
| author2 | Massachusetts Institute of Technology. Flight Transportation Laboratory |
| author_facet | Massachusetts Institute of Technology. Flight Transportation Laboratory Trivizas, Dionyssios Anastasios |
| author_sort | Trivizas, Dionyssios Anastasios |
| collection | MIT |
| description | Cover title |
| first_indexed | 2024-09-23T16:17:45Z |
| format | Technical Report |
| id | mit-1721.1/68055 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:17:45Z |
| publishDate | 2012 |
| publisher | Cambridge, Mass. : Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, Flight Transportation Laboratory, [1987] |
| record_format | dspace |
| spelling | mit-1721.1/680552019-04-10T10:00:36Z Parallel parametric combinatorial search : its application to runway scheduling Parametric combinatorial search, parallel : its application to runway scheduling Trivizas, Dionyssios Anastasios Massachusetts Institute of Technology. Flight Transportation Laboratory Cover title February 1987 Also issued as a Ph. D. thesis, Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 1987 Includes bibliographical references (p. 167-171) The Runway Scheduling Problem (RSP) addresses the fundamental issues of airport congestion and energy conservation. It is a variation of the Traveling Salesman Problem (TSP) from which it differs in three basic points: the maximum position shift (MPS) constraints, the requirement to enforce the triangular in its cost structure and the multiplicity of runways (corresponding to multiple salesmen in TSP). The RSP is dynamic, requiring fast and frequent schedule updates. The MPS constraints, designed to prevent inequitable treatment of aircraft, define a combinatorial neighborhood of tours around a base tour, determined by the arrival sequence of aircraft in RSP. The neighborhood contains all tours in which the position of an object (aircraft, city etc.) in the new tour is within MPS positions of its position in the base tour. The parameter MPS controls the radius of the neighborhood, which covers the full solution space when MPS equals half the number of aircraft. We first describe the RSP and then develop a parallel processor (PPMPS) that finds the optimal solution in the MPS-neighborhood in time linear to the number of objects, using up to 4MPS processors in parallel. Subsequently, PPM'S is applied to the general RSP and a case study is presented to justify simplifying assumptions in the scheduling of mixed traffic on multiple runways. The case study shows substantial improvements in the capacity of a system of three runways. Suggestions are made on how to use the PPMPS to create fast heuristic procedures for the TSP, based on divide and conquer and node insertion strategies. Supported, in part, by grants from the FAA. 2012-01-06T22:04:38Z 2012-01-06T22:04:38Z 1987 Technical Report 18486422 http://hdl.handle.net/1721.1/68055 FTL report (Massachusetts Institute of Technology. Flight Transportation Laboratory) ; R87-4 171 p application/pdf Cambridge, Mass. : Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, Flight Transportation Laboratory, [1987] |
| spellingShingle | Trivizas, Dionyssios Anastasios Parallel parametric combinatorial search : its application to runway scheduling |
| title | Parallel parametric combinatorial search : its application to runway scheduling |
| title_full | Parallel parametric combinatorial search : its application to runway scheduling |
| title_fullStr | Parallel parametric combinatorial search : its application to runway scheduling |
| title_full_unstemmed | Parallel parametric combinatorial search : its application to runway scheduling |
| title_short | Parallel parametric combinatorial search : its application to runway scheduling |
| title_sort | parallel parametric combinatorial search its application to runway scheduling |
| url | http://hdl.handle.net/1721.1/68055 |
| work_keys_str_mv | AT trivizasdionyssiosanastasios parallelparametriccombinatorialsearchitsapplicationtorunwayscheduling AT trivizasdionyssiosanastasios parametriccombinatorialsearchparallelitsapplicationtorunwayscheduling |