A Hierarchical Market Solution to the Min–Max Multiple Depots Vehicle Routing Problem Open Access Deposited

Downloadable Content

Download PDF
Download Adobe Acrobat Reader
Date Uploaded: 02/03/2017
Date Modified: 04/05/2017

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.

Date Created
  • 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

This DOI link is the best way for others to cite your work.


Permanent link to this page: