• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Two hybrid metaheuristic approaches for the covering salesman problem

Pandiri, Venkatesh; Singh, Alok; Rossi, André (2019), Two hybrid metaheuristic approaches for the covering salesman problem, Neural Computing and Applications, 32, 19, p. 15643-15663. 10.1007/s00521-020-04898-4

Type
Article accepté pour publication ou publié
Date
2019
Journal name
Neural Computing and Applications
Volume
32
Number
19
Publisher
Springer
Pages
15643-15663
Publication identifier
10.1007/s00521-020-04898-4
Metadata
Show full item record
Author(s)
Pandiri, Venkatesh
School of Computer and Information Sciences
Singh, Alok
School of Computer and Information Sciences
Rossi, André
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This paper addresses the covering salesman problem (CSP), which is an extension of the classical traveling salesman problem (TSP). Given a set of cities and a coverage radius associated with each one of them, the CSP seeks a Hamiltonian cycle over a subset of cities such that each city not in the subset is within the coverage radius of at least one city in the subset and that has minimum length among all Hamiltonian cycles over such subsets. To solve this problem, one has to deal with the aspects of subset selection and permutation. The CSP finds application in emergency and disaster management and rural healthcare. This paper presents two hybrid metaheuristic approaches for the CSP. The first approach is based on the artificial bee colony algorithm, whereas the latter approach is based on the genetic algorithm. Both the approaches make use of several new first improvement or best improvement based local search strategies defined over various neighborhood structures. Computational results on a wide range of benchmark instances demonstrate the effectiveness of the proposed approaches. We are able to improve the best known solution values on majority of the large instances.
Subjects / Keywords
Covering salesman problem; Traveling salesman problem; Heuristic; Genetic algorithm; Artificial bee colony algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    Multi-start iterated local search, exact and matheuristic approaches for minimum capacitated dominating set problem 
    Nakkala, Mallikarjun Rao; Singh, Alok; Rossi, André (2021) Article accepté pour publication ou publié
  • Thumbnail
    Swarm intelligence, exact and matheuristic approaches for minimum weight directed dominating set problem 
    Nakkala, Mallikarjun Rao; Singh, Alok; Rossi, André (2021) Article accepté pour publication ou publié
  • Thumbnail
    Focus distance-aware lifetime maximization of video camera-based wireless sensor networks 
    Rossi, André; Singh, Alok; Sevaux, Marc (2019) Article accepté pour publication ou publié
  • Thumbnail
    A Hybrid Optimization Approach For the Steiner k-Connected Network Design Problem 
    Diarrassouba, Ibrahima; Labidi, M. K.; Mahjoub, Ali Ridha (2018) Article accepté pour publication ou publié
  • Thumbnail
    Search space reduction in MILP approaches for the robust balancing of transfer lines 
    Pirogov, Aleksandr; Rossi, André; Gurevsky, Evgeny; Dolgui, Alexandre (2021) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo