校园最佳游览路线问题的数学模型分析.(定稿)

校园最佳游览路线问题的数学模型分析

廖川荣

(南昌大学数学系, 江西南昌 330031)

[摘要] 将某高校的校园示意图转化为赋权连通图,求得该连通图的邻接矩阵,利用Floyd算法及图论软件包构造一个最短路径矩阵,得到一个赋权完全图,将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题,建立混合整数线性规划模型,并利用优化软件求得最优解.从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题.

[关键词] 赋权完全图；最佳游览路线；最优配置.

[中图分类号] O157.6 [文献标识码] A [文章编号] 91136

1 引言

现在国内许多高校每年都会定期举办校园开放日,开放日旨在全面展示该校的办学特色及优美的校园环境,反映大学生丰富多彩的校园生活.通过举办开放日,为考生填报高考志愿提供全面真实和具体的信息,让考生和家长了解学校的历史和现状,熟悉招生,在大学和考生之间建立一个友好顺畅的交流沟通平台.

某高校开放日,将会有许多考生及家长要求参观该校的新校园,以下为校园简化示意图:(其中vi为参观者需参观的主楼、景点和场地,连线为两参观点间道路,连线上数字为两参观点间距离，单位:公里)

图1:校园简化示意图

说明: V1医学院教学大楼, V2本科生公寓A区, V3学生食堂A, V4国际学术交流中心, V5白求恩广场, V6医学实验大楼, V7青年教师宿舍区, V8研究生院, V9运动场A, V10正门, V11工程实验楼, V12天健园, V13研究生公寓区, V14基础实验大楼, V15本科生公寓B区, V16办公楼, V17中心广场, V18图书馆, V19计算机实验中心, V20保安楼, V21理科生命大楼, V22材料楼, V23环境楼, V24正气广场, V25人文楼, V26信工楼, V27法学楼, V28机电楼与建工楼, V29综合教学楼, V30学生食堂B, V31外经楼, V32学工楼, V33艺术楼, V34商业街, V35校医院, V36本科生公寓C区, V37学生食堂C, V38体育馆, V39体育场, V40游泳馆, V41

1

运动场B.

校方拟在本校高年级学生中招募一批临时导游,负责接待并陪同考生及家长乘坐校园游览车（限载 50人,时速20公里/小时）参观游览新校园,路线是从新校园正大门出发,最后返回到出发地.为了向所有参观者展示该校的风貌和亮点,同时满足参观者了解校园的不同要求,校方要求应聘者提供一份详细的校园游览计划,计划中应包括以下内容:

1）根据考生的理、文、工、医四种报考专业为参观者选择下车参观的主楼、景点和场地. 2）根据校园简化示意图及问题1确定的下车参观的主楼、景点和场地,建立数学模型,按报考专业分别设计4条不同的最佳游览路线,使每条游览路线的总路程最短.

3）假设有3000本省考生及1000外省考生想在开放日这天参观游览该校的新校园；且根据历年统计，开放日上午参观人数约为全天参观人数的60%.问该校开放日至少要预备多少辆校园游览车?

2 模型假设

1) 不同报考专业的参观者总是更有兴趣参观与本专业有关的主楼、景点或场地,导游通过指示牌来引导报考不同专业的考生及家长乘坐不同路线的游览车.

2) 道路通畅,游览车只在选定参观点仃车,每个参观点只参观一次. 3) 对相同性质的楼群只参观一栋有代表性的主楼. 4) 不考虑天气等环境因素的影响.

5) 校园游览车限载50人,时速20公里/小时.

6) 参观者参观选定的主楼、景点与场地的时间均为5分钟.

7) 在开放日这天有3000本省考生及1000外省考生想参观游览该校的新校园. 8) 不考虑参观者上下车时间.

9) 开放日工作时间为上午8:00-12:00, 下午1:00-17:00.

10) 根据历年统计, 校园开放日上午参观人数约为全天参观人数的60%.

11）将各主楼、景点或场地看作平面上的质点,不考虑自身形状的大小,均称之为图论中的结点。

3 符号说明

vi: 参观者需参观的主楼、景点和场地. i1,2,,41

,41

,41

dvi,vj：两参观点vi与vj之间的路程.i,j1,2,di,jmindvi,vj: 两参观点vi与vj之间的最短路程.i,j1,2,Dk：第k条游览路线的最短路径矩阵(Floyd矩阵).Dk(di,j)n中的参观点数. (n1 =15, n2 =17, n3 =19, n4 =12)

knk，其中nk表示第k条游览路径

x(vi, vj): 代表游览路径中两参观点间的特征变量. 当vi与vj为最佳游览路线上两个相邻的需下车参观的景点时x(vi, vj)=1, 反之, x(vi, vj)=0. (i, j=1,2,……,41)

Pi: 参观者乘游览车游览第i条路线的概率. (i=1,2,3,4) Ri: 第i条游览路线上参观游览的人数. (i=1,2,3,4)

2

Si : 第i条游览路线起点发车速率. (i=1,2,3,4)

Ti : 游览车在第i条路线行驶一圈所需时间. (i=1,2,3,4) Ni: 第i条游览路线需要预备的最低校园游览车数. (i=1,2,3,4) N: 校方需要预备的最低校园游览车数. (N= N1 + N2 + N3 + N4 )

M: 在开放日这天想参观游览该校新校园的本省及外省考生的总人数.(M =4000)

4 模型建立与求解

4.1 选择参观者下车参观的主楼、景点和场地

校园开放日活动是社会各界认识了解高校的一个重要窗口,是加强学校与社会联系的一个重要途径,是提升高校社会影响力,发挥高校在科学技术领域中引领作用的重要措施,高校应在开放日向参观者充分展现该校的风貌和亮点.如:基础教学设施,医疗卫生设施,体育运动设施,亮点建筑和人文景观,同时还应考虑到参观者了解校园的不同要求.为此,根据考生的理、文、工、医四种报考专业为参观者选择下列需下车参观的主楼、景点和场地.

1) 理科路线参观点: v10正门, v16办公楼, v17中心广场, v18图书馆, v14基础实验大楼, v19计算机实验中心, v21理科生命大楼, v30学生食堂B, v29综合教学楼, v32学工楼, v34商业街, v36本科生公寓C区, v35校医院, v41运动场B, v24正气广场. (n1=15)

2） 文科路线参观点: v10正门, v16办公楼, v17中心广场, v18图书馆, v19计算机实验中心, v25人文楼, v27

法学楼, v31外经楼, v29综合教学楼, v30学生食堂B, v32学工楼, v34商业街, v33艺术楼, v35校医院, v36本科生公寓C区, v41运动场B, v24正气广场. (n2 =17)

3） 工科路线参观点: v10正门, v16办公楼, v17中心广场, v18图书馆, v11工程实验楼, v14基础实验大楼, v19计算机实验中心, v22材料楼, v23环境楼, v26信工楼, v28机电楼与建工楼, v30学生食堂B, v29综合教学楼, v32学工楼, v34商业街, v35校医院, v36本科生公寓C区, v41运动场B, v24正气广场. (n3=19)

4） 医科路线参观点: v10正门, v16办公楼, v17中心广场, v18图书馆, v6医学实验大楼, v5白求恩广场, v9

运动场A, v3学生食堂A, v2本科生公寓A区, v1医学院教学大楼, v4国际学术交流中心, v24正气广场. (n4=12)

4.2 设计4条不同的最佳游览路线 1）最短路径矩阵

将校园示意图转化为赋权连通图G(V, E):

vi,vjE,vi,vjdvi,vj.

求得该连通图的邻接矩阵,并利用Floyd算法及图论软件包构造一个最短路径矩阵(Floyd矩阵),得到一个赋权完全图G'V,E',

［1］

其中E′中每条边的权等于结点vi与vj在图G(V, E)中的最短路径的权: vi,vjE','vi,vjdi,jmindvi,vj.

根据问题1确定的理、文、工、医4个报考专业,分别得到4个赋权完全子图的最短路径矩阵。

3

例如医科路线的Floyd矩阵为:

D4(di,j)1212=

[0.00 0.40 0.65 0.90 0.80 0.60 1.35 1.25 1.00 0.60 0.40 0.90

0.40 0.00 0.25 0.50 1.20 1.00 1.75 1.65 1.40 1.00 0.80 0.50 0.65 0.25 0.00 0.25 1.40 1.25 1.60 1.85 1.60 1.25 1.05 0.75 0.90 0.50 0.25 0.00 1.15 1.35 1.35 1.60 1.35 1.50 1.30 1.00 0.80 1.20 1.40 1.15 0.00 0.20 0.55 0.45 0.20 0.40 0.40 1.70 0.60 1.00 1.25 1.35 0.20 0.00 0.75 0.65 0.40 0.20 0.20 1.50 1.35 1.75 1.60 1.35 0.55 0.75 0.00 0.30 0.60 0.95 0.95 2.25 1.25 1.65 1.85 1.60 0.45 0.65 0.30 0.00 0.30 0.70 0.85 2.15 1.00 1.40 1.60 1.35 0.20 0.40 0.60 0.30 0.00 0.40 0.60 1.90 0.60 1.00 1.25 1.50 0.40 0.20 0.95 0.70 0.40 0.00 0.20 1.50 0.40 0.80 1.05 1.30 0.40 0.20 0.95 0.85 0.60 0.20 0.00 1.30 0.90 0.50 0.75 1.00 1.70 1.50 2.25 2.15 1.90 1.50 1.30 0.00];

2）最佳游览路线求解

求考生理、文、工、医四种报考专业的最佳游览路线问题可归结为图论中的最佳推销员回路问题,

［3］

［2］

即在4个赋权完全子图中分别求一个近似最优的Hamilton圈,该最优H圈问题可用以下两种方法求解：

方法一：二边逐次修正法.

［4］

（1）输入图G'V,E'的一个初始圈; （2）用对角线完全算法产生一个初始H圈; （3）随机搜索出G′中若干个H圈,例如2000个;

（4）对第1、2、3步所得的每个H圈,用二边逐次修正法进行优化,得到近似最佳H圈; （5）在第4步求出的所有H圈中,找出权最小的一个,此即要找的最佳H圈的近似解. 方法二：混合整数线性规划模型.

［5］



nminZdijxiji,j1nj1,2,....nst.xij1,i1nxij1,i1,2,....nj1uiujnxijn1,2ijnxij0,1i,j1,2,.....nui0i2,3,....n

说明: 约束条件

xi.j1,j1,2,....n,xi.j1,i1,2,....n.只是该线性规划模型中的两个必要约束条件,

i1j1nn 4

而约束条件

uiujnxijn1,(2ijn)是为避免产生子巡回而附加的充分约束条件,其中

uii2,3,都满足该约束条件.

n可看作n-1个额外的变量.可以证明:任何含子巡回的路线都不满足该约束条件,全部巡回路线

求解结果如下(不加括号为下车参观点）：

（1）理科最佳游览路线: v10→(v16)→v24→(v31)→v29→v35→(v36)→v41→v36→v34→v32→v30→(v28)→(v26) →(v22)→v21→(v19)→v14→v19→v18→v17→v16→v10, 共有n1=15个下车参观点;最短游览路程：5.900000（公里）.

（2）文科最佳游览路线: v10→v16→v24→v25→v27→v29→v31→v33→(v39)→v35→(v36)→v41→v36→v34→ v32→v30→(v28)→(v26)→(v22)→(v21)→v19→v18→v17→(v16)→v10，共有n2=17个下车参观点；最短游览路程：6.300000（公里）.

（3）工科最佳游览路线: v10→(v16)→v24→(v31)→v29→v35→(v36)→v41→v36→v34→v32→v30→v28→v26→ v22→v23→(v22)→(v21)→(v19)→v14→v11→(v14)→v19→v18→v17→v16→v10, 共有n3=19个下车参观点；最短游览路程：6.800000（公里）.

（4）医科最佳游览路线: v10→v4→v1→v5→v6→v2→v3→(v7)→v9→(v8)→(v11)→(v14)→(v19)→v18→v17

→v16→v24→(v16)→v10, 共有n4 =12个下车参观点；最短游览路程：5.050000（公里）.

3) 计算校方开放日需要预备的最低校园游览车数

由问题假设,开放日将有3000本省考生及1000外省考生及其家长参观游览该校的新校园,参观者总数为M=4000;开放时间为上午8:00-12:00下午13:00-17:00.参观者按问题2确定的4条最佳游览路线分别参观游览新校园。

根据历年校园开放日的人数统计,开放日上午参观人数约为全天参观人数的60%.因此，开放日上午将有0.6×M人参观游览新校园,下午有0.4×M人参观游览新校园;校方开放日上午需要预备的最低校园游览车数可根据开放日上午参观游览的人数计算.

具体计算过程如下：

（1） 参观者游览第i条路线的概率: Pini.

ini=14（2）第i条路线上参观游览的人数: Ri =0.6×M×Pi（人）. （3）第i条路线起点发车速率: SiRi1辆/h. 游览车限载人数上午参观游览时间游览车行驶速度（4）第i条路线游览一圈所需时间: Ti游览路线的最短路程ni参观点的参观时间h, （5）第i条路线上最低游览车数: Ni=Si×Ti（辆）.

（6）开放日上午校方需要预备的最低校园游览车数：N= N1 + N2 + N3 + N4 .

5

5 结果

根据以上公式可算出:该高校开放日上午往返循环行使的校园游览车辆数为：理科游览路线4辆,文科游览路线6辆,工科游览路线7辆,医科游览路线3辆，开放日上午需要预备的最低游览车数为20辆.

同理可算出开放日下午往返循环行使的校园游览车辆数为：理科游览路线3辆,文科游览路线4辆, 工科游览路线5辆,医科游览路线2辆,开放日下午需要预备的最低游览车数总共为14辆.

由于开放日上午参观的人数多于下午的人数,校方开放日上午需要预备的最低游览车数也为全天所需要最低车辆数.因此,校方校园开放日需要预备的最低游览车数为20辆.

[参考文献]

[1] 张 蕾.矩阵方法求赋权图中最短路的算法[J].西北大学学报(自然科学版),2004,10: 527-530. [2] 马 良.旅行推销员问题的算法综述[J].数学的实践与认识,2000,4: 156-165. [3] 谭永基.经济管理数学模型案例教程[M].北京:高等教育出版社,2001,8: 374-377. [4] 杨庭栋等.最佳灾情巡视路线的数学模型[J]. 数学的实践与认识,1999,1: 50-59. [5] 韩中庚.数学建模方法及其应用[M].北京:高等教育出版社,2005,6: 185-188

Mathematical model Analysis about the best route of tourist in campus

Liao chuanrong

(Department of Mathematics, Nanchang University, Nanchang 330031, China)

Abstract: A campus’s sketch map is transfered into connected graph with weight and its adjacency matrix is gotten. The shortest path matrix is constructed and a completed graph with weight is gotten by Floyed arithmetic and the software package of graph. The best tourist route of campus problem is regarded as TSP problem, i.e., find the best similar Hamilton circle in the completed graph with weight. It is solved three problems in the opening day of campus:

1. For visitors to choose the main buildings, spots or sites.

2. According to the sketch map, design the shortest four tourist paths. 3. Get the minimal number of sightseeing bus in the opening day of campus.

Keywords: Completed graph with weight; The shortest tourist path; The best configuration.

6