Journal article
Upgrading arcs to minimize the maximum travel time in a network
Networks, Vol.47(2), pp.72-80
03/2006
DOI: 10.1002/net.20097
Abstract
In transportation and telecommunication systems, the performance of the underlying network can often be improved by upgrading some of the arcs in the network. If an arc is upgraded, the travel time along this arc is reduced by a discount factor α, 0 ≤ α < 1. With respect to different minimax network objectives, we define a series of problems that involve finding the best q arcs in a network to upgrade. We show that these problems are NP-hard on general graphs, but polynomially solvable on trees. Finally, we compare three heuristic solution approaches for complete graphs based on these polynomial results and find one to far outperform the others
Details
- Title: Subtitle
- Upgrading arcs to minimize the maximum travel time in a network
- Creators
- Ann Melissa Campbell - Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242-1994Timothy J. Lowe - Pennsylvania State UniversityLi Zhang - Citadel
- Resource Type
- Journal article
- Publication Details
- Networks, Vol.47(2), pp.72-80
- Publisher
- Wiley Subscription Services, Inc., A Wiley Company
- DOI
- 10.1002/net.20097
- ISSN
- 0028-3045
- eISSN
- 1097-0037
- Number of pages
- 9
- Language
- English
- Date published
- 03/2006
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380396802771
Metrics
2 Record Views