1. 引言
信息技术的发展对公共交通影响越来越大，近几年来，定制公交开始进入公众视野，相对于传统公交，定制公交具有相对灵活的运行方式，能提供便捷、环保、舒适的合乘服务 [1]。目前国内对于定制公交的研究主要集中在定制公交的优势、存在的问题、运营模式、票价制度、系统评价及运行方案等方面 [2]，而定制公交的线路规划和站点选择的研究相对不足。
在定制公交线路规划研究中，根据起点和终点的不同，有“一对一”、“多对一”、“多对多”等模式。文献 [3] 使用蚁群算法求解“多对一”定制公交线路方案，对于多起点多终点的“多对多”定制公交模式，一般将问题归结为车辆路径问题(VRP) [4]，使用蚂蚁算法对路径求解；通过构建解空间树 [5]，可以将多起点多终点问题转换为单起点单终点问题，用蚂蚁算法求解路径；文献 [6] 在交通条件动态变化状态时，提出了一种基于遗传算法和蚁群算法的动态最短路径算法；文献 [7] 运用层次分析法建立道路综合权值模型，A*算法求解最短路径。在定制公交的站点选择研究中，文献 [4] 使用K-means聚类算法求解站点，文献 [8] 对K-means聚类算法进行改进提出K-means++聚类算法求解站点，文献 [9] 提出了一种考虑乘客分布和线路方向的站点分割聚类算法，以最大最小蚁群算法进行求解。
当前线路规划的研究本质上都是求解起点和终点之间的最小距离路径，定制公交的线路规划需要在路径最短和服务更多市民中进行权衡；当前城市管理中站点的设定都有严格的规定，不能随意设置。针对目前定制公交存在的路径规划、站点选择方面的问题，本文提出一种新型定制公交乘车模式，依托现有公交站点组成的公交网络，定制公交只在公交站点停车，公众选择最近公交站点乘车，城市公交站点是长期选择的结果，基本满足公众就近出行需要，这样就解决了站点选择的难题；将路口作为路径规划的节点，所有站点均处于相邻的两个路口之间，通过改进A*算法实现路径的动态规划，该路径规划既考虑距离因素，也考虑乘车人数因素，达到便捷乘车和经济效益的统一，提高了公众出行的效率。
2. 定制公交路径规划算法
2.1. 启发式搜索算法
路径规划中常用启发式搜索算法，如：蚂蚁算法、遗传算法、A*算法等，启发式搜索就是在状态空间搜索中对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标，这样可以省略大量无谓的搜索路径，提高效率。
在启发式搜索中，对位置的估价是十分重要的，估价是用估价函数表示，算法表示为：f(n) = g(n) + h(n)
其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。
2.2. A*算法
A*算法是一种典型的启发式搜索算法，建立在Dijkstra算法的基础之上，广泛应用于游戏地图、现实世界中，用来寻找两点之间的最短路径 [10]。A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，A*算法能够高效地找到两点之间的最优路径。但在A*算法中，往往通过一个函数来计算每个节点的权值，而这个函数，则决定算法的搜索效率。
2.3. A*算法存在的问题
A*算法广泛应用于各种路径搜索问题，虽然A*算法优势比较明显，寻路过程中可以更智能地分析最优路径并减少搜索的冗余节点。但是，A*算法在路径规划应用中经常用来求解最短路径 [7] [10] [11]，而定制公交运行中既需要考虑距离、时间因素，又需要考虑乘客乘车便捷、运营公司的经济效益，所以求得最短路径不一定是最优的路径。
如图1所示，设A站为起点，B站为终点，从A开始，有两个分支，分别到达C站和D站。
假设一：设C站等待人数五人，D站等待人数三人，从A到C300 m，从A到D300 m，此时如果想减少成本增加收入，应选择最优策略即从A站到C站，而传统的A*算法也有可能选择A到D。
假设二：设C站等待人数五人，D站等待人数五人，从A到C200 m，从A到D300 m，此时如果想减少成本增加收入，应选择最优策略即从A站到C站。
假设三：设C站等待人数三人，D站等待人数五人，从A到C300 m，从A到D400 m，此时如果想减少成本增加收入，应选择最优策略即从A站到D站，而传统的A*算法则会选择较短的A到C，造成成本的增加。
总之，A*算法虽然可以规划最短的线路，但并未考虑综合成本的问题，所生成的最短线路不一定是在成本和便捷方面最优的路线。
3. 改进的A*算法
针对A*算法在定制公交路径规划时无法综合考量多种因素的问题，本文提出一种改进的A*算法。现有公交站点组成定制公交运输网络，定制公交只在公交站点停车，公众选择最近公交站点乘车，解决站点选择问题；所有公交站点都处于运行方向不同的一个路段中，路段的端点为路口，将路口作为路径规划的节点，在传统A*算法基础上，将预计乘车人数与估价函数结合，估价函数中f(n)含有距离和人数信息，同时估计的成本函数h(n)也含有距离和人数信息，在路径规划时将不必要路径方向剪枝，提高搜索效率。
3.1. 路网结构
将实际的路网结构抽象为二维网格，根据运行方向成为有向图，节点为路口，节点与节点之间为路段，路段结构如图2所示，C、D、E、F为公交站点，A、B为路口，路口记录所在方位、进入方向的预计乘车人数、坐标数据和路段长度，如：在路口A中记录路段AB数据为：站点C、D的预计乘车人数，路段AB在A的右方，坐标数据为[X,Y]，路段AB长度。
3.2. 估价函数
在A*算法中需要估算h(n)，h(n)估算方法为：
1) 依次搜索n节点相邻节点，计算邻接点与n组成的向量和n与终点组成的向量的夹角，如果夹角大于90度，说明远离终点而去，则不进行搜索；
2) 对于符合条件的邻接点，计算邻接点到终点的欧几里得距离，得到h(n)。
改进后的A*算法需要计算预计乘车人数，预计乘车人数估算方法为：
1) 搜索n节点的有效邻接点，统计n与人员乘车终点向量和n与终点向量夹角；
2) 如果向量夹角小于45度，则统计该乘车人，否则不统计；
3) 统计各方向预计乘车人数x。
估价函数为：f(n) = g(n) + h(n)，其中g(n)为成本函数，g(n) = g(v) + cost(v,n)，v为n的父节点，g(v)为起点到v的实际综合成本，n为v的邻接点，cost(v,n)为计算成本，在路径规划中由v到n的距离和预计乘车人数组成，修改g(n)为：
g(n) = g(v) + α*vn + (β/(1 + x))*vn
其中：vn为v到n的距离，x为v到n路段预计乘车人数，α、β为调整参数，取值范围为[0,1]，α = 0、β = 1时，以乘车人数为重要计算标准，α = 1、β = 0时，为传统的A*算法。h(n)为n节点到终点的欧几里得距离。
3.3. 改进后的A*算法
改进后A*算法以实际公交站点为乘车地点，一个路段的乘车人数统计在路段入口，公交站点不进行位置计算与搜索，参与路径规划的只是路网中的路口；改进后的A*算法见算法1。
算法1：改进的A*算法。
输入：起点src(x0,y0)，终点dst(x,y)，路网结构grid(x,y)；
输出：规划路径path；
说明：g(n)计算n节点的g值，f(n)计算n节点的f值，set_father(n)设置n节点的父节点，get_father(n)获得n节点的父节点，adjvex(n)n节点的邻接点。
(1) open={},close={},path={}
(2) open←src,g(src)=0，f(src)
(3) while(open<>null){
(4) v=f_min(open) //取open表中最小f值的节点
(5) if(v==dst) break
(6) close←v，open→v
(7) while(adjvex(v)<>null){
(8) m=adjvex(v)
(9) if(angle(
,
)<=90){
(10) x=person(
)//计算vm路段乘车人数
(11) g(m)= g(v)+vm+(1+x)*vm
(12) h(m)=dist(
) //m到dst的欧几里得距离
(13) f(m)=g(m)+h(m) //计算m点的f值
(14) if(m not in open and m not in close)
(15) set_father(m)←v
(16) open←m
(17) else
(18) if( m in open and g(m)
(19) g_old(m)=g(m)
(20) set_father(m)←v
(21) if( m in close and g(m)
(22) g_old(m)=g(m)
(23) set_father(m)←v
(24) open←m
(25) close→m }
(26) } //adjvex(v) 循环结束
(27) } //open<>null循环结束
(28) if(v==dst)
(29) path←v,m=v
(30) while((m<>src){
(31) m= get_father(m)
(32) path←m}
(33) print path
(34) else
(35)print搜索失败
改进的A*算法在定制公交路径规划时有可能规划出的路线不是最短路径，但考虑了乘车人数的因素，既为乘车人最大程度的提供便利，又提供了公交运营方的收益，是适应定制公交开行的意图的；改进的A*算法在路径选择时，对与行进方向背离的路径进行剪枝处理，提高了搜索效率。
4. 改进后的A*算法与传统A*算法的对比
实际城市路网结构大致为表格状，依此建立数据模型，使用c++语言编写传统A*算法与改进后的A*算法程序，选择多个测试样例，进行结果对比。
测试例1，数据模型如图3表示，假设以C为起点，G为终点，标注在路线上的数字为两站点之间的距离，标注在点附近的为去某一站的人数。
Figure 3. Test example 1 road network structure model
图3. 测试样例1路网结构模型
运行结果如表1所示，从C到G，用传统A*算法与改进A*算法规划出的路径长度是相同的，但由于应用了改进后的估价函数和剪枝算法，乘车人数最优，搜索的点次也变少了，更快的规划出路线。
Table 1. Test example 1 algorithm comparison table
表1. 测试样例1算法对比表
改进后的A*算法搜索路径长度为4.8与传统A*算法相等，乘车人数6人比传统A*算法多1人，提高20%，搜索次数由23次减少到11次，减少无效搜索52%。
测试例2，数据模型如图4所示，假设以C为起点，G为终点，标注在路线上的数字为两站点之间的距离，标注在点附近的为去某一站的人数。
Figure 4. Test example 2 road network structure model
图4. 测试样例2路网结构模型
运行结果如表2所示，从C到G，用传统A*算法与改进A*算法规划出的路径长度是相同的，但由于应用了改进后的估价函数和剪枝算法，乘车人数最优，搜索的点次也变少了，更快的规划出路线。
Table 2. Test example 2 algorithm comparison table
表2. 测试样例2算法对比表
改进后的A*算法搜索路径长度为4.8与传统A*算法相等，乘车人数7人比传统A*算法多2人，提高40%，搜索次数由23次减少到13次，减少无效搜索43%。
测试例3，数据模型如图5所示，假设以C为起点，G为终点，标注在路线上的数字为两站点之间的距离，标注在点附近的为去某一站的人数。
Figure 5. Test example 3 road network structure model
图5. 测试样例3路网结构模型
运行结果如表3所示，从C到G，用传统A*算法与改进A*算法规划出的路径长度是相同的，但由于应用了改进后的估价函数和剪枝算法，乘车人数最优，搜索的点次也变少了，更快的规划出路线。
Table 3. Test example 3 algorithm comparison table
表3. 测试样例3算法对比表
改进后的A*算法搜索路径长度为4.8与传统A*算法相等，乘车人数10人比传统A*算法多1人，提高11%，搜索次数由23次减少到11次，减少无效搜索43%。
从测试样例看，改进的A*算法在路径规划中能找到最优路径，搜索路径的乘车人数要优于传统A*算法，并且提高了搜索效率。
5. 结束语
本文针对传统A*算法在定制公交线路规划时存在的问题，提出一种改进的A*算法，以现有公交站点组成的定制公交运输网络，定制公交只在公交站点停车，解决站点选择问题，将路口作为路径规划的节点，在传统A*算法基础上，将预计乘车人数与估价函数结合，估价函数中f(n)含有距离和人数信息，同时成本函数g(n)也含有距离和人数信息，在路径规划时将不必要路径方向剪枝，提高搜索效率。改进后的A*算法简化了节点模型、改进了估价函数，将距离和乘车人数都作为影响估价函数的因素，既提高了路径搜索效率，又能得到综合效益最优路线。
基金项目
山东省自然科学基金资助项目(编号：ZR2017BF043)；山东省大学生创新创业训练计划项目(编号：S201910429064)。