Upgrading arcs to minimize the maximum travel time in a network

Upgrading arcs to minimize the maximum travel time in a network

0.00 Avg rating0 Votes
Article ID: iaor2007378
Country: United States
Volume: 47
Issue: 2
Start Page Number: 72
End Page Number: 80
Publication Date: Mar 2006
Journal: Networks
Authors: , ,
Keywords: programming: dynamic, heuristics, graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.