کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7539198 1488938 2018 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks
ترجمه فارسی عنوان
الگوریتم هورنفتی برای کمترین زمان سفر زمان سفر در شبکه های وابسته به زمان وقوع و تصادفی
کلمات کلیدی
شبکه وابسته به زمان اتفاقی زمان سفر پویا و تصادفی، زمان سفر کمترین انتظار، هزینه کمترین انتظار، هرس زیر زمینی، توزیع زمان سفر پیوند وابسته،
ترجمه چکیده
در این مطالعه، مسئله تعیین مسیر با کمترین زمان سفر مورد انتظار در شبکه های وابسته به زمان و وابسته است. اصل بهینه بودن بلمن برای این مشکل قابل اجرا نیست - به دلیل عملکرد غیرخطی آن، مشکل حل آن است. در این نور، ما یک الگوریتم مبتنی بر هرس را پیشنهاد می دهیم که به تدریج زیر مسیر ها را از منبع تعیین می کند و موارد غیر مطلوب را حذف می کند. این الگوریتم از یک معیار برش مبتنی بر محدوده دو سطح جدید استفاده می کند تا تعیین کند که آیا زیر قطعه می تواند به مسیر مطلوب تعلق داشته باشد یا خیر. ما نشان می دهیم که معیار هرس معتبر است و الگوریتم با یک راه حل دقیق متوقف می شود. آزمایش های محاسباتی نشان می دهد که الگوریتم می تواند این مشکل را حتی در شبکه های بزرگ دنیای واقعی حل کند و پیچیدگی محاسباتی عملی آن چندجملهای است. در نهایت، ما نشان می دهیم که الگوریتم هرس با فرایند نسبت به اندازه شبکه در شبکه های متوسط ​​متوسط ​​و به همین ترتیب در شبکه های بزرگ بزرگ، فراتر از روند مبتنی بر غلبه موجود عمل می کند. این کار بالقوه برای کمک به استفاده گسترده از شبکه های وابسته به زمان بروز تصادفی برای مدل سازی و تجزیه و تحلیل کمک می کند.
موضوعات مرتبط
علوم انسانی و اجتماعی علوم تصمیم گیری علوم مدیریت و مطالعات اجرایی
پیش نمایش مقاله
الگوریتم هورنفتی برای کمترین زمان سفر زمان سفر در شبکه های وابسته به زمان وقوع و تصادفی
چکیده انگلیسی
This study addresses the problem of determining the path with the least expected travel time on stochastic and time-dependent networks. The Bellman's optimality principle is not applicable to this problem -because of its non-linear objective function- making it difficult to solve. In this light, we propose a pruning-based algorithm that progressively determines subpaths from the source and eliminates those that are non-optimal. The algorithm uses a novel bi-level, bounds-based pruning criterion to determine whether subpath can belong to the optimal path. We show that the pruning criterion is valid and that the algorithm terminates with an exact solution. Computational experiments demonstrate that the algorithm can successfully solve the problem even on large real-world networks and that its practical computational complexity is polynomial. Finally, we show that the pruning algorithm outperforms the existing non-dominance based procedure by a factor proportional to the network size on medium-sized networks and more so on large-sized networks. This work has the potential to aid in a wider application of stochastic time-dependent networks for modeling and analysis.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Transportation Research Part B: Methodological - Volume 108, February 2018, Pages 127-147
نویسندگان
,