Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
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
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : lundi 1 juin 2020 - 20:20:52
Dernière modification le : lundi 14 novembre 2022 - 02:42:07




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⟩



Consultations de la notice