The ever-growing air traffic demand arouses an urgent need for improved airport ground movement efficiency. New operational concepts are emerging which use time-based taxi trajectories to reduce uncertainty and make more efficient use of the airport resource. In this study, an improved approach is proposed for time-based taxi trajectory planning, which is formulated as the shortest path problem with time windows and the maximum traversal time constraint. With the introduction of the taxi time in the cost and the maximum traversal time constraint to limit the waiting time, more efficient and fluent ground movement of aircraft can be realised. An A*-based solution algorithm is developed for the investigated problem, which utilises the arrival time interval and dominance-based comparison to search for the best solution. Experimental results on real-world problem instances demonstrate the effectiveness of the proposed approach as well as its advantages over the existing approach.

References

1. 1)
  - 20. Stahlbock, R., Voβ, S.: ‘Vehicle routing problems and container terminal operations–an update of research’, in Golden, B.L., Raghavan, S., Wasil, E. A. (Eds): ‘The vehicle routing problem: latest advances and new challenges’ (Springer, Boston, MA, USA, 2008), pp. 551–589.
2. 2)
  - 12. Zhang, T., Ding, M., Wang, B., et al: ‘Conflict-free time-based trajectory planning for aircraft taxi automation with refined taxiway modeling’, J. Adv. Transp., 2016, 50, (3), pp. 326–347.
3. 3)
  - 1. Eurocontrol: ‘Challenges of growth 2013: the effect of air traffic network congestion in 2035’ (Eurocontrol, Brussels, Belgium, 2013).
4. 4)
  - 31. Cheng, V., Sweriduk, G.D.: ‘Trajectory design for aircraft taxi automation to benefit trajectory-based operations’. Proc. of the 7th Asian Control Conf., Hong Kong, China, 2009.
5. 5)
  - 6. Foyle, D.C., Hooey, B.L., Bakowski, D.L., et al: ‘Flight deck surface trajectory-based operations (STBO): simulation results and ConOps implications’. Proc. of the Ninth USA/Europe Air Traffic Management Research and Development Seminar (ATM2011), Berlin, Germany, 2011.
6. 6)
  - 11. Ravizza, S., Atkin, J.A., Burke, E.K.: ‘A more realistic approach for airport ground movement optimisation with stand holding’, J. Sched., 2014, 17, (5), pp. 507–520.
7. 7)
  - 26. Okuniek, N., Sparenberg, L.: ‘Opportunities and challenges when implementing trajectory-based taxi operations at European and U.S. CDM airports’. 2017 IEEE/AIAA 36th Digital Avionics Systems Conf. (DASC), St. Petersburg, FL, USA, 2017.
8. 8)
  - 29. Mori, R.: ‘Optimal pushback time with existing uncertainties at busy airport’. Proc. of 29th Congress of the ICAS, St. Petersburg, 2014.
9. 9)
  - 2. Weiszer, M., Chen, J., Stewart, P.: ‘A real-time active routing approach via a database for airport surface movement’, Transp. Res. C, Emerg. Technol., 2015, 58, pp. 127–145.
10. 10)
  - 28. Gerdes, I., Schaper, M.: ‘Management of time based taxi trajectories coupling departure and surface management systems’. 11th ATM Seminar, Lisbon, Portugal, 2015.
11. 11)
  - 30. Mori, R.: ‘Development of a pushback time assignment algorithm considering uncertainty’, J. Air Transp., 2017, 25, (2), pp. 51–60.
12. 12)
  - 23. Hart, P.E., Nilsson, N.J., Raphael, B.: ‘A formal basis for the heuristic determination of minimum cost paths’, IEEE Trans. Syst. Sci. Cybern., 1968, 4, (2), pp. 100–107.
13. 13)
  - 14. Pugliese, L.D.P., Guerriero, F.: ‘A survey of resource constrained shortest path problems: exact solution approaches’, Networks, 2013, 62, (3), pp. 183–200.
14. 14)
  - 32. Chen, J., Weiszer, M., Stewart, P., et al: ‘Toward a more realistic, cost effective and greener ground movement through active routing: part 1-optimal speed profile generation’, IEEE Trans. Intell. Transp. Syst., 2016, 17, (5), pp. 1196–1209.
15. 15)
  - 18. Olmi, R.: ‘Traffic management of automated guided vehicles in flexible manufacturing systems’ (Università degli Studi di Ferrara, Ferrara, Italy, 2011).
16. 16)
  - 22. ter Mors, A., Witteveen, C., Zutt, J., et al: ‘Context-aware route planning’, in Dix, J., Witteveen, C. (Eds): ‘Multiagent system technologies’ (Springer, Berlin Heidelberg, 2010), pp. 138–149.
17. 17)
  - 15. Desaulniers, G., Villeneuve, D.: ‘The shortest path problem with time windows and linear waiting costs’, Transp. Sci., 2000, 34, (3), pp. 312–319.
18. 18)
  - 25. Atkin, J.D., Burke, E., Greenwood, J.: ‘TSAT allocation at London heathrow: the relationship between slot compliance, throughput and equity’, Public Transp., 2010, 2, (3), pp. 173–198.
19. 19)
  - 9. Marín, Á.G.: ‘Airport management: taxi planning’, Ann. Oper. Res., 2006, 143, (1), pp. 191–202.
20. 20)
  - 4. Okuniek, J.N., Gerdes, I., Jakobi, J., et al: ‘A concept of operations for trajectory-based taxi operations’. 16th AIAA Aviation Technology, Integration, and Operations Conf., Washington, DC, USA, 2016.
21. 21)
  - 17. Ioachim, I., Gelinas, S., Soumis, F., et al: ‘A dynamic programming algorithm for the shortest path problem with time windows and linear node costs’, Networks, 1998, 31, (3), pp. 193–204.
22. 22)
  - 7. Weiszer, M., Chen, J., Locatelli, G.: ‘An integrated optimisation approach to airport ground operations to foster sustainability in the aviation sector’, Appl. Energy, 2015, 157, pp. 567–582.
23. 23)
  - 24. Chen, J., Weiszer, M., Locatelli, G., et al: ‘Toward a more realistic, cost effective and greener ground movement through active routing: a multi-objective shortest path approach’, IEEE Trans. Intell. Transp. Syst., 2016, 17, (12), pp. 3524–3540.
24. 24)
  - 19. Fanti, M.P.: ‘Event-based controller to avoid deadlock and collisions in zone-control AGVS’, Int. J. Prod. Res., 2002, 40, (6), pp. 1453–1478.
25. 25)
  - 21. Smolic-Rocak, N., Bogdan, S., Kovacic, Z., et al: ‘Time windows based dynamic routing in multi-AGV systems’, IEEE Trans. Autom. Sci. Eng., 2010, 7, (1), pp. 151–155.
26. 26)
  - 8. Clare, G.L., Richards, A.G.: ‘Optimization of taxiway routing and runway scheduling’, IEEE Trans. Intell. Transp. Syst., 2011, 12, (4), pp. 1000–1013.
27. 27)
  - 27. Benlic, U., Brownlee, A.E., Burke, E.K.: ‘Heuristic search for the coupled runway sequencing and taxiway routing problem’, Transp. Res. C, Emerg. Technol., 2016, 71, pp. 333–355.
28. 28)
  - 3. ICAO: ‘Advanced surface movement guidance and control systems (A-SMGCS) manual’ (International Civil Aviation Organization, Montreal, Canada, 2004).
29. 29)
  - 5. Hooey, B.L., Cheng, V.H., Foyle, D.C.: ‘A concept of operations for far-term surface trajectory-based operations (STBO)’, 2014.
30. 30)
  - 13. Nikoleris, T., Gupta, G., Kistler, M.: ‘Detailed estimation of fuel consumption and emissions during aircraft taxi operations at Dallas/Fort Worth International Airport’, Transp. Res. D, Transp. Environ., 2011, 16, (4), pp. 302–308.
31. 31)
  - 10. Lesire, C.: ‘Iterative planning of airport ground movements’. Proc. of the 4th Int. Conf. on Research in Air Transportation (ICRAT 2010), Budapest, Hungary, 2010.
32. 32)
  - 16. Solomon, M.M., Desrosiers, J.: ‘Survey paper–time window constrained routing and scheduling problems’, Transp. Sci., 1988, 22, (1), pp. 1–13.

Improved approach for time-based taxi trajectory planning towards conflict-free, efficient and fluent airport ground movement

References

Related content