A Bicriteria Traveling Salesman Problem with Sequence Priorities

Heinz Schmitz () and Sebastian Niemann
Additional contact information
Heinz Schmitz: Fachhochschule Trier
Sebastian Niemann: Fachhochschule Trier

Chapter 1 in Metaheuristics in the Service Industry, 2009, pp 1-14 from Springer

Abstract: Abstract This paper introduces a bicriteria version of the classical Traveling Salesman Problem (TSP) which is motivated by various applications in the context of service delivery. The additional objective allows to take priorities among locations into account while minimizing the costs of traveling. For this, cities in the input are given in a strict ordering, e.g., due to arrival times of delivery requests. The goal is to compute the set of efficient solutions when both objectives are optimized simultaneously. To the best of our knowledge, this variation of TSP has not been studied before. After making the notion of priorities precise, we present a local-search algorithm to approximate the set of non-dominated solutions.While still being conceptionally easy, our algorithm employs different means of intensification and diversification in a way we call breadth-first local search. We maintain one candidate solution for each possible value of the additional objective in a polynomially-sized archive, and try to improve this set towards the Pareto front. Experimental results with test data from TSPLIB show that this is a reasonable approach to attack the problem.

Keywords: Bicriteria traveling salesman problem; Local search; Metaheuristic; Multi-objective discrete optimization; Sequence priorities (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:lnechp:978-3-642-00939-6_1

Ordering information: This item can be ordered from
http://www.springer.com/9783642009396

DOI: 10.1007/978-3-642-00939-6_1

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().