کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895529 1445976 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lower bounding procedure for the asymmetric quadratic traveling salesman problem
ترجمه فارسی عنوان
روش محدود کردن کمتر برای مشکل فروش نامتقارن فروشنده درجه دوم
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem (AQTSP). Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimal. We propose an extended Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we propose a column generation approach. Moreover, we apply a particular reformulation-linearization technique on a compact representation of the problem, and compute lower bounds based on Lagrangian relaxation. We compare our new bounds with those obtained by some linearization models proposed in the literature. Computational results on some set of benchmarks used in the literature show that our lower bounding procedures are very promising.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 253, Issue 3, 16 September 2016, Pages 584-592
نویسندگان
, , , ,