最优旅行方案设计

孙玉静　王月琨

【摘 要】随着自由行成为出行的新选择，制定一个全面的旅游计划越来越重要，而选择交通工具、安排酒店和设计旅游路线则是规划的关键。本文将时间与费用问题转化为换乘次数和站台数问题，将站台和所在线路构成换乘矩阵，建立多目标路径优化模型，运用MATLAB，逐步求解直达路线、换乘一次、两次及三次路线，结合站台数，选取最佳路线。采用背包问题与旅行商问题（TSP）相结合的方法，先通过背包问题将所有景点进行分组，再通过TSP问题，将每天的路线进行优化，达到乘车总时间最小，利用Lingo求解。考虑乘车路费与时间，景点门票与酒店价格以及景点游览时间等因素，建立0-1规划，将实现费用少、景点多的多目标通过适当的拟合转化为单目标优化模型，并使用Lingo得出3天内最优的旅游路线与酒店安排。依据游客的游览兴趣，赋予景点门票一定的权重约束，并考虑安排不同酒店的因素，基于问题三的模型，增加优先级约束条件与目标函数，建立多目标规划之权重最优化模型，采用模型三的方法，利用Lingo求解出最佳路线与酒店安排。

【关键词】多目标规划；旅行商问题；背包问题；Lingo；MATLAB

一、问题的分析

选择最优的出行方案。所谓最优的选择，可以有如下几种解释：（1）最节省时间的线路（尤其是存在换乘的情况），（2）最节省费用的线路，（3）将时间与车费做加权平均后的最小值，根据游客个人对时间和金钱的重视程度选择要搭乘的公交车及其线路。

在限定游览时间的前提下，为实现费用少、景点多的目标 ，需选择酒店距离景点较近、每天的景点之间路径近、景点游览时间较短且费用较低的酒店和景点。……