The traveling salesman problem with release dates and drone resupply
| Autor: | Alice E. Smith, Daniel F. Silva, Juan C. Pina-Pardo |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization 021103 operations research General Computer Science Linear programming Computer science 0211 other engineering and technologies Context (language use) 02 engineering and technology Management Science and Operations Research Travelling salesman problem Drone 020901 industrial engineering & automation Order (business) Modeling and Simulation Decomposition (computer science) |
| Zdroj: | Computers & Operations Research. 129:105170 |
| ISSN: | 0305-0548 |
| Popis: | This paper introduces the Traveling Salesman Problem with Release Dates and Drone Resupply, which consists of finding a minimum time route for a single truck that can receive newly available orders en route via a drone sent from the depot. We assume that each order’s release date is known at the time of delivery planning. This context is common for many applications, notably last-mile logistics. We develop a Mixed-Integer Linear Program and a solution approach for larger instances based on decomposing the problem into the truck-routing and the drone-resupply decisions. Numerical experiments show that using drones for resupply can reduce the total delivery time by up to 20%. Additionally, experiments show that the decomposition can rapidly obtain high-quality solutions. For instances of 10 and 15 customers, the decomposition solved the majority to optimality, with a trivial gap. For larger instances, this approach provided lower delivery times than a traditional parcel delivery system using a truck only. Investigations on the effects of drone speed, drone capacity, depot location, constraint addition, and allowing the truck to return to the depot are studied. We consider instances up to 50 customers. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect