IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v90y2016icp38-55.html
   My bibliography  Save this article

The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

Author

Listed:
  • Furini, Fabio
  • Persiani, Carlo Alfredo
  • Toth, Paolo

Abstract

The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.

Suggested Citation

  • Furini, Fabio & Persiani, Carlo Alfredo & Toth, Paolo, 2016. "The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 38-55.
    • Handle: RePEc:eee:transb:v:90:y:2016:i:c:p:38-55
    DOI: 10.1016/j.trb.2016.04.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261516302041
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2016.04.009?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gouveia, Luis & Vo[ss], Stefan, 1995. "A classification of formulations for the (time-dependent) traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 69-82, May.
    2. Albiach, José & Sanchis, José Marí­a & Soler, David, 2008. "An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation," European Journal of Operational Research, Elsevier, vol. 189(3), pages 789-802, September.
    3. Franceschetti, Anna & Honhon, Dorothée & Van Woensel, Tom & Bektaş, Tolga & Laporte, Gilbert, 2013. "The time-dependent pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 265-293.
    4. Jean-Claude Picard & Maurice Queyranne, 1978. "The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research, INFORMS, vol. 26(1), pages 86-110, February.
    5. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.
    6. Sánchez-Díaz, Iván & Holguín-Veras, José & Ban, Xuegang (Jeff), 2015. "A time-dependent freight tour synthesis model," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 144-168.
    7. Lam, William H.K. & Li, Zhi-Chun & Huang, Hai-Jun & Wong, S.C., 2006. "Modeling time-dependent travel choice problems in road networks with multiple user classes and multiple parking facilities," Transportation Research Part B: Methodological, Elsevier, vol. 40(5), pages 368-395, June.
    8. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    9. Beasley, JE, 1981. "Adapting the savings algorithm for varying inter-customer travel times," Omega, Elsevier, vol. 9(6), pages 658-659.
    10. Chen, Huey-Kuo & Hsueh, Che-Fu & Chang, Mei-Shiang, 2006. "The real-time time-dependent vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 42(5), pages 383-408, September.
    11. Matteo Fischetti & Paolo Toth, 1997. "A Polyhedral Approach to the Asymmetric Traveling Salesman Problem," Management Science, INFORMS, vol. 43(11), pages 1520-1536, November.
    12. Bernhard Fleischmann & Martin Gietz & Stefan Gnutzmann, 2004. "Time-Varying Travel Times in Vehicle Routing," Transportation Science, INFORMS, vol. 38(2), pages 160-173, May.
    13. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhu, Xiaoning & Yan, Rui & Peng, Rui & Zhang, Zhongxin, 2020. "Optimal routing, loading and aborting of UAVs executing both visiting tasks and transportation tasks," Reliability Engineering and System Safety, Elsevier, vol. 204(C).
    2. Maskooki, Alaleh & Kallio, Markku, 2023. "A bi-criteria moving-target travelling salesman problem under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 271-285.
    3. Kaiping Wang & Mingzhu Song & Meng Li, 2021. "Cooperative Multi-UAV Conflict Avoidance Planning in a Complex Urban Environment," Sustainability, MDPI, vol. 13(12), pages 1-21, June.
    4. Ming Liu & Xin Liu & Maoran Zhu & Feifeng Zheng, 2019. "Stochastic Drone Fleet Deployment and Planning Problem Considering Multiple-Type Delivery Service," Sustainability, MDPI, vol. 11(14), pages 1-18, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    2. Xiao, Yiyong & Konak, Abdullah, 2016. "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 146-166.
    3. Anke Stieber & Armin Fügenschuh, 2022. "Dealing with time in the multiple traveling salespersons problem with moving targets," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(3), pages 991-1017, September.
    4. Kinable, Joris & Cire, Andre A. & van Hoeve, Willem-Jan, 2017. "Hybrid optimization methods for time-dependent sequencing problems," European Journal of Operational Research, Elsevier, vol. 259(3), pages 887-897.
    5. Albiach, José & Sanchis, José Marí­a & Soler, David, 2008. "An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation," European Journal of Operational Research, Elsevier, vol. 189(3), pages 789-802, September.
    6. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    7. Huang, Yixiao & Zhao, Lei & Van Woensel, Tom & Gross, Jean-Philippe, 2017. "Time-dependent vehicle routing problem with path flexibility," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 169-195.
    8. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    9. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    10. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    11. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    12. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    13. Maskooki, Alaleh & Kallio, Markku, 2023. "A bi-criteria moving-target travelling salesman problem under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 271-285.
    14. Tao Zhang & W. Art Chaovalitwongse & Yuejie Zhang, 2014. "Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 288-309, July.
    15. Cacchiani, Valentina & Contreras-Bolton, Carlos & Toth, Paolo, 2020. "Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times," European Journal of Operational Research, Elsevier, vol. 283(3), pages 825-843.
    16. Rifki, Omar & Chiabaut, Nicolas & Solnon, Christine, 2020. "On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    17. Lecluyse, Christophe & Sörensen, Kenneth & Peremans, Herbert, 2013. "A network-consistent time-dependent travel time layer for routing optimization problems," European Journal of Operational Research, Elsevier, vol. 226(3), pages 395-413.
    18. Fontaine, Romain & Dibangoye, Jilles & Solnon, Christine, 2023. "Exact and anytime approach for solving the time dependent traveling salesman problem with time windows," European Journal of Operational Research, Elsevier, vol. 311(3), pages 833-844.
    19. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    20. Daqing Wu & Chenxiang Wu, 2022. "Research on the Time-Dependent Split Delivery Green Vehicle Routing Problem for Fresh Agricultural Products with Multiple Time Windows," Agriculture, MDPI, vol. 12(6), pages 1-28, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:90:y:2016:i:c:p:38-55. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.