Combining Exact and Heuristic Approaches for the Covering Salesman Problem

Publish Year: 1391
نوع سند: مقاله کنفرانسی
زبان: English
View: 1,256

This Paper With 5 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

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