کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949565 1440195 2017 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A heuristic for cumulative vehicle routing using column generation
ترجمه فارسی عنوان
یک مسیریابی برای خودروهای تجمعی با استفاده از نسل ستون
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we computationally study, an inexact approach for constructing solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation and is solved using column generation. The pricing subproblem is solved heuristically using dynamic programming. Simulation results show that a simple scalable strategy gives solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 228, 10 September 2017, Pages 140-157
نویسندگان
, ,