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

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها

موضوعات


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