Title :
A Tree Pruning Algorithm for the Capacitated p-hub Median Problems
Author :
Wei, Ge ; Jinfu, Zhu ; Weiwei, Wu
Author_Institution :
Coll. of Civil Aviation, Nanjing Univ. of Aeronaut. & Astronaut., Nanjing, China
Abstract :
Because of the constraint conditions of hub capacity and the large number of the hub combinations, the capacitated p-hub median problems are complicated. This paper presented a tree pruning algorithm to obtain the optimal solution in a local range. The algorithm was combined with Lagrangian relaxation method and applied to the air transportation system using data on passenger flows between the top 20 Chinese cities. Calculating results suggest that this algorithm is effective to reduce the complexity of the capacitated p-hub median problems.
Keywords :
relaxation theory; transportation; trees (mathematics); Lagrangian relaxation method; air transportation system; capacitated p-hub median problems; tree pruning algorithm; Airports; Algorithm design and analysis; Atmospheric modeling; Cities and towns; Complexity theory; Europe; Resource management; Lagrangian relaxation algorithm; network flow; p-hub median problem; tree pruning algorithm;
Conference_Titel :
Information Engineering (ICIE), 2010 WASE International Conference on
Conference_Location :
Beidaihe, Hebei
Print_ISBN :
978-1-4244-7506-3
Electronic_ISBN :
978-1-4244-7507-0
DOI :
10.1109/ICIE.2010.254
