کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4959440 1364862 2018 11 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
Two phased hybrid local search for the periodic capacitated arc routing problem
ترجمه فارسی عنوان
جستجوی فیزیکی ترکیبی دو فازی برای مشکل مسیریابی قوس ظرفیت دار دوره ای
کلمات کلیدی
ابتکارات؛ مسیریابی قوس ظرفیت دار؛ بهینه سازی دوسطحی؛ جستجوی ترکیبی محدود
Heuristics; Capacitated arc routing; Bi-level optimization; Constrained combinatorial search;
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی

•Periodic capacitated arc routing has two hierarchical optimization objectives.•We present a novel two phased hybrid local search algorithm for the problem.•The outcome of the first phase helps to prune the search space in the second phase.•We devise combined local search heuristics for both search phases.•We report improved best upper bounds for 44 out of 63 benchmarks.

The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (Fv) and a secondary objective of minimizing the total cost (Fc). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective Fc while attaining all the known optimal values regarding the objective of the number of vehicles Fv. To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 264, Issue 1, 1 January 2018, Pages 55-65
نویسندگان
, ,