Combining Exact and Heuristic Approaches for the Covering Salesman Problem
Publish place: 08th International Industrial Engineering Conference
Publish Year: 1391
نوع سند: مقاله کنفرانسی
زبان: English
View: 1,289
This Paper With 5 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
IIEC08_209
تاریخ نمایه سازی: 7 آذر 1391
Abstract:
We consider a generalized version of the well known Traveling Salesman Problem called Covering Salesman problem. In this problem, we are given a set of vertices while each vertex ican cover a subset of vertices within its predetermined covering distance r ;. The goal is to construct a minimum lengthHamiltonian cycle over a subset of vertices in which those vertices not visited on the tour has to be within the covering distance of at least one vertex visited on the tour. We propose ahybrid exact and heuristic approach which takes advantage of Integer Linear Programming (ILP) techniques and heuristicsearch to improve the quality of the solutions. Extensive computational tests on the standard benchmark instances and on a new set of large sized datasets show the effectiveness of the proposed approach.
Authors
Majid Salari
Ferdowsi University ofMashhad