Abstract: For the long travel time on trip itinerary planned by iterated local search (ILS), this paper proposes an optimization algorithm based on iterated local search with cuckoo search optimization to reduce the travel time. Firstly, this algorithm adopts ILS algorithm for solving an initial trip itinerary and several tourist attractions with some relevant objectives and constraints. Then, under the circumstance of no changing the time windows and the number of tourist attractions, this paper utilizes CS algorithm to minimize the travel time. The tourist route is obtained by above methods in this paper. It is more conform to travel habits and less travel time than existed ones. The experimental results on Daminaos and Guilin city data sets show that the average travel time of the proposed method reduces by 8%, compared with only using ILS algorithm in itinerary optimization, and planning the itinerary for personalized tourists is more in line with user's choice.

Key words: trip itinerary planning, iterated local search, cuckoo search, orienteering problem with time windows, travel salesman problem with time windows

摘要： 针对迭代局部搜索（iterated local search，ILS）算法求解旅游线路时间花费较长的问题，提出了一种ILS结合布谷鸟搜索（cuckoo search，CS）的优化算法，来优化旅游线路的时间花费。该算法首先根据相关目标和约束采用ILS算法求解旅游景点及初始旅游线路，然后在满足旅游景点时间窗约束及景点总数不变的情况下采用CS算法进一步最小化旅游线路的时间花费。该研究获得的线路更符合旅游习惯，并且旅游时间花费更少。通过Daminaos数据集和桂林景点数据集进行验证，结果表明该优化算法相比于仅使用ILS算法所规划出的旅游线路，平均时间花费减少8%，更符合用户旅游选择习惯。

关键词: 旅游线路规划, 迭代局部搜索, 布谷鸟搜索, 带时间窗的定向问题, 带时间窗的旅行商问题