The hierarchical traveling salesman problem |
| |
Authors: | Kiran Panchamgam Yupei Xiong Bruce Golden Benjamin Dussault Edward Wasil |
| |
Institution: | 1. Oracle Analytical Foundation, Oracle Inc., 10 Van De Graaff Dr, Burlington, MA, USA 2. Mercury Systems Inc., New York, NY, USA 3. Robert H. Smith School of Business, University of Maryland, College Park, MD, USA 4. Department of Mathematics, University of Maryland, College Park, MD, USA 5. Kogod School of Business, American University, Washington, DC, USA
|
| |
Abstract: | The distribution of relief aid is a complex problem where the operations have to be managed efficiently due to limited resources. We present a routing problem for relief operations whose primary goal is to satisfy demand for relief supplies at many locations taking into account the urgency of each demand. We have a single vehicle of unlimited capacity. Each node (location) has a demand and a priority. The priority indicates the urgency of the demand. Typically, nodes with the highest priorities need to be visited before lower priority nodes. We describe a new and interesting model for humanitarian relief routing that we call the hierarchical traveling salesman problem (HTSP). We compare the HTSP and the classical TSP in terms of worst-case behavior. We obtain a simple, but elegant result that exhibits the fundamental tradeoff between efficiency (distance) and priority and we provide several related observations and theorems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|