کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959637 | 1445953 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster
ترجمه فارسی عنوان
مسائل مربوط به عدم همبستگی: نقاط نزولی پویا در برچسب دو طرفه برای حل مشکلات کمترین مسیر با محدودیت منابع سریع تر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسیریابی مشکل کوتاهترین مسیر با محدودیت منابع، الگوریتم برچسب زدن دو طرفه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
With their paper “Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints” [Discrete Optimization 3, 2006, pp. 255-273] Righini and Salani introduced bounded bidirectional dynamic programming (DP) as an acceleration technique for solving variants of the shortest path problem with resource constraints (SPPRC). SPPRCs must be solved iteratively when vehicle routing and scheduling problems are tackled via Lagrangian relaxation or column-generation techniques. Righini and Salani and several subsequent works have shown that bounded bidirectional DP algorithms are often superior to their monodirectional counterparts, since the former can mitigate the fact that the number of labels increases strongly with the path length. Bidirectional DP has become a quasi-standard for solving SPPRCs with general resource extension functions. In computational experiments, however, one can still observe that the number of forward and backward label extensions is very unbalanced despite a symmetric bounding of a critical resource in the middle of its feasible domain. We exploit this asymmetry in forward and backward label extensions to reduce the overall workload by introducing a so-called dynamic half-way point, which is a dynamic bounding criterion based on the current state of the simultaneously solved forward and backward DPs. Experiments with the standard and the electric vehicle routing problem with time windows as well as the vehicle routing and truck driver scheduling problem confirm that dynamic half-way points better balance forward and backward labeling and reduce the overall runtime.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 261, Issue 2, 1 September 2017, Pages 530-539
Journal: European Journal of Operational Research - Volume 261, Issue 2, 1 September 2017, Pages 530-539
نویسندگان
Christian Tilk, Ann-Kathrin Rothenbächer, Timo Gschwind, Stefan Irnich,