مساله تسریع در کوتاهترین مسیرهای متغیر زمانی با زمانهای انتظار دلخواه

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشیار، گروه ریاضی، دانشکده علوم پایه، دانشگاه قم، قم، ایران.

2 دکترا، ریاضی کاربردی، دانشکده علوم پایه، دانشگاه قم، قم، ایران.

چکیده

مسائل شبکه جریان، شاخه حیاتی در تحقیق در عملیات هستند. این مسائل به حالتهای متغیر زمانی و ایستا طبقه‌بندی می‌گردند. مسائل شبکه جریان در کاربردهای واقعی، متغیر زمانی هستند، زیرا هر جریان برای عبور از یک کمان باید یک مقدار زمان داده شده را اتخاذ کند، همچنین همه پارامترها در شبکه می توانند به جریان وابسته باشد. در این مقاله، مساله تسریع روی کوتاهترین مسیر متغیر زمانی مطالعه می گردد. در ابتدا، ما کوتاهترین مسیر متغیر زمانی را توضیح می‌دهیم. این مساله یافتن مسیرهایی از یک راس مشخص شده (که مبدا نامیده می شود) به سایر رئوس است به‌طوریکه هزینه این مسیر کمترین گردد و مجموع زمان‌های عبور و زمان‌های انتظار حداکثر T شود، که T یک عدد صحیح مثبت داده شده است. سپس مساله تسریع برای یک مساله کوتاهترین مسیر شرح داده شده است.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Speed-up Technique in Time-Varying Shortest Path Problems with Arbitrary Waiting Times

نویسندگان [English]

  • Gholamhasan Shirdel 1
  • Hasan Rezapour 2
1 Associate Prof., Department of Mathematics, Faculty of Basic Sciences, University of Qom, Qom, Iran.
2 Ph.D, Applied Mathematics, Faculty of Basic Sciences, University of Qom, Qom, Iran.
چکیده [English]

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.

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

  • Speed-Up Techniques
  • Time-Varying Shortest Path
CAPTCHA Image