کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9664085 | 1446256 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Locating median cycles in networks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Locating median cycles in networks Locating median cycles in networks](/preview/png/9664085.png)
چکیده انگلیسی
In the median cycle problem the aim is to determine a simple cycle through a subset of vertices of a graph involving two types of costs: a routing cost associated with the cycle itself, and the cost of assigning vertices not on the cycle to visited vertices. The objective is to minimize the routing cost, subject to an upper bound on the total assignment cost. This problem arises in the location of a circular-shaped transportation and telecommunication infrastructure. We present a mixed integer linear model, and strengthen it with the introduction of additional classes of non-trivial valid inequalities. Separation procedures are developed and an exact branch-and-cut algorithm is described. Computational results on instances from the classical TSP library and randomly generated ones confirm the efficiency of the proposed algorithm. An application related to the city of Milan (Italy) is also solved within reasonable computation time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 160, Issue 2, 16 January 2005, Pages 457-470
Journal: European Journal of Operational Research - Volume 160, Issue 2, 16 January 2005, Pages 457-470
نویسندگان
Martine Labbé, Gilbert Laporte, Inmaculada RodrıÌguez MartıÌn, Juan José Salazar González,