Stochastic Task Scheduling in UAV-Based Intelligent On-Demand Meal Delivery System

被引:30
作者
Huang, Haiping [1 ]
Hu, Chengxi [1 ]
Zhu, Jie [2 ]
Wu, Min [1 ]
Malekian, Reza [3 ]
机构
[1] Nanjing Univ Posts & Telecommun, Jiangsu High Technol Res Key Lab Wireless Sensor, Nanjing 210013, Peoples R China
[2] Nanjing Univ Posts & Telecommun, Sch Comp Sci, Nanjing 210013, Peoples R China
[3] Malmo Univ, Dept Comp Sci & Media Technol, S-20506 Malmo, Sweden
基金
中国国家自然科学基金; 美国国家科学基金会;
关键词
Task analysis; Heuristic algorithms; Routing; Costs; Vehicle dynamics; Stochastic processes; Logistics; UAV; stochastic task scheduling; O2O on-demand meal delivery; simulated annealing; rescheduling strategy; VEHICLE-ROUTING PROBLEM; SEARCH ALGORITHM; ENERGY; DRONES; MODEL;
D O I
10.1109/TITS.2021.3119343
中图分类号
TU [建筑科学];
学科分类号
0813 ;
摘要
In this paper, we investigate the dynamic task scheduling problem with stochastic task arrival times and due dates in the UAV-based intelligent on-demand meal delivery system (UIOMDS) to improve the efficiency. The objective is to minimize the total tardiness. The new constraints and characteristics introduced by UAVs in the problem model are fully studied. An iterated heuristic framework SES (Stochastic Event Scheduling) is proposed to periodically schedule tasks, which consists of a task collection and a dynamic task scheduling phases. Two task collection strategies are introduced and three Roulette-based flight dispatching approaches are employed. A simulated annealing based local search method is integrated to optimize the solutions. The experimental results show that the proposed algorithm is robust and more effective compared with other two existing algorithms.
引用
收藏
页码:13040 / 13054
页数:15
相关论文
共 36 条
  • [1] A Distributed Cluster-Based Approach for Pick-Up Services
    Abbatecola, Lorenzo
    Fanti, Maria Pia
    Pedroncelli, Giovanni
    Ukovich, Walter
    [J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2019, 16 (02) : 960 - 971
  • [2] Vehicle routing problem in omni-channel retailing distribution systems
    Abdulkader, M. M. S.
    Gajpal, Yuvraj
    ElMekkawy, Tarek Y.
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2018, 196 : 43 - 55
  • [3] Optimization Approaches for the Traveling Salesman Problem with Drone
    Agatz, Niels
    Bouman, Paul
    Schmidt, Marie
    [J]. TRANSPORTATION SCIENCE, 2018, 52 (04) : 965 - 981
  • [4] A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption: A case study
    Alinaghian, Mehdi
    Naderipour, Mansoureh
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2016, 99 : 210 - 222
  • [5] Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows
    Brandao, Jose
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 120 : 146 - 159
  • [6] Trajectory Optimization for High-Altitude Long-Endurance UAV Maritime Radar Surveillance
    Brown, Angus
    Anderson, David
    [J]. IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS, 2020, 56 (03) : 2406 - 2421
  • [7] Modeling a green inventory routing problem with a heterogeneous fleet
    Cheng, Chun
    Yang, Peng
    Qi, Mingyao
    Rousseau, Louis-Martin
    [J]. TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2017, 97 : 97 - 112
  • [8] THE TRUCK DISPATCHING PROBLEM
    DANTZIG, GB
    RAMSER, JH
    [J]. MANAGEMENT SCIENCE, 1959, 6 (01) : 80 - 91
  • [9] Vehicle Routing Problems for Drone Delivery
    Dorling, Kevin
    Heinrichs, Jordan
    Messier, Geoffrey G.
    Magierowski, Sebastian
    [J]. IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2017, 47 (01): : 70 - 85
  • [10] Joint Resources and Workflow Scheduling in UAV-Enabled Wirelessly-Powered MEC for IoT Systems
    Du, Yao
    Yang, Kun
    Wang, Kezhi
    Zhang, Guopeng
    Zhao, Yizhe
    Chen, Dongwei
    [J]. IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, 2019, 68 (10) : 10187 - 10200