Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones
The employment of drones for the distribution of goods represents a significant avenue for addressing logistical challenges at the end of the supply chain. The truck-drone cooperative delivery model overcomes drone limitations such as limited capacity and endurance and has emerged as a crucial mode...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Hindawi Limited
2023-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2023/1183764 |
| _version_ | 1797733165463240704 |
|---|---|
| author | Yan-Qiu Liu Jing Han Ying Zhang Yan Li Tao Jiang |
| author_facet | Yan-Qiu Liu Jing Han Ying Zhang Yan Li Tao Jiang |
| author_sort | Yan-Qiu Liu |
| collection | DOAJ |
| description | The employment of drones for the distribution of goods represents a significant avenue for addressing logistical challenges at the end of the supply chain. The truck-drone cooperative delivery model overcomes drone limitations such as limited capacity and endurance and has emerged as a crucial mode of drone participation in logistics delivery. This delivery model effectively reduces delivery costs and shortens delivery times. Herein, we examine a variant of the truck-drone routing problem, which encompasses the strategic deployment and routing of multiple fleets of trucks, each equipped with an auxiliary drone. The objective is to fulfill all the pickup and delivery demands of a designated customer base while minimizing the overall route cost. Within this problem domain, drones are authorized to serve multiple customers within their capacity and endurance limits, providing both pickup and delivery services during each trip. However, the utilization of drones for servicing all customers is impeded by the existence of no-fly zones that have been implemented in numerous cities worldwide. These prescribed no-fly zones cause significant challenges when attempting to optimize the routing of truck-drone operations. Thus, this study constructs a mixed integer linear programming (MILP) model for the path optimization problem of joint service of trucks and drones considering no-fly zones and simultaneous pickup and delivery. Given the intricacy of the MILP model, we propose a two-stage heuristic algorithm based on a simulated annealing approach, combined with strategies for rectifying infeasible solutions and expediting algorithmic processes. During the phase of computational experimentation, we explore the advantages derived from enabling drones to serve multiple customers and assess the effectiveness of the proposed model and two-stage heuristic algorithm. Finally, sensitivity analysis is conducted on two key parameters. |
| first_indexed | 2024-03-12T12:25:12Z |
| format | Article |
| id | doaj.art-e5ad0264b4da41ce836b136548b1a670 |
| institution | Directory Open Access Journal |
| issn | 1607-887X |
| language | English |
| last_indexed | 2024-03-12T12:25:12Z |
| publishDate | 2023-01-01 |
| publisher | Hindawi Limited |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj.art-e5ad0264b4da41ce836b136548b1a6702023-08-30T00:00:02ZengHindawi LimitedDiscrete Dynamics in Nature and Society1607-887X2023-01-01202310.1155/2023/1183764Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly ZonesYan-Qiu Liu0Jing Han1Ying Zhang2Yan Li3Tao Jiang4School of ManagementSchool of ManagementSchool of ManagementSchool of Transportation and Logistics EngineeringSchool of ManagementThe employment of drones for the distribution of goods represents a significant avenue for addressing logistical challenges at the end of the supply chain. The truck-drone cooperative delivery model overcomes drone limitations such as limited capacity and endurance and has emerged as a crucial mode of drone participation in logistics delivery. This delivery model effectively reduces delivery costs and shortens delivery times. Herein, we examine a variant of the truck-drone routing problem, which encompasses the strategic deployment and routing of multiple fleets of trucks, each equipped with an auxiliary drone. The objective is to fulfill all the pickup and delivery demands of a designated customer base while minimizing the overall route cost. Within this problem domain, drones are authorized to serve multiple customers within their capacity and endurance limits, providing both pickup and delivery services during each trip. However, the utilization of drones for servicing all customers is impeded by the existence of no-fly zones that have been implemented in numerous cities worldwide. These prescribed no-fly zones cause significant challenges when attempting to optimize the routing of truck-drone operations. Thus, this study constructs a mixed integer linear programming (MILP) model for the path optimization problem of joint service of trucks and drones considering no-fly zones and simultaneous pickup and delivery. Given the intricacy of the MILP model, we propose a two-stage heuristic algorithm based on a simulated annealing approach, combined with strategies for rectifying infeasible solutions and expediting algorithmic processes. During the phase of computational experimentation, we explore the advantages derived from enabling drones to serve multiple customers and assess the effectiveness of the proposed model and two-stage heuristic algorithm. Finally, sensitivity analysis is conducted on two key parameters.http://dx.doi.org/10.1155/2023/1183764 |
| spellingShingle | Yan-Qiu Liu Jing Han Ying Zhang Yan Li Tao Jiang Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones Discrete Dynamics in Nature and Society |
| title | Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones |
| title_full | Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones |
| title_fullStr | Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones |
| title_full_unstemmed | Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones |
| title_short | Multivisit Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery considering No-Fly Zones |
| title_sort | multivisit drone vehicle routing problem with simultaneous pickup and delivery considering no fly zones |
| url | http://dx.doi.org/10.1155/2023/1183764 |
| work_keys_str_mv | AT yanqiuliu multivisitdronevehicleroutingproblemwithsimultaneouspickupanddeliveryconsideringnoflyzones AT jinghan multivisitdronevehicleroutingproblemwithsimultaneouspickupanddeliveryconsideringnoflyzones AT yingzhang multivisitdronevehicleroutingproblemwithsimultaneouspickupanddeliveryconsideringnoflyzones AT yanli multivisitdronevehicleroutingproblemwithsimultaneouspickupanddeliveryconsideringnoflyzones AT taojiang multivisitdronevehicleroutingproblemwithsimultaneouspickupanddeliveryconsideringnoflyzones |