Article
A Hierarchical Market Solution to the Min–Max Multiple Depots Vehicle Routing Problem Open Access Deposited
The problem of assigning a group of Unmanned Aerial Vehicles (UAVs) to perform spatially distributed tasks often requires that the tasks will be performed as quickly as possible. This problem can be defined as the Min–Max Multiple Depots Vehicle Routing Problem (MMMDVRP), which is a benchmark combinatorial optimization problem. In this problem, UAVs are assigned to service tasks so that each task is serviced once and the goal is to minimize the longest tour performed by any UAV in its motion from its initial location (depot) to the tasks and back to the depot. This problem arises in many time-critical applications, e.g. mobile targets assigned to UAVs in a military context, wildfire fighting, and disaster relief efforts in civilian applications. In this work, we formulate the problem using Mixed Integer Linear Programming (MILP) and Binary Programming and show the scalability limitation of these formulations. To improve scalability, we propose a hierarchical market-based solution (MBS). Simulation results demonstrate the ability of the MBS to solve large scale problems and obtain better costs compared with other known heuristic solution.
- Creator
- License
- Submitter
- College
- Department
- Date Created
- Language
- Note
This work was part of a pilot "mediated-deposit model" where library staff found potential works, later submitted for faculty review
Digital Object Identifier (DOI)
Identifier: 10.1142/S230138501450006X
Link: https://doi.org/10.1142/S230138501450006X
This DOI link is the best way for others to cite your work.
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
|
A_Hierarchical_Market_Solution_to_the_Min-Max_Multiple_Depots_Vehicle_Routing_Problem.pdf | 2017-02-03 | Open Access |
|
Permanent link to this page: https://scholar.uc.edu/show/bc386s72j