Competitive travelling salesmen problem: A hyper-heuristic approach

G. Kendall, J. Li

Research output: Journal PublicationArticlepeer-review

15 Citations (Scopus)

Abstract

We introduce a novel variant of the travelling salesmen problem and propose a hyper-heuristic methodology in order to solve it. In a competitive travelling salesmen problem (CTSP), m travelling salesmen are to visit n cities and the relationship between the travelling salesmen is non-cooperative. The salesmen will receive a payoff if they are the first one to visit a city and they pay a cost for any distance travelled. The objective of each salesman is to visit as many unvisited cities as possible, with a minimum travelling distance. Due to the competitive element, each salesman needs to consider the tours of other salesman when planning their own tour. Since equilibrium analysis is difficult in the CTSP, a hyper-heuristic methodology is developed. The model assumes that each agent adopts a heuristic (or set of heuristics) to choose their moves (or tour) and each agent knows that the moves/tours of all agents are not necessarily optimal. The hyper-heuristic consists of a number of low-level heuristics, each of which can be used to create a move/tour given the heuristics of the other agents, together with a high-level heuristic that is used to select from the low-level heuristics at each decision point. Several computational examples are given to illustrate the effectiveness of the proposed approach.

Original languageEnglish
Pages (from-to)208-216
Number of pages9
JournalJournal of the Operational Research Society
Volume64
Issue number2
DOIs
Publication statusPublished - Feb 2013
Externally publishedYes

Keywords

  • Game theory
  • Heuristics
  • Hyper-heuristic
  • Travelling salesmen problem

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Fingerprint

Dive into the research topics of 'Competitive travelling salesmen problem: A hyper-heuristic approach'. Together they form a unique fingerprint.

Cite this