تعميم روش فرانك - ولف براي حل مساله تخصيص همگاني با محدوديت ظرفيت ناوگان

xtending the FW Method to Solve Transit Assignment Problem with Fleet Capacity Constraint

برنامه ريزي سيستم هاي حمل و نقل همگاني شهري نيازمند استفاده از مدل هاي تخصيص همگاني به منظور برآورد توزيع مسافران بين خطوط همگاني است. مسيله روي شبكه اي به نام شبكه همگاني تعريف مي شود كه هر كمان آن داراي يك تابع زمان سفر و يك تابع تواتر است. در شبكه هاي همگاني غيرمتراكم ، كه ظرفيت وسايل نقليه همگاني بي نهايت است، مسيله با در نظرگيري زمان سفر و تواتر ثابت كمان ها به صورت يك مدل بهينه سازي خطي فرمول بندي و با استفاده از روش هاي برنامه ريزي خطي حل مي شود. درشبكه هاي متراكم ، كه ظرفيت (ناوگان) وسايل نقليه همگاني محدود است ، مسيله با در نظرگيري توابع زمان سفر وابسته به جريان و تواتر ثابت كمان هاي شبكه به صورت يك مدل بهينه سازي غيرخطي بر حسب جريان در كمان ها فرمول بندي و روش ميانگين هاي متوالي (MSA) ، به عنوان روشي تقريبي ، براي حل آن پيشنهاد شده است. هدف از اين مقاله تعميم روش فرانك - ولف (FW) براي حل دقيق مسيله تخصيص همگاني با محدوديت ظرفيت ناوگان است. مسيله با در نظرگيري يك تابع زمان سفر وابسته به جريان فرمول بندي و با استفاده از هر دو روش MSA و تعميم FW براي يك شبكه نمونه حل مي شود. نتايج سرعت بسيار بيشتر روش پيشنهادي را در دقت هاي مشابه نشان مي دهند.

Planning for public transportation systems requires solving the transit assignment models in order to determine the distribution pattern of travelers between the transit lines. Transit assignment problem is defined on a transit network which a travel time and a frequency function will be defined for each link. In uncongested transit networks that the capacity of the transit vehicles are infinite, the problem is formulated as a linear programming (LP) model by considering fixed travel time and frequency for links and it is solved by LP algorithms. In congested transit networks that the capacity of the transit vehicles are finite, the problem is written as a non-linear programming model by considering flow dependent travel time and fixed frequency for links which the link flows are its variables. The method of successive average (MSA) as an inexact method is applied to solve this problem. The purpose of this paper is to extend the Frank and Wolfe (FW) method for solving the transit assignment problem with fleet capacity constraint. The problem is formulated with the flow dependent travel times and it is solved by both the MSA and extended FW for a sample test network. The proposed algorithm shows a fast rate of convergence based on the numerical results.