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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Applegate D, Bixby R, Chvátal V and Cook W (2006). The Travelling Salesman Problem: A Computational Study. Princeton University Press: Princeton, NJ.
Bai R, Burke E and Kendall G (2008). Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation. Journal of the Operational Research Society 59 (10): 1387–1397.
Bektas T (2006). The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega 34 (3): 209–219.
Burke E, Kendall G and Soubeiga E (2003a). A tabu-search hyperheuristic for timetabling and rostering. Journal of Heuristics 9 (6): 451–470.
Burke E, Kendall G, Newall J, Hart E, Ross P and Schulenburg S (2003b). Hyper-heurisitics: An emerging direction in modern search technology. In: Glover G and Kochenberger K (eds). Handbook of Metaheuristics. Chapter 16, Kluwer Academic Publishers: The Netherlands, pp 457–474.
Burke E, McCollum B, Meisels A, Petrovic S and Qu R (2005). A graph-based hyper-heuristic for educational timetabling problems. European Journal of Operational Research 176 (1): 177–192.
Burke EK, Hyde MR and Kendall G (2006). Evolving bin packing heuristics with genetic programming. In: Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN 2006). Lecture Notes in Computer Science, Vol. 4193, pp 860–869.
Burke E, Hyde M, Kendall G, Ochoa G, Ozcan E and Woodward J (2009). Exploring hyperheuristic methodologies with genetic programming. In: Mumford C and Jain L (eds). Collaborative Computational Intelligence. Springer Verlag: Berlin, Heidelberg, pp 177–201.
Burke E, Hyde M, Kendall G and Woodward J (2010a). A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics. IEEE Transactions on Evolutionary Computation 14 (6): 942–958.
Burke E, Hyde M, Kendall G, Ochoa G, Ozcan E and Woodward J (2010b). A classification of hyper-heuristic approaches. In: Handbook of Meta-Heuristics. Kluwer: The Netherlands, pp 449–468.
Cowling P, Kendall G and Soubeiga E (2000). A hyperheuristic approach to scheduling a sales summit. Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling, PATAT 2000; Konstanz, Germany, pp 176–190.
Garrido P and Riff M (2007). DVRP: A hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic. Journal of Heuristics 16 (6): 795–834.
Gendreau M and Potvin J (2005). Metaheuristics in combinatorial optimization. Annals of Operations Research 140 (1): 189–213.
Gutin G and Punnen A (2002). The Travelling Salesman Problem and Its Variations. Kluwer Academic Publishers: The Netherlands.
Laporte G (2010). A concise guide to the traveling salesman problem. Journal of Operational Research Society 61 (1): 35–40.
Lawler E, Lenstra J, Kan A and Shmoys D (1986). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons: Hoboken, NJ.
Nash J (1951). Noncooperative games. Annals of Mathematics 54 (2): 286–295.
Osborne M and Rubinstein A (1999). A course in Game Theory. MIT Press: New York.
Papadimitriou C and Roughgarden T (2005). Computing equilibria in multi-player games. In: Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, pp 82–91.
Pisinger D and Ropke S (2007). A general heuristic for vehicle routing problems. Computers and Operations Research 34 (8): 2403–2435.
Ross P (2005). Hyper-heuristics. In: Burke EK and Kendall G (eds). Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer Science+Business Media, LLC, pp 529–556.
Acknowledgements
This study is supported by an EPSRC (Engineering and Physical Science Research Council) project (Ref: EP/D061571/1). The authors would like to thank Dr Andrew Parkes for his helpful comments. The authors also thank two anonymous reviewers for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kendall, G., Li, J. Competitive travelling salesmen problem: A hyper-heuristic approach. J Oper Res Soc 64, 208–216 (2013). https://doi.org/10.1057/jors.2012.37
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2012.37