Minimum Spanning Tree concept development to the case of loaded networks and its application in transportation analysi

Authors
A. R. Mamdoohi 1
A. Mahpour 2
M. Yousefikia
1 Tarbiat Modares University
2 Shahid Beheshti University
Abstract
Minimum Spanning Tree (MST) is a mathematical programming problem that may be applied for analyzing transportation network structure and its performance, like its connectivity and link prioritization. Generally, the cost associated with each link is its Free Flow Travel Time (FFTT), however in this paper this concept is developed to the case of a loaded network with capacity constraints and its application to transportation network planning is examined for times of disaster, when the life of many people is involved. In this paper equilibrium travel time for a loaded network is proposed as the link cost and the problem is formulated and solved for Tehran province network. Results show that based on equilibrium travel times, the total cost of MST will have an 8 percent increase from 25973 to 28081 seconds and about 30 percent of the links in the new MST will change. It is also observed that if the MST based on FFTT is used for computing the total cost of the loaded network, the total cost will be 30232 seconds which demonstrates 17 percent increase in cost and 9 percent in error.

Keywords

Subjects

[1]    S Pettie, "On the Shortest Path and Minimum Spanning tree problems", PhD thesis, department of computer science, The University of Texas at Austin, 2003.
[2]    S Chung and A Condon, “Parallel implementation of Boruvka’s minimum spanning tree algorithm”, Computer sciences department, University of Wisconsin, IEEE Journal, 2003, Vol. 7, No 1.
[3]    T M Murali, “Applications of minimum spanning trees”, Science press, 2009, In Proc, 39th Annual IEEE Symposia.
[4]    S P Bradley, A C Hax and T L Magnanti, Applied mathematical programming, Addison Wesley, 1977.
[5]    D Eppstein, “Dynamic euclidean minimum spanning trees and extreme of binary functions”, Department of information and computer science, University of California, Irvine, 2009, Tech. Rep. 92-88, ICS, UCI.
  [6  پیش بینی تقاضای مسافری، مطالعات جامع حمل و نقل کشور، فاز سوم، گزارش جلد 3، وزارت راه و ترابری، 1373 ،تهران.
[7]    C Feremans, M Labbe and G Laporte , “The generalized minimum spanning tree problem: polyhedral analysis and branch-and-cut algorithm”, Networks, 2004, Vol.43, 71-86.
[8]    J A Fill and J M Steele, “Exact expectations of minimal spanning trees for graphs with random edge weights”, 2004, Acheson University.
[8]    A Kanafani, Transportation demand analysis, First Edition, McGraw Hill, New York, 1983.
[9]    J D Ortuzar and L G Willumsen, Modeling transport, Third Edition, John Wiley and Sons, 2004.
[10]    M Patrikson, “The traffic assignment problems- models and methods”, Linkopring Institute of technology, Linkoping, Sweden., 2003.
[11]    Y Sheffi, Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice-Hall, New Jersey, 1985.
Modares Civil Engineering journal
Volume 12, Issue 2
May and June 2012
Pages 61-69