کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476374 | 699457 | 2006 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Vehicle Routing Problem with elementary shortest path based column generation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The usual column generation model for a Vehicle Routing Problem involves an elementary shortest-path subproblem. The worst-case complexity of the known algorithms for this problem being too high, the elementary-path constraint is usually relaxed. Indeed, as each customer must be visited exactly once, the two problems with and without the elementary-path constraint have the same optimal integer solutions. In this article, we propose one theoretical and several practical improvements to the algorithm for elementary paths. We obtain better lower bounds and pruning of the search tree, and these improvements allowed us to find an exact solution to 17 instances of the Solomon benchmark suite which were previously open.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 33, Issue 10, October 2006, Pages 2972–2990
Journal: Computers & Operations Research - Volume 33, Issue 10, October 2006, Pages 2972–2990
نویسندگان
Alain Chabrier,