توسعه مفهوم کوتاهترین درخت گسترش به شرایط تحت بار و کاربرد آن در تحلیل شبکه های حمل و نقل

نویسندگان
امیررضا ممدوحی
علیرضا ماهپور
محمد یوسفی کیا
دانشگاه تربیت مدرس
چکیده
از جمله مسایل مهم جریان در شبکه برای تحلیل ساختار و عملکرد آن، مساله کوتاهترین درخت گسترش است. بررسی پیوستگی شبکه در شرایط بحران و اولویت‌بندی کمان‌های شبکه از جمله کاربردهای این مساله است. معیار محاسبه و تعیین کوتاه‌ترین درخت گسترش مفهوم هزینه کمان است که تا به حال در اکثر مطالعات مربوطه از مفهوم زمان سفر آزاد استفاده شده است. در مقاله جاری این مفهوم به حالت عام زمان سفر تحت بار تقاضا و محدودیت ظرفیت توسعه یافته، و کاربرد آن در تحلیل شبکه‌های حمل و نقل در زمان بحران که جان افراد زیادی منوط به امدادرسانی سریع است، بررسی می‌شود. با توجه به ضرورت تعریف و بررسی اثر هزینه‌ای که در شرایط مختلف بتواند هزینه‌ی کل واقعی را نشان دهد، در این مقاله، هزینه‌ی کمان برای محاسبه کوتاهترین درخت گسترش، زمان سفر کمان تحت بار جریان در شبکه تعریف شده و مساله برای مطالعه موردی راه‌های شریانی استان تهران فرمول‌بندی و حل می‌گردد. نتایج نشان می‌دهد که با تعریف هزینه به صورت زمان سفر تعادلی کمان و حل مجدد مساله هزینه‌ی کل شبکه از 25973 به 28081 ثانیه (8 درصد) افزایش و کمان‌های تشکیل دهنده نیز حدود 30 درصد تغییر می‌کنند. در صورت استفاده از کوتاهترین درخت گسترش اولیه (بدون بار) برای مساله تحت بار تقاضا، هزینه‌ی شبکه برابر 30232 ثانیه می‌شود که معادل 17 درصد افزایش در هزینه و 9 درصد خطا است.

کلیدواژه‌ها

موضوعات

عنوان مقاله English

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

نویسندگان English

Amir Reza Mamdoohi
Alireza Mahpour
Mohammad Yousefikia
Tarbiat Modares University
چکیده English

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.

کلیدواژه‌ها English

network analyses
minimum spanning tree
Cost
travel time
Tehran city arterial road network
[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.
مهندسی عمران مدرس
دوره 12، شماره 2
خرداد و تیر 1391
صفحه 61-69