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

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
نویسندگان
,