方苏杰 张宇航 方成刚

1(南京师范大学附属中学 江苏 南京 210003)2(南京工业大学 江苏 南京 211800)

0 引 言

随着生活水平的提高，人们对旅游消费的热情一直处于持续增长的过程。游览景点的规划是否合理对于旅行过程的感受至关重要，合理的游览路径不仅使旅行者感到时间安排合理、费用合算、旅游感观价值高，还能使旅行社降低成本、提高效益、提升好评指数。游览景点规划问题从不同角度对旅行过程进行优化，如从最短时间、最小费用、最短距离等不同方面对旅游景点进行寻优[1-3]。文献[4]以庐山为例，以一日游为时间约束，利用Dijkstra算法实现尽可能多景点的最短路径规划；文献[5]以旅游成本和游客舒适度为目标函数，利用遗传算法对全国201个5A级景区的旅游路径进行优化。

传统的游览景点规划通常以成本最小作为优化目标，但对于旅行社或旅行者常常需要针对一定的旅行预算费用进行规划，并希望在预算费用范围内尽可能游览更多综合性价比高的景点。

1 问题描述与分析

旅行费用通常包括交通费、住宿膳食费、门票费等几个部分，不同的游览景点规划将导致上述几个费用比例发生变化。对于旅行社或旅行者而言，如何优化选择旅游景点以便在合理的预算费用范围内游览更多评价指数高的景点是一个经常遇见的问题。

该问题难点在于旅行总费用随景点规划的不确定而发生动态变化，需要通过优化算法在预算费用范围内选择合适的游览景点以降低交通食宿费所占比例，增强旅行体验。……