农村客运网络的图论实践和探索
第３６卷第２期数学的实践与认识ｖｏｉ．３６Ｎ。．２２０（）６年２月ＭＡＴＨＥＭＡＴＩＣＳＩＮＰＲＡＣＴＩＣＥＡＮＤＴＨＥＯＲＹＦｅｂ．，２００６
农村客运网络的图论实践和探索
张毅１，张桓奇２
（１．吉林大学交通学院。长春１３００２５）
（２．吉林省运输管理局。长春１３００２１）
摘要：按照城乡运输一体化的总体思路，为实现农村村村通客车的目标．针对农村客运线路繁杂，节点众
多的特点．本文应用图论最短树．Ｈａｍｉｌｔｏｎ回路．进行网络优化，并对其算法进行了探索．
关键词：农村运输；图论；算法探索
Ｏ引言
农村公路客运网的规划和建设是农村发展的重要内容，为全面建设小康社会，实现人便于行，货畅其流．需要从规划布局的角度，科学地审视农村公路网和客运线路．
村村通客车，是农村客运网的基本要求，但农村村屯点多面广，线路繁杂，网络节点众多，道路迂回曲折．如何科学合理的选择路径，即达到农村客运网络畅达便捷，合理布局即是关键问题．
现有的客运线路，系依托路网，村屯自然经济和区域特点而形成；其路径是否合理，线路覆盖面和便捷程度，总体资源配置是否优化，尚无完整定量分析，系统和路网是否科学等一系列问题还有待确定．本文拟对农村公路客运网络用经典的图论和新型的算法进行结构布局分析．并在实践中对组合优化中的ＮＰ类问题的解法探索．
１路网图论概述
一般区域农村公路网，是一个点集
（村、屯、乡、镇）和线集（道路、桥梁）组
成的大型复杂图．图的理论，作为独立
的学科有其自身的发展，图论源起自于
路径，例如经典的哥尼斯堡七桥问题，
以及计算证明浩繁的四色定理问题．现
在，追朔图论其源，用图论研究解决农
村公路运输网是恰如其分的决择，亦是
迄今为止．社会经济工作中最庞大的网
络系统工程．
一个图Ｇ，各顶点（村乡）用ｙｊ表
示，连接孤线（道路）用ｄ，．表示．若两村巧问有道路，则以ｊ一１．无道路以ｊｖ，寒铡墨
一ｏ．例如，吉林省某地区和县城间的网络图如图１．
收稿日期：２００４—１０一２０
图ｌ弭孚常
２期张毅，等：农村客运网络的图论实践和探索１９９
该网络中道路是双向的，即每条路径上车辆可同时相向行驶．因此，所构成的邻接矩阵Ａ是：
此矩阵是咒×以（１）ｙ２ｙ３ｙ４Ｖ５ｙ６ｙ７ｙ８ｙ９ｙｌｏｙ１１ｙ１２ｙ１３
清楚表明了网络各节点的相互位置和连接关系．显然，网络中任意两点都有道路可通，为全面判定农村路网中任意二点间的可达性，可依据道路矩阵来运算，道路矩阵Ｐ的计算公式为：
其中Ｊ，
Ｐ＝ＡＶＡ２…Ｖ以“＝ＶＡ‘Ｋ’Ｉ—ｌ
Ａ。＝以’１／＼以（ｒ一２，３…咒）Ｐ“＝｛：喜二７到ｕ存在道路如果表明点和线的关联关系，即村和道路的连接关系，可引入门×ｍ关联矩阵．示，Ｂ中的元素定义为：
ｆ１（ｙ，ｙＫ）一Ｐ，ｙ，是Ｐ』的始点
％一≮一１（耽ｙ，）一勺，
ｙｉ是勺的终点ｌｏ其它
（２）
（３）
（４）
以Ｂ表（５）
考虑到目前的道路都是双向的，因此，关联矩阵中一般无一１元素．按图１所示的路网
关联矩阵是：
ＯＯ１Ｏ０ＯＯ０１ＯＯＯＯＰ１（’Ｐ１３掣１４（６）Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
１
Ｏ
Ｏ
０
Ｏ
Ｏ
１
Ｏ
ＯＯ０Ｏ１ＯＯＯＯ０１ＯｌＯ００ＯＯＯＯ０Ｏ１Ｏ１ＯＯＯＯＯＯＯＯ０ｌ０１ＯＯＯ０１Ｏ０ＯＯＯＯ１ＯＯＯ０ＯｌＯ１ＯＯＯＯ０ＯＯＯｌＯＯＯＯ１ＯＯＯＯＯＯＯＯ００Ｏ１Ｏ１０ＯＯＯＯ１Ｏ０Ｏ１０１ＯｌＯＯ０１０１Ｏ１Ｏ１Ｏ０ＯＯ０Ｏ０Ｏ０１Ｏ１００Ｏ１１ＯＯ０Ｏ１Ｏ１Ｏ０ＯＯＯＯＯＯＯＯ田１ｏ１ｏｏ１ｏｏｏｏｏｏＨ型仉仍儿仉儿讥仍仉‰儿‰｜ｌＡ１
Ｏ
Ｏ
１
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
ＯＯＯＯ００ＯＯＯＯＯ１１Ｐ
ＯＯＯＯ０ＯＯＯ０Ｏ１１Ｏ白ＯＯＯＯ０１ＯＯＯＯＯＯ１０ＯＯＯ１Ｏ０Ｏ０ＯＯ１Ｏｏｏｏｏｏｏｏｏｏ１１ｏｏ％ＯＯＯＯＯ０ＯＯ１１Ｏ０Ｏ．，ＯＯＯＯ１ＯＯ１０ＯＯ０Ｏ．０ＯＯ１ＯＯＯ０１ＯＯＯＯＯ～１ＯＯＯＯ０１ＯＯＯＯ０Ｏ白Ｏ００ＯＯ１１ＯＯＯＯ０Ｏ．６Ｏ０ＯＯｌ１ＯＯＯＯＯＯＯ０Ｏ００ｌ１ＯＯＯ０ＯＯ０Ｏ．０ＯＯｌ１ＯＯＯＯＯＯＯ０ＯｂＯｌ１００Ｏ０Ｏ０Ｏ０Ｏ０吒１１ＯＯＯ０ＯＯＯ０ＯＯＯＰ仉仉仉以儿仉“％一８
２０（）数学的实践与认识３６卷２以最短树方法布置客运线路
２．１最短树和营运线路
树是不含有回路的连通图，如果村落的地理座标已知，将这些村落以直线连接起来，并且总路径最短，则就构成了最短树．如果暂不考虑人口，经济等诸因素，以通达率和营运覆盖率为基点，则应用最短树来连接各村落并由此来确定营运线路，不失为最佳决择．
２．２最短的Ｋｒｕｓｋａｌ算法应用实例
设丁．是正权图Ｇ＝（可，Ｐ，山）中支撑树的集合，若其中一棵树Ｔ的总长度Ｌ，，满足加一ｍｉｎ（乏：啡）则丁是图Ｇ的—棵最｛辫求最短椭多僦，其中Ｋｒｕｓｋａｌ算法为：
。”５７“－石’
１．将图中所有边接权的太小顺序排列，
∞（∥，１）≤甜（Ｆ皑）…≤∞（Ｐｍ，）
２．按次序加放最短边‰构成子图７１’，若加入‰后，丁’中出现回路，则排除％继续进行．３．若丁’中的边数为＂～１，则结束，否则按步骤２继续．
设某地区县域内，座落着２４个行政市、乡、村，这些行政村位于高速公路一侧，在高速公路上有地区中心城入口和若干个镇人口，并且各入口都有匝道相连．各匝道通向并连接着各个村的公路．为使农村客运线路向高速公路聚集．形成城乡问的密切交流．如何安排确定农村客运线路，使其更快捷．
这２４个点线网络如图２，各连线上的数字是道路里程，单位为Ｋｍ，ｉ为各节点编号，下边标注为地名
图２
按Ｋｒｕｓｋａｌ算法，得出最短树如图３
２期张毅，等：农村客运网络的图论实践和探索２０１
＼
＼＼＼
、
图３
２．３营运线路在最短树上运行
根据最短树的性质，丁是一个树，则丁是最小的连接图，且无回路，因此图３中有些树枝是悬置的，对于营运线路必须按原路返回，并没有达到向高速公路聚集的目的，因此，在确定营运线路时，应考虑以县域中心县城为始（终）发点，以高速公路主干线上的点２２，２３，２４为终（始）点，确定营运线路的思路是：
１）最短树是构成营运线路的基本框架．
２）营运线路应尽可能的在最短树的枝上运行．为使线路直达，允许最短树上临近的二点相连，并允许隶属于不同营运线路产生回路．
基于上述原则，如以县域中心梨树县（节点３），为始点，拟开辟如下线路，路线所经节点是：
Ａ：③一⑧一⑥一③一⑩一⑨
Ｂ：③一⑥一⑧一⑩一＠
ｃ：③一④一⑤一⑥一⑦一⑨一⑨一⑨
Ｄ：⑧一②一⑨一⑧一③
Ｅ：③一②一①一⑧一⑤一⑩一◎
Ｆ：③一⑩一⑥一⑩
上述线路，返程亦然，并且可以重新组合，如以月一，Ｂ＿１…Ｆ１表示回程，则Ａ与Ｃ～，Ｄ与Ｅ“或Ｆ＿１可以组合，构成多对线路，再辅以时间的有序安排，即可实现农村线路与高速公路主干线衔接，又可覆盖每个村屯．实现网络优化和城乡一体化布局．
３哈密顿回路与循环发车的营运线路
在农村客运线路的实践中，基层运输管理部门创造出循环发车方法．这实际上是图论中著名的哈密顿（Ｈａｍ订ｔｏｎ）回路问题．即ｎ个地点，要求从暮一个地点出发，寻找出一条线路。经过每个点一次且仅一次最后又返回原地的周游路线．我们现在所研究的农村客运线路的首要问题是如何使这一循环发车总的里程最短，即求最短的Ｈａｍ订ｔｏｎ回路．图４为县域内１４个市镇乡的节点及路径图．
其相应的道路矩阵为：
２０２数学的实践与认识３６卷
ｙ，
ｙ，
ｙ，
ｙ．ｙ。
ｙ６
ｙ，
Ａ＝ｙ８
ｙ。
ｙｌｏ
ｙｌｌ
ｙ１２
ｙ１３
ｙ１４图４
ｙｌＶ２ｙ３ｙ４ｙ５ｙ６ｙ７ｙ８ｙ９ｙｌｏｙｌｌｙ１ｚｙ１３ｙ１４
１）以矩阵（或图）找出１４条矩离最短的路径
ｙ４ｙ５—５
ｙ５ｙ７—６ｙｌ矿１１＝７ｙｌｙ２—８ｙ１３ｙ１４＝８
ｙ２ｙ１４—９ｙ３ｙ１４—９Ｖ１２ｙ１３—１０ｙｚｙ３＝１２
ｙｚｙ４＝１２ｙ４ｙ８—１２ｙ６ｙ７＝１２
ｙ１１ｙ１２＝１２ｙ３ｙ６＝１３将上述路径构画到各节点上如图５：
（７）
＂９ｏ８珀衢卯∞镐∞甜札弘勰心№埔加丛∞弘曲鸥蛎粥坞¨勰％卵弘押弛铊∞¨掩船弘弛粥拢烈嬲挖押¨¨∞羽鹂弱勰拍ｎ
均＂牡０鸺弛∞孙鹃弛拍Ｍ地Ｍｏ８ｏ
２期张毅，等：农村客运网络的图论实践和探索２０３
④
图５
此路径显然不是Ｈａｍｉｌｔｏｎ回路
。．。１．ｙ。，矿。。两点无路径连接
２．点ｙ：ｙ。ｙ。ｙ。。的线度（即连线）均超过３（即此点多次进出），因为只有线度为２，即“一进一出”才符合要求．
２）点ｙ：的线度４，必须排除２条线度，在ｙ，ｙ。，ｙ。ｙ。，ｙ：ｙ。，ｙ。ｙ…４条线路中，连接ｙ。点的线度已为２，说明在没构成回路之前已返回ｙ。点，因此必须排除ｙ。ｙ：．同时增加ｙ。ｙ。一１５这条边；在剩余的３条边中，考虑必须排除ｙ。ｙ。这条边，（因为如果保留此边中，将增加里程．并须向二个方向搜索）．同地添加边ｙ。ｙ。。＝１８．
３）排除ｙ，ｙ：，ｙ：ｙ。后，此时只有点ｙ。，ｙ。。的线度为３，显然只有断开连接这二点的ｙ。ｙ…方使二点线度为２，同时增加ｙ。。ｙ，，至此，回路构成．如图６．
以上路径全程１５９公里，按图中连接关系，以ｙ。点或其它ｙｊ点沿顺、逆时针方向构成循环发车．从包含１，１个节点来讲，此回路是最短的Ｈａｍｉｌｔｏｎ路．
在实际运作中，可以依此为基础架构，创造出多种发车方式和营运线路，如连接ｙ。ｙ：两点，可以形成ｏ。型两个循环线每年春运，瞬间农村客流高峰涌现，及时依上述架构为基础，安排合理的班线，创造出科学的营运路线．示意如图７．形成畅达、便捷、连通的循环发车方式，为疏导客流，构通城乡运输服务．
４算法分析
组合优化理论中的ＮＰ类算法是至今发展迅速但仍尚未得到解决的问题，“村村通客车”归结为旅行商问题是ＮＰ类难题．只要有一类问题找出多项式解法，整个ＮＰ类问题都将迎刃而解．近年来涌现的遗传算法，人工智能算法对于求解复杂度较高的网络问题行之有效．为复杂网络工程的实际应用奠定了基础，例如利用计算机Ｋｒｕｓｋａｌ算法求最小生成树并
２０４数学的实践与认识３５卷
ｏｏｏｏｏ图６
ｏ
图７
ｃ路田
不需要对所有边排序而是建堆，其类Ｃ＋＋算法为：
ｆｏｒ（Ｉ一０：Ｉ（ｅＮｕｍ＆＆１（ｖＮｕｍ；Ｉ＋＋）／／ＫｒｕｓｋａｌＳｔａｒｔ
｛
产ｖ．ｆｉｎｄ（Ｅ．ｔｏｐ（）．ｖ１）；ｋ＝Ｖ．ｆｉｎｄ（Ｅ．ｔｏｐ（）．Ｖ２）－
ｉｆ（ｊ！＝ｋ）｛Ｖ．ｍｅｒｇｅ（ｊ，ｋ）；ａ［１］一Ｅ．ｔｏｐ（）；ｌ＋＋）
Ｅ．ｐｏｐ（）；
｝
其中ｅＮｕｍ表示边数ｖＮｕｍ为点数，具体代码不冗述．
连接“村村通客车’’是在一定区域内求最短路程的Ｈａｍｉｌｔｏｎ回路，对此，人类已探索了近１５０年，目前遗传算法等新型算法颇多且较为有效，但搜寻是否终止在最优解上仍须证明，将其归结为整数规划问题似已见到解决问题的端倪，如
ｍｉｎｚ一∑∑ｄ庐；』
２期张毅．等：农村客运网络的图论实践和探索２０５
ｆ∑％＝ｌ
㈠
文匕１∑％＝１（８）
ｉ卢１
式中整数变量ｚｉ』＝１表示从点ｉ到歹．该模型乍看类似分配问题，但为防止出现子回路
ｆ萎｝％托删～以
户：ｃｒ，一｛趸乏三ｕ。∥愚哆。。）’∈““。驯。口‘ｃｔ。，
峨∽＝高…’
峨（ｆ）一∑△吒（ｆ）（１２）
２０６数学的实践与认识３６卷
该方法在公路路径数据库的基础上，具有实用性，具有正反馈，分布式计算等特点，在农村较大网络中实践应用是适宜的．
５结束语
为实现全面建设小康社会的宏伟目标，解决广大农村人口的出行问题亦是重要内容之一，农村客运线路的优化问题．应迅速提到日程上来．应用经典的图论问题研究当今社会经济问题显得必要和迫切．本文应用经典的图论问题，结合现代的算法，对农村营运线路优化作出实践，已开始应用实施．相信也具有其普遍意义．
参考文献
卢开澄．图论及其应用［Ｍ］．清华大学出版社．２０００．
张纪会．徐心和．一种新的进化算法——蚁群算法［Ｊ］．系统工程理论与实践．１９９９．ｉ９（３）：８４一一８７．
王励成．孙麟平．求解度限制最小生成树的启发式遗传搜索算法［Ｊ］．系统工程理论与实践．２００３．２３（５）：１０３一
１０７．
赵学峰．基于蚁群算法的一类扩展ＴｓＰ研究［Ｊ］．系统工程．２０Ｑ３．１．
金海和．陈剑等．基于Ｈｏｐｆｉｅｌｄ网络学习的多城市旅行商问题的解法［Ｊ］．系统工程理论与实践．２００３．２３（７）
１００一１０５．
盂繁桢。胡云昌等．旅行商问题的遗传算法［Ｊ］．系统工程理论与实践．１９９７．９．
孙焕纯．王跃方．货郎扭问题的人：Ｉ：智能～一人机交换解法口］．系统工程理论与实践，２０００．２０（５）：卜一ｌｏ．
ＰｒａｃｔｉｃｅａｎｄＥｘｐｌｏｒｅｏｆＧｒａｐｈｉｃＴｈｅｏｒｙ
ｉｎＣｏｕｎｔｒｙｓｉｄｅＰａｓｓｅｎｇｅｒＴｒａｆｆｉｃ
ＺＨＡＮＧＹｉｌ，ＺＨＡＮＧＨｕａｎ～ｑｉ２
（１．ＪｉｌｉｎＵｎｉｖｅｒｓｉｆｙＣｏＩｌｅｇｅｏｆＴｒａｎｓｐｏｒｔａｔｉｏｎ，Ｃｈａｎｇｃｈｕｎ１３００２５．Ｃｈｉｎａ）
（２．ＪｉｌｉｎＰｒｏｖｉｎｃｉａｌＢｕｒｅａｕｏｆＴｒａｎｓｐｏｒｔａｔｉｏｎＡｄｍｉｎｉｓｔｒａｔｉｏｎ，Ｊｉｌｉｎ１３００２ｌ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ
ｔｏｔｈｅｔｈｏｕｇｈｔｏｆｕｒｂａｎａｎｄｒｕｒａｌａｒｅａｓｔｒａｎｓｐｏｒｔａｔｉｏｎｉｎｔｅｇｒａｔｅｄｏＶｅｒａＵｔｒａｉｎ，ｆｏｒｒｅａｌｉｚｅｔｈｅｇｏａｌｏｆｃｏｕｎｔｒｙｓｉｄｅｅｖｅｒｙｖｉｌｌａｇｅ
ｃｏｈｅｒｅｎｔｐａｓｓｅｎｇｅｒｔｒａｉｎ，ｔｏｒｕｒａｌｐａｓｓｅｎｇｅｒｔｒａｆｆｉｃｂｅｉｎｇｃｉｒｃｕｉｔｍｉｓｃｅｌ】ａｎｅｏｕｓ，ｎｏｄｅ
ｎＬｌｍｅｒｏｕｓｃｈａｒａｃｔｅｒｊｓｔｉｃ?ｔｈｉｓａｒｔ；ｃｌｅＬｌｓｅ．Ｓｈｏｒｔｅｓｔｔｒｅｅｔｈｅｏｒｙｏｆｇｒａｐｈｉｃ，ｔｈｅｒｅｔｕｒｎｃｉｒｃｕｉｔｏｆＨａｍｉｌｔｏｎ，ｎｅｔｗｏｒｋｏｐｔｉｍｉｚｅｓ，ａｎｄｅｘｐｌｏｒｅ
ｉｔｓａＩｇｏｒｉｔｈｍ．
Ｋｅｙｗｏｒｄｓ：ｃｏＬＩｎｔｒｙｓｉ（１ｅｔｒａｆ“ｃ；ｇｒａｐｈｉｃｔｈｅｏｒｙ
］Ｊ１『一１Ｊｎ瞳口Ｌ＝ｌ卧哑口
农村客运网络的图论实践和探索
作者：张毅， 张桓奇， ZHANG Yi， ZHANG Huan-qi
作者单位：张毅,ZHANG Yi(吉林大学交通学院,长春,130025)， 张桓奇,ZHANG Huan-qi(吉林省运输管理局,长春,130021)
刊名：
数学的实践与认识
英文刊名：MATHEMATICS IN PRACTICE AND THEORY
年，卷(期)：2006，36(2)
被引用次数：2次
参考文献(7条)
1.卢开澄图论及其应用 2000
2.张纪会.徐心和一种新的进化算法--蚁群算法[期刊论文]-系统工程理论与实践 1999(03)
3.王励成.孙麟平求解度限制最小生成树的启发式遗传搜索算法[期刊论文]-系统工程理论与实践 2003(05)
4.赵学峰基于蚁群算法的一类扩展TSP研究[期刊论文]-系统工程 2003
5.金海和.陈剑基于Hopfield网络学习的多城市旅行商问题的解法[期刊论文]-系统工程理论与实践 2003(07)
6.孟繁桢.胡云昌旅行商问题的遗传算法 1997(0q)
7.孙焕纯.王跃方货郎扭问题的人工智能--人机交换解法[期刊论文]-系统工程理论与实践 2000(05)
引证文献(2条)
1.李雪滨.秦鸿睿.谢军基于运输网络细分的农村客运发展策略研究[期刊论文]-科技资讯 2009(2)
2.张博通村公交规划方法初探[期刊论文]-湖南交通科技 2007(3)
本文链接：https://www.wendangku.net/doc/6a2195509.html,/Periodical_sxdsjyrs200602033.aspx
授权使用：中南大学(zndx)，授权号：ea455d10-127c-47b9-845e-9e4501020382
下载时间：2010年12月7日