Skip to Main content Skip to Navigation
Journal articles

Proper balance between search towards and along Pareto front: biobjective TSP case study

Andrzej Jaszkiewicz 1 Thibaut Lust 2
2 DECISION
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this paper we propose simple yet efficient version of the two-phase Pareto local search (2PPLS) for solving the biobjective traveling salesman problem (bTSP). In the first phase the powerful Lin–Kernighan heuristic is used to generate some high quality solutions being very close to the Pareto front. Then Pareto local search is used to generate more potentially Pareto efficient solutions along the Pareto front. Instead of previously used method of Aneja and Nair we use uniformly distributed weight vectors in the first phase. We show experimentally that properly balancing the computational effort in the first and second phase we can obtain results better than previous versions of 2PPLS for bTSP and at least comparable to the state-of-the art results of more complex MOMAD method. Furthermore, we propose a simple extension of 2PPLS where some additional solutions are generated by Lin–Kernighan heuristic during the run of PLS. In this way we obtain a method that is more robust with respect to the number of initial solutions generated in the first phase.
Document type :
Journal articles
Complete list of metadata

https://hal.sorbonne-universite.fr/hal-02076619
Contributor : Thibaut Lust <>
Submitted on : Friday, March 22, 2019 - 11:36:15 AM
Last modification on : Friday, January 8, 2021 - 5:32:06 PM

Identifiers

Citation

Andrzej Jaszkiewicz, Thibaut Lust. Proper balance between search towards and along Pareto front: biobjective TSP case study. Annals of Operations Research, Springer Verlag, 2017, 254 (1-2), pp.111-130. ⟨10.1007/s10479-017-2415-5⟩. ⟨hal-02076619⟩

Share

Metrics

Record views

93