Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Hybrid evolutionary search for the traveling repairman problem with profits

Abstract :

The Traveling Repairman Problem with Profits is a node routing problem, where a repairman visits a subset of nodes of a weighted graph in order to maximize the collected time-dependent profits. In this work, we present the first population-based hybrid evolutionary search algorithm for solving the problem that combines: (i) a randomized greedy construction method for initial solution generation, (ii) a dedicated variable neighborhood search for local optimization, (iii) two crossover operators for solution recombination with an adaptive rule for crossover selection. Computational results on six sets of 120 benchmark instances from the literature demonstrate that the proposed algorithm achieves a high performance - it improves the best-known results (new lower bounds) for 39 instances, while matching the best-known results for the remaining cases. We investigate several main algorithmic ingredients to understand their impacts on the performance of the algorithm.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02715690
Contributeur : Okina Université d'Angers <>
Soumis le : lundi 1 juin 2020 - 20:20:52
Dernière modification le : mardi 2 juin 2020 - 04:03:49

Identifiants

Collections

Citation

Yongliang Lu, Jin-Kao Hao, Qinghua Wu. Hybrid evolutionary search for the traveling repairman problem with profits. Information Sciences, 2019, 502, pp.91-108. ⟨10.1016/j.ins.2019.05.075⟩. ⟨hal-02715690⟩

Partager

Métriques

Consultations de la notice

19