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

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

نویسندگان

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

مراجع

Ahuja, R. K. & Magnanti, T. L. & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. DC: Prentice-Hall, Englewood Cliffs, NJ.
Ford, L. R. & Fulkerson, D. R.  (1958). Constructing maximal dynamic flows from static flows, Operations Research, 6, 419–433.
Aronson, J. (1989). A survey of dynamic network flows. Annals of Operations Research, 20, 1–66.
Hoppe, B. (1995). Efficient Dynamic Network Flow Algorithms. Ph.D. Thesis, Cornell University.
Chabini, L. (1998). Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record, 1645, 170–175.
Glockner, G. & Nemhauser, G. (2000). A dynamic network flow problem with uncertain arc capacities: formulation and problem structure, Operations Research, 48 (2): 33–242.
Salehi Fathabadi, H. & Hosseini, S.A. (2010).  Maximum flow problem on dynamic generateve network flows with time-varying bounds. Applied Mathematical Modeling, 34, 2136–2147.
Orda, A. & Rom, R. (1990). Shortest-path and minimum-delay algorithms in networks with time-dependent edge length. Journal of the Association for Computing, 37, 607–625.
Orda, A. & Rom, R. (1991). Minimum weight paths in time-dependent networks. Networks, 21, 295–320.
Cai, X. & Kloks, T. & Wong, C.k. (1997). Time-varying shortest path problems with constraints. Networks, 29, 141–149.
Cai, X. & Sha, D. & Wong, C. K. (2001). Time-varying minimum cost flow problems. European Journal of Operational Research, 131, 352–374.
Nasrabadi, E. & Hashemi, M. (2010). Minimum cost time-varying network flow problems. Optimization Methods & Software, 25 (3): 429–447.
Shirdel, Gh. & Rezapour, H. (2015). K-Objective Time-Varying Shortest Path Problem with Zero Waiting Times at Vertices. Trends in Applied Sciences Research, 10 (5): 278-285.
Shirdel, Gh. & Rezapour, H.  (2016). the Arbitrary Waiting Times in the Time-Varying Shortest Path with Triangular Fuzzy Costs. Advances and Applications in Mathematical Sciences, 15, (2): 75-85.
Shirdel, Gh. & Rezapour, H. (2016). Time-varying maximum capacity path problem with zero waiting times and fuzzy capacities, SpringerPlus 5, 981-990.
ارسال نظر در مورد این مقاله
CAPTCHA Image

فایل ها

هم رسانی

ارجاع به این مقاله

آمار