１研究背景

九江当前公交车线路对应的是过去的九江经济发展模式．但在新的时代背景下九江突破了往日的限制,一批又一批的地方如八里湖等地经济迅速发展,这也使往日的公交车线路不再适应当前的九江经济发达区发展的需要．从人口布局变化角度:城市的发展日新月异,人口的布局也在不断变化,过去集中在浔阳区的人口慢慢地已经分化至濂溪区、开发区、八里湖新区,但九江公交的线路规划却没有及时跟上人口布局的变化,如从火车站到开发区长江大道(含柴桑美食街、联盛快乐城等商圈)目前无线路规划,濂溪区与开发区之间线路过少等．因此,对于九江市公交车线路规划的改进就显得尤为重要与迫切．

２研究问题

此次研究目的在于设计出最合理的、最有利于经济发展的、市民满意的线路,改进九江市公交车线路规划．

３建立数学模型

简单的思路为:在获得市民普遍反映的、需要增添线路的站点的数据基础之上,将各个站点通过数学模型求解出连接顺序,即可获得民意线路．可以参考旅行商问题:一名推销员准备前往若干城市,从城市V１出发,要遍访城市V２,V３,V４,…,Vn各一次,最后返回V１．已知从Vi到Vj的距离为Wij,问他应按怎样的次序访遍这些城市,使总距离最少?用图论的术语说,就是在一个赋权完全图中,找出一个有最小权的Hamilton圈,也称这种圈为最优圈(其中边表示两个点之间的连线,权即为每个边的赋值大小)．其解决的思路为将各边的权加起来,寻找出求解最小权的圈的方法．此问题的权取决于各边的距离长短,距离长,权大;相应的,距离短,权小．因此,圈权和越小,总距离越小．综合分析后,只需将上述问题的影响权的参数扩展范围,使权越小,对应现实中价值越高．这样在我们找到了一些站点后,在完全赋权图上找出最小权圈,这就是我们要的民意线路．连出对应求最小权圈的解决思路也与上述问题一致．下面开始正式建模:

(１)问题分析

首先,每个站点都要连接,且只能连接一次,不能重复．其次每连接一个站点,则这个站点既使一条边的起点,也是下一条边的终点．连接完所有站点后,应回到起始点．我们这里的数学模型可以用纯粹的０－１整数规划来构建．

(２)约定符号

f(x)表示目标函数;Vn表示标号为n的地点;Wij同表示从i到j地间对应的权．其中i,j＝１,２,３,…,n．

(３)决策变量

变量Xij表示是否要从Vi出发到Vj,且令.

(４)目标函数

若决定将从Vi与Vj连接,则其权表达为Xij*Wij,于是目标函数表达为minf(x)＝∑ni＝１∑nj＝１Wij*Xij．此时目标函数的解也就对应了现实中满意度最高的,价值最高的民意线路连线顺序．

(５)约束条件

约束条件１由于每个地方只可以进入一次,则有∑nj＝１Xij＝１．约束条件２同理,由于每个地方只可以出发一次,则有∑ni＝１Xij＝１．约束条件３由于上述两个条件无法限制赋权图中有两个及两个以上圈情况的产生,如四个点连成一个小圈:v４→v５→v６→v７,其余点连成另一个大圈,这样就有两个圈．但仍然符合上述条件．因此需要附加条件使这种情况无法产生．条件如下:ui－uj＋nXij≤n－１．此式中:u１＝０,１≤ui≤n－１,ui为一个连续变量,仅用于约束条件３．ui可自行取值,如令ui＝i－１．类似于方程中的参数,仅影响Xij的取值,且ui无实际意义．(想一想,只要找到一组ui满足上述不等式就可以了吗?———编者注)下面开始证明该条件可以使形成赋权图中只含一个圈:任何含两个及以上圈的赋权图必然不满足于约束条件３用反证法进行证明:假设赋权图不止一个圈,则至少存在两个圈,那么至少有一个圈不含起点V１,如圈V４→V５→V６→V７,使用条件三,则必有:u４－u５＋n≤n－１,u５－u６＋n≤n－１,u６－u７＋n≤n－１．上述三式相加得０≤－３,不成立．因此假设不成立．所以任何含两个及以上圈的赋权图必然不满足于约束条件３．全部仅含一个圈的整体巡回路线都可以满足约束条件３(ui取适当值)以一特殊取值为例:ui取整数,起点编号u１＝０,第一个到达顶点的编号u２＝１,每到达一个顶点编号加一:对于总圈上的边,则必有ui－uj＝－１,约束条件变为－１＋n≤n－１,必然成立;对于非总圈上的边,因为xij＝０,则约束条件变为ui－uj≤n－１,由于左边最大值为n－１,故恒成立．[１]综上所述,约束条件３可以使形成赋权图中只含一个圈．至此,模型建立完成:minf(x)＝∑ni＝１∑nj＝１Wij*Xij,满足条件∑nj＝１Xij＝１,∑ni＝１Xij＝１,ui－uj＋nXij≤n－１,u１＝０(１≤ui≤n－１),Xij＝０或１．(i,j＝１,２,３,…n)求解可采用MATLAB搭配求解模型．

４初次实践

在模型建立完之后,进行初次实践应用．

(１)问卷调查

在不同地方进行投放问卷,采用实体问卷调查和网络问卷调查结合的形式．实体问卷发放１７０份,回收１５３份．网络问卷收回１５７份．共计３１０份．整理出有效问卷为２５４份．且大多数为学生回答．经过统计,得出了反馈数最多的的１５个民意站点(即人们认为坐公交车不方便的地方,需要增加线路)分别为:三中鹤问湖校区,向阳闸,二中,快乐城,财校,一中,冷冻厂,德化路,汽车总站,荷花垅,中茂铂宫,长虹小区,万达广场,联泰,国棉三厂．在自主绘制的九江市公交线路图上,将通过对问卷数据统计得到的十五个点所在位置进行标注,并按照从左往右的顺序依次记作V１,V２,…,V１５．(此次问卷调查仅获得各个站点信息,即模型中Vi的具体位置,无其他信息)

(２)赋权

边权影响因素包括:１．各边之间的距离．２．各边的经济价值．３．各边附近的公交线路．(即若一个边附近线路多,相应权也大)．考虑到各因素权重不同,对应赋权区间也不同.．对影响因素１,权即为两点之间图上距离(以cm为单位长度)．对影响因素２,权区间为[４.５,１２]．对影响因素３,权区间为[３,８]．最后求各因素权和即为各边的实际权大小.各边权情况如图１,图中数据已求和．其中,以第七行第八列的４３.５为例,表示７地与８地之间的权为２６.５＋１１＋６＝４３.５．以此类推．

(３)代入求解

变量Xij类似于方程组的解,将程序输入计算机后,可自动求出相应解集,无需我们去一一尝试．解出该问题的解集(取值为１的变量):{X１,４,X４,７,X７,２,X２,５,X５,６,X６,３,X３,１５,X１５,１０,X１０,９,X９,１１,X１１,１２,X１２,８,X８,１３,X１３,１４,X１４,１},对应线路为:三中鹤问湖校区→快乐城→冷冻厂→向阳闸→财校→九江一中→二中→国棉三厂→荷花垅→汽车总站→中茂铂宫→长虹小区→三中鹤问湖校区

５反思评价(对设计线路的优化)

从满意角度出发,问卷系统应更贴合民众．在公交车上及各个站点投放问卷更为合理．这样可以直接面向乘车群众,获得的民意站点更科学和普适．同时可调整问卷问题,如通过设置问题获得人们对现有的从１地去往２地的公交车设置的满意程度．若不太满意,考虑减小该边权．要采取种种措施增加人民对该线路的满意度,这些措施就尤为重要．从权方面,各边权的影响参数不应局限于距离,要扩展到道路承载能力,经济效应,人口密度分布,与其他公交车线路拟合度等等,这些都可以成为独立的建模体系．同时也都需要在实地考察的基础上合理赋权．此外,各因素权重各不相同,求和时应乘以相应系数．权区间的选取也是十分必要的．这样更符合社会价值．进行演算时,我们可能会发现:当某一条边相对距离过长,连接意义不大,而其他因素权较小,使该边权求和后总权较小了,反而可能会解出x＝１．对此,可以在赋权的时候,对在某个因素下毫无意义的边,权取为无穷大,这样可以巧妙解决问题．

６研究的切身感受

发现问题比解决问题更难,也更有意义．只有发现在有价值的问题的基础上,解决问题的办法才体现出宝贵．尽管数学建模的整体过程很有难度与深度,但是这对于社会的发展是必不可少的．社会真正的快速发展要靠数学建模的多领域渗透．数学建模在时代的发展中就显得尤为重要．

参考文献

[１]司守奎,孙玺菁．数学建模算法与应用[M]．北京:国防工业出版社,２０２１:２０-２１．

作者：李雨轩 单位：九江市第三中学