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

Andrzej Jaszkiewicz () and Thibaut Lust ()
Additional contact information
Andrzej Jaszkiewicz: Poznan University of Technology
Thibaut Lust: Sorbonne Universités, UPMC Universités Paris 06

Annals of Operations Research, 2017, vol. 254, issue 1, No 7, 130 pages

Abstract: 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.

Keywords: Multiobjective optimization; Pareto local search; Traveling salesman problem (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2415-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:254:y:2017:i:1:d:10.1007_s10479-017-2415-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2415-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().