Skip to Main content Skip to Navigation
Book sections

An Evolutionary Algorithm with Path Relinking for a Bi-objective Multiple Traveling Salesman Problem with Profits

Abstract : This chapter deals with a bi-objective multiple traveling salesman problem with profits (BOMTSPP), generalizing the classical TSP with profits (TSPP). The TSPP is in fact a generic name for TSP problems taking into account the length of the tour and profits collected at customers. However, all these problems are not really bi-objective: the two criteria are aggregated into a single objective or one of them is replaced by a constraint. Our BOMTSPP aims at building m cycles covering a subset of potential customers so that the total collected profit is maximized and the overall traveling distance is minimized. This new problem generalizes the TSPP in two directions: a true bi-objective treatment and the construction of multiple tours. The proposed solution method is an effective evolutionary algorithm, reinforced by a post-optimization procedure based on path-relinking (PR).
Document type :
Book sections
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02490543
Contributor : Daniel Gavrysiak <>
Submitted on : Tuesday, February 25, 2020 - 11:44:47 AM
Last modification on : Wednesday, February 26, 2020 - 2:02:53 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Nacima Labadie, Jan Melechovský, Christian Prins. An Evolutionary Algorithm with Path Relinking for a Bi-objective Multiple Traveling Salesman Problem with Profits. Applications of Multi-Criteria and Game Theory Approaches, pp.195-223, 2014, Springer Series in Advanced Manufacturing, 978-1-4471-5295-8. ⟨10.1007/978-1-4471-5295-8_10⟩. ⟨hal-02490543⟩

Share

Metrics

Record views

41