试论南京青奥会游客最优线路模型

【摘 要】 第二届夏季青奥会2014年将在南京举行。本文主要运动数学手段，按照实际原型到数学模型，再指导实际的研究思路，以个人需求为导向，为南京青奥会的游客制定了一条最佳的路线方案。

【关键词】 指派模型 旅行商模型 匈牙利法 层次分析

为了制定一条满足游客要求的路线方案，我们应用解释结构模型（ISM）技术，将路线方案分为三个因素：路线选择、赛场以及景点，并运用ISM的实用化方法，建立的多级递阶有向图。在景点和赛场之间建立指派模型，以公交路线的距离为基础建立效率矩阵，运用匈牙利算法，将赛场与1—2个景点捆绑，得到最优解（整体路程最短）；在赛场和路线方案之间，建立有向图，计算两点之间的权重时综合考虑出行时间、换乘次数以及出行费用这三个因素，运用层次分析法，确定这三个因素的权重。其次，因为三个因素的单位不同，我们选定评价尺度，将三个因素无量纲化，方便统计。在确定两点之间的权重的基础上，建立旅行商模型，得到最优方案。

在对问题建立模型与求解之后，我们对模型进行了评价与改进，使之更符合动态实际。

1 问题重述

南京2014年青奥会各项目比赛将安排在2014年8月17日至28日举行。本届青奥会的竞赛项目主要是参考2012年伦敦奥运会和2010年新加坡青奥会的项目设置，确定了28个竞赛项目，所有比赛将在“三大场馆区”的15个不同竞赛场馆进行。请你解决一下问题：

现为一个游客制定一条线路，要求在至少观看七场比赛（不同赛场）的同时，还要游览10个景点。

2 问题假设

（1）假设依据个人兴趣爱好，已经确定了至少需要观看的七场比赛和十个景点；（2）在评价线路方案时，以公交为基础，只考虑换乘次数、出行时间、出行费用三种因素，忽略其他因素的影响。

3 问题分析

为了制定一条满足要求的路线方案，我们应用解释结构模型（ISM）技术，将路线方案分为三个因素：路线选择、赛场以及景点。并运用ISM的实用化方法，建立了多级递阶有向图：

在景点和赛场之间建立指派模型，以公交路线的距离为基础建立效率矩阵，运用匈牙利算法，将赛场与1—2个景点捆绑，得到最优解（整体路程最短）；

在赛场和路线方案之间，建立有向图，计算两点之间的权重时综合考虑出行时间、换乘次数以及出行费用这三个因素，运用层次分析法，确定这三个因素的权重。其次，因为三个因素的单位不同，我们选定评价尺度，将三个因素无量纲化，方便统计。在确定两点之间的权重的基础上，运用相应的算法，得到最优方案。

4 基于指派模型，将10个景点试指派给7个赛场

应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小），这类问题称为指派问题或分配问题。每个指派问题存在一个效率矩阵，其元素Cij>0表示指派第i个人去完成第j项任务时的效率（或时间、成本等）。解题时引入变量Xij；其取值只能是1或0。并令

1当指派第i个人完成第j项任务

=

0当不指派第i个人完成第j项任务

当问题要求极小化时的数学模型是：

，j=1，2，3，…，n

，i=1，2，3，…，n

=1或0

指派问题是0—1规划特例，可以用匈牙利法解决：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。

依据个人实际，在确定需要游玩的10个景点以及观看的7场不同比赛之后，以每个景点距离7个赛场的距离为基础，建立效率矩阵。指派观看某场比赛时，游玩哪些景点。

由于想要游玩的景点多分布在江苏省五台山体育中心、玄武湖公园铁人三项赛场和南京市龙江体育馆周边，所以假设在观看这三处比赛时，游玩两个景点，其它处只游玩一个景点。同时依据实际，假设在观看玄武湖公园铁人三项赛场比赛时，游玩玄武湖景点，在观看南京金牛湖风景区帆船赛场的比赛，游玩金牛湖景点。这样，得到一个8*8的效率矩阵：

第二步：进行试指派，以寻求最优解

（1）从只有一个0元素的行开始，给这个0元素加圈。

（2）给只有一个0元素的列的0元素加圈；然后划去所在行的0元素。

（3）反复进行（1）、（2）两步，直到所有0元素都被圈出和划掉为止。

（4）若任有没有画圈的0元素，且同行（列）的0元素至少有两个（表示对这个可以从两项任务中指派其一）。这是可以进行试指派。

（5）若元素的数目m等于矩阵的阶数n，那么这个指派问题的最优解已得到。若m

第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能够找到最多的独立元素。

第四步：增加0元素，返回第二步，若得到n个独立的0元素，则以的最优解，否则回到第三步重复进行。

结果：

南京奥林匹克体育中心——莫愁湖

江苏省五台山体育中心——中山陵、总统府

南京市龙江体育馆——南京大屠杀纪念馆、夫子庙

江宁区体育中心——雨花台

江苏省房山体育训练基地——栖霞山

玄武湖公园铁人三项赛场——玄武湖、明孝陵

南京金牛湖风景区帆船赛场——金牛湖

这样总路程为105.5公里

5 基于层次分析和图与网络方法建模

在乘坐公交的过程中，不同的乘客可能有很多种优先考虑的因素，比如说换乘次数，总站数，时间，费用等等，但我们经过分析后认为，主要考虑的换乘次数、出行时间、出行费用三项，然后用层次分析法综合考虑这三个因素的综合评价标准。因此，我们建立了如下模型——基于层次分析评价的模型（如图1）

如右图所示，我们自上而下地建立了三个层次：目标层，准则层和方案层。其中在准则层中，我们考虑三方面的因素：总时间，费用和换乘次数（如图2）。

我们运用1-9标度来对三个准则进行成对比较。根据三个因素对评价结果的比较分析，构造出成对比较矩阵A（如表1）。

判断依据：

①在青奥会期间，人流及车流量增大，乘客一般会优先考虑换乘次数最少的方案，比如说在有直达车到达的情况下，在有多辆车同时直达的情况下才会考虑时间费用等因素，因为换乘所带来的不便和不可预期的等待时间往往是人们力图避免的，所以换乘次数比时间稍重要，比费用明显重要。

②时间与费用相比，由于南京青奥会只举办12天，游客需要观看比赛的同时，需要游览景点，耽误时间将会产生不可预估的经济损失，所以时间比费用稍重要。

计算公式：

6 路线确定

由于目前2014年青奥会的赛程安排还未确定，我们这里假设，该游客在到达某奥运场馆的当天刚好有比赛。

基于这点，便可引用图论中无向图原理，建立权值矩阵，具体建立过程如下。

图G={V，E}，其中顶点集，表示7个不同的场馆，边集，并且边或弧上的权值为，其数值大小有上一步计算出的两两场馆间的综合距离给出。由图论原理，建立权值矩阵，其中，

考虑到该游客出行与回程的方便，我们规定其出游路线中首站与末站相同，且距离他到达南京首发位置最近（如南京火车站等）。考虑到出游效率最大化，我们规定该游客每天在不同的场馆观看不同的比赛，且游玩不同的景区，即7天内经过7个场馆一次且恰一次。这与求解旅行商问题类似，下面给出两个模型求解。

7 求近似最优Hamilton圈的最邻近算法模型：

将求解最优路线的问题简化为“Hamilton回路问题”。“Hamilton回路问题”可以简述为，在n面体上寻找经过每个顶点一次且恰一次的特殊的圈。利用求近似最优Hamilton圈的最邻近算法（其MATLAB程序见附录），执行调用函数f=TSP（w，v0）。

因素一：

考虑出游路程最短，建立的权值矩阵

经过程序运行，可得结果为

江苏省五台山体育中心江苏省房山体育训练基地江宁区体育中心南京奥林匹克体育中心南京市龙江体育馆玄武湖公园铁人三项赛场南京金牛湖风景区帆船赛场

这样的出游路线能够使得旅游的路程总和最短，具有较高的效用性。

因素二：

考虑游玩方便，将游客在各场馆间乘坐公交所需要换乘的次数作为主要参考要素，可建立权值函数：

经过程序运行，可得结果为

江苏省五台山体育中心江苏省房山体育训练基地南京金牛湖风景区帆船赛场南京奥林匹克体育中心南京市龙江体育馆玄武湖公园铁人三项赛场江宁区体育中心

这样的路线能够更加方便游客出游，具有较高的实用性。

因素三：

若考虑交通费用，将游客在出游期间乘坐交通工具的花费作为主要参考要素，可建立权值函数：

经过程序运行，可得结果为

江苏省五台山体育中心江苏省房山体育训练基地江宁区体育中心南京奥林匹克体育中心南京市龙江体育馆玄武湖公园铁人三项赛场南京金牛湖风景区帆船赛场

这样的出游路线能够使得旅游的路程总和最短，具有较高的经济性。

8 结合赛程以0-1规划求解最优线路

在实际青奥会的比赛过程中，由于每个场馆都会有比赛日程，并不能对场馆地点直接进行排序。还应当结合实际比赛的日程安排，再做具体规划。

目前，距离南京青奥会的举办还有2年，场馆尚在筹办中，我们目前还不能获得具体的赛程安排表。不妨假设，在saicheng（i，j）矩阵中，以i代表日期，j代表场馆，其值为0则该天该场馆无比赛，1表示有比赛。我们根据上届安排，给出了一个大致的安排表，可以根据最后的实际情况，再做改动。

规划线路的具体实现步骤：

（1）创建场馆间的综合权值矩阵，赛程安排矩阵；

（2）给出限制条件，即每天只能在一个场馆观看比赛，7天内能参观7个不同场馆；

（3）做出游览线路规划，并使得在场馆换程过程中，其综合权值的和最小。

使用lingo软件，可以实现这样的规划。结果如下：

因此，我们给出了最后的线路安排：

玄武湖公园铁人三项赛场南京金牛湖风景区帆船赛场江宁区体育中心南京奥林匹克体育中心江苏省房山体育训练基江苏省五台山体育中心南京市龙江体育馆

9 模型评价及优化，结合赛程的最优线路模型的评价：

该模型以三个不同的因素作为主要参考值，给出三条不同的出游路线，分别具有效用性，实用性，经济性。游客可根据自身的健康、爱好、经济状况，决定采用哪种方案。同时，给出多种方案，也有利于疏散集中人群，使得交通不致拥堵。

该模型具有一般的通用性。能够适用于任何给定权值的路径检索或最优规划问题，应用广泛，且运行稳定，是个不错的模型。

参考文献：

[1]青奥会青网，http：///，2012年7月5日.

[2]王海英.图论算法及其MATLAB实现.北航，2010年2月1日.

[3]杜利峰，牛永洁.蚁群算法在MATLAB中的实现.信息技术，2011年第6期.

[4]韩中庚.数学建模方法及其应用.高等教育出版社，2006.