دانشگاه قم مدیریت مهندسی و رایانش نرم 2538-2675 3 2 2018 02 20 Speed-up Technique in Time-Varying Shortest Path Problems with Arbitrary Waiting Times مساله تسریع در کوتاهترین مسیرهای متغیر زمانی با زمانهای انتظار دلخواه 9 20 1068 10.22091/jemsc.2018.1688.1049 FA غلام حسن شیردل دانشیار، گروه ریاضی، دانشکده علوم پایه، دانشگاه قم، قم، ایران. حسن رضاپور دکترا، ریاضی کاربردی، دانشکده علوم پایه، دانشگاه قم، قم، ایران. Journal Article 2017 01 04 Network flow problems are considered a vital branch of operations research. These problems are classified into static and time-varying classes. Network flow problems are time-varying in real application, because any flow must take a given amount of time to traverse an arc. Moreover, all the parameters in the network can be time-dependent. In this paper, the speed-up technique on time-varying shortest path problems is studied. First of all, the time-varying shortest path problem is explained. The problem is to find the shortest paths from a specific vertex (which is called a source) to other vertices, so that the total cost of the path is minimized and the total travel times and waiting times reach a maximum value of T, where T is a given positive integer. Then the speed-up technique is explained for a shortest path problem. مسائل شبکه جریان، شاخه حیاتی در تحقیق در عملیات هستند. این مسائل به حالتهای متغیر زمانی و ایستا طبقه‌بندی می‌گردند. مسائل شبکه جریان در کاربردهای واقعی، متغیر زمانی هستند، زیرا هر جریان برای عبور از یک کمان باید یک مقدار زمان داده شده را اتخاذ کند، همچنین همه پارامترها در شبکه می توانند به جریان وابسته باشد. در این مقاله، مساله تسریع روی کوتاهترین مسیر متغیر زمانی مطالعه می گردد. در ابتدا، ما کوتاهترین مسیر متغیر زمانی را توضیح می‌دهیم. این مساله یافتن مسیرهایی از یک راس مشخص شده (که مبدا نامیده می شود) به سایر رئوس است به‌طوریکه هزینه این مسیر کمترین گردد و مجموع زمان‌های عبور و زمان‌های انتظار حداکثر T شود، که T یک عدد صحیح مثبت داده شده است. سپس مساله تسریع برای یک مساله کوتاهترین مسیر شرح داده شده است. http://jemsc.qom.ac.ir/article_1068_0383523408bd8113d827c73090ee8b64.pdf