کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
483295 1446213 2006 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A simulated annealing and hill-climbing algorithm for the traveling tournament problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A simulated annealing and hill-climbing algorithm for the traveling tournament problem
چکیده انگلیسی

The Traveling Tournament Problem (TTP) [E. Easton, G. Nemhauser, M. Trick, The traveling tournament problem description and benchmarks, in: Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, CP 2001, 2001, pp. 580–584; M. Trick, Challenge Traveling Tournament Problems, 2004] schedules a double round-robin tournament to minimize the total distance traveled by competing teams. It involves issues of feasibility and optimality and is a challenge to constraint and integer programming. In this work, we divide the search space and use simulated annealing (SA) to search a timetable space and hill-climbing to explore a team assignment space. The SA component mutates timetables using conditional local jumps to find timetables which lead to better schedules while hill-climbing is enhanced by pre-computation and dynamic cost updating to provide fast and efficient search. Computational experiments using this hybrid approach on benchmark sets give results comparable to or better than current best known solutions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 174, Issue 3, 1 November 2006, Pages 1459–1478
نویسندگان
, , ,