The 8th International Industrial Engineering Conference , 2012-02-15

Title : ( Combining Exact and Heuristic Approaches for the Covering Salesman Problem )

Authors: Majid Salari , Zahra Naji Azimi ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote

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 i can cover a subset of vertices within its predetermined covering distance ri. The goal is to construct a minimum length Hamiltonian 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 a hybrid exact and heuristic approach which takes advantage of Integer Linear Programming (ILP) techniques and heuristic search 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.

Keywords

, Integer Linear Programming, Heuristics
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1025777,
author = {Salari, Majid and Naji Azimi, Zahra},
title = {Combining Exact and Heuristic Approaches for the Covering Salesman Problem},
booktitle = {The 8th International Industrial Engineering Conference},
year = {2012},
location = {IRAN},
keywords = {Integer Linear Programming; Heuristics},
}

[Download]

%0 Conference Proceedings
%T Combining Exact and Heuristic Approaches for the Covering Salesman Problem
%A Salari, Majid
%A Naji Azimi, Zahra
%J The 8th International Industrial Engineering Conference
%D 2012

[Download]