多目标动态优化的问题,而最短路径算法也是计算机科学与.doc

[摘要] TSP问题是运筹学的典型问题，其衍生模型可以用于各种多目标动态优化的问题，而最短路径算法也是计算机科学与地理信息科学等多领域的研究热点。其实际问题的约束条件复杂，目标函数多样，问题的特殊性使其甚至不具有最优算法。本文则运用多种方法多角度对这一问题进行了建模及求解。第一问从传统的图论解法开始，通过无向图的Hamilton回路建模，使用Dijkstra的改进算法将问题转化为单目标的非线性规划函数并得出了单一旅行商的问题。第二、三问仍从图论入手，基于最小生成树用两种方法共同建立出模型。第四问的求解跳出传统的算法框架，借用经济学中消费者效用的概念从旅行者的角度出发，先运用模糊数学的层次分析法（AHP）将复杂的满意度的主观评价问题定量分析，得出比较分散的景点选择域。考虑到游客在消费博弈中的自组织行为和政府规划的管制效应，建立局部反馈的RBF神经网络模型通过迭代对景点选区进行优化。最后运用Huffman二叉树对景点进行路性组织，得到适合于不同品味人群的五条路线，同时还分散了游客对环境和资源的压力。模型的建立过程中从浅入深，虽然还存在很大改进余度，但已逐步摒弃了传统TSP问题中对游客刚性的、理性的、线性的行为假设，还原了社会生活中柔性的、非线性，非理想的行为人模式，具有很强的现实价值和拓展前景。 [关键字]TSP问题 多目标动态优化 最短路径 Hamilton回路 最小生成树 主观评价 层次分析法 RBF神经网络 最优二叉树 非线性 一.问题的重述 王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。 Q1．请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。 Q2．如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。 Q3．如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。 Q4．新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。 二.基本假设 模型假设及分析 所有景区、景点均为节点。 假设个旅游景点之间用同样的汽车作为交通工具，并且单位路程的交通费相同（均为0.10元）。 只考虑不同景点间公路的连接，将公路作为节点之间的通路。在简化过程中，优先考虑主要公路。 汽车发车时间连续，行驶时间不单独计算，不考虑交通中的意外。 考虑仅乌鲁木齐有全国班机通航，规定游客的旅行起止都是从乌鲁木齐 问题初步分析 根据图中给出的各景点的分布情况，结合所搜集的信息，将位于主要交通线路上的、知名度高的景点作为重要景点，并简化为算法中的节点。结合实际情况，从上海出发到新疆，则旅游起点只能为乌鲁木齐，因此将乌鲁木齐设为中心节点。在根据所查得的景点和景区间的距离，对题目所给交通图简化如图1-1。图中连线表示各地之间的公路，数字代表路程（单位为KM）。 图1-1 三．问题一 问题分解： 以旅游景点逗留的天数作为自变量，以单位天数所用的钱为目标函数，取最小值。 选择最优巡回路，我们参考了如下两个定义： 巡回路：过各个节点，每个节点至少经过一次的回路。 哈密尔顿回路：每个节点只经过一次的回路。 总长度最小的巡回就是最优巡回路。 最优巡回赂和最优哈密尔顿回路在如下条件下是等价的； 定理：回路中，任2个节点，若能满足下列三角不等式： 则最优巡回路与哈密尔顿回路相同。 理论模型建立的基本思想是： 首先，对于任意一个无向网络，利用任意节点之间的最短路算法构建一个等价网络，在网络中个节点之间的距离用最短路代替。据此，解得的最优哈密尔顿回路就可以很方便的还原为最优巡回路，实质是TSP问题。而解最优哈密尔顿回路的方法可以才用最优二叉树法（参考书[1]64页）、DijKstra（见参考书[2]336页）法等。解TSP问题也有相应的软件求解，更为方便。 基于以上对问题1的分析，要解决问题1的关键在于每种旅行路线方案的最优解的获得，而获得最优解的关键则在于确定网络的最优巡回路。 第1步 将图变换为。 第2步 为方便表示，将图中各节点进行编号如表1-1 编号 景区（景点）名称 编号 景区（景点）名称 A 乌市 K 天鹅湖 B 石河子 L 喀什、香妃墓 C 伊犁 M 和田