最优旅行方案设计.doc

最优旅行方案设计 随着自由行成为出行的新选择制定一个全面的旅游计划越来越重要而选择交通工具、安排酒店和设计旅游路线则是规划的关键本文将时间与费用问题转化为换乘次数和站台数问题将站台和所在线路构成换乘矩阵建立多目标路径优化模型运用MATLAB逐步求解直达路线、换乘一次、两次及三次路线结合站台数选取最佳路线下面是小编整理的最优旅行方案设计欢迎来参考 采用背包问题与旅行商问题（TSP）相结合的方法先通过背包问题将所有景点进行分组再通过TSP问题将每天的路线进行优化达到乘车总时间最小利用Lingo求解考虑乘车路费与时间景点门票与酒店价格以及景点游览时间等因素建立01规划将实现费用少、景点多的多目标通过适当的拟合转化为单目标优化模型并使用Lingo得出3天内最优的旅游路线与酒店安排依据游客的游览兴趣赋予景点门票一定的权重约束并考虑安排不同酒店的因素基于问题三的模型增加优先级约束条件与目标函数建立多目标规划之权重最优化模型采用模型三的方法利用Lingo求解出最佳路线与酒店安排 一、问题的分析 选择最优的出行方案所谓最优的选择可以有如下几种解释：（1）最节省时间的线路（尤其是存在换乘的情况）（2）最节省费用的线路（3）将时间与车费做加权平均后的最小值根据游客个人对时间和金钱的重视程度选择要搭乘的公交车及其线路 在限定游览时间的前提下为实现费用少、景点多的目标需选择酒店距离景点较近、每天的景点之间路径近、景点游览时间较短且费用较低的酒店和景点此问题类似最小费用最大流问题本文建立01规划使用Lingo得出3天内最优的旅游路线与酒店安排 二、基本假设 1.假设交通系统始终正常运行不存在堵车临时交通事故恶劣天气等情况 2.假设乘坐一辆车为不换乘乘坐两辆车为换乘一次以此类推 3.假设游客是理性的即会从时间最优、价钱最优或者时间与价钱权重最优三种情况下选择其中之一 4.假设公交车的行驶速度保持不变 5.假设游客参观时间为该景区给定的参观时间 6.假设从酒店步行到车站以及从车站步行到景点的时间忽略不计 7.假设乘客到起始站可以直接选择公交车即不计在起始站的等车时间 8.假设游客每天的游览路线是环形的 三、问题分析与求解 基于预处理矩阵判断出发点和目的地之间是否有直达的线路如有就确定为最优线路若无就通过MATLAB寻找换乘次数超过一次的所有站点 寻找换乘站点把求得的站点与要求的出发点和目的地建立循环逐个修改起始站点与终止站点的值可求出通过各站点的路线再将经过所求得的站点的路线与经过起点和终点的路线进行比较寻找相同的路线若存在则这个站点可作已知的起点与终点的中转站；若不存在中转站则调整换乘次数直到可以找到可行的乘车路线为止在换乘次数尽量最少的原则之下以从出发地点到达目的地点的总乘车站数为基准换乘车前后总乘车站数为最少的作为系统的推荐线路这样既符合常规也可能是最优线路 因此选取上述三种方法权重最小的作为最有出行线路从出发地到目的地的所需要的总时间T由两部分构成：一是公交的行驶时间；二是乘客换乘时的耗时（本题忽略此时间）公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数即从出发点到目的地所需总时间为 T=（mk1）*t1 建立目标函数 minT mins（换乘次数） s.t.0s2mk1 路径选择原则具体如下： 在系统中输入乘客的起始位置和目的地为了实现乘客的目标且能使换乘次数少则可按如下步骤进行搜索16；（若乘客所行驶的路线经过某个车站则为1否则为0用C表示） 搜索集合A与看是否存在一条路线使得流线同时经过a与b两种结果若存在则说明只要乘车一次就可以到达目的地乘车路线可为a与b所同时存在的那条线 若种情况不成立则需要换车搜索集合A与看是否存在两条路线且在这两条路线上有相交的车站cap满足cap不等于0如果存在则说明需要换车一次则可到达目的地乘车路线为：acapb若cap只有一种搜索结果显示从a到b的乘车线路就是这种最佳若不是唯一的而有多种选择换乘一次可达目的地则此时可有K种途径可以到达目的地此时就进一步对此K种中转站进行扫描输出站点数最少的一种方式进而显示乘坐次数最佳的途径到达目的地 如果都不存在时说明乘车至少要换两次搜索集合A：看是否存在两个中转站站点以及满足在这三条路线上至少有两条路线上有公共的车站若存在则说明只需换车两次即可到