论文部分内容阅读
摘要：针对城市公共自行车系统的现状，通过逐步遍历找到每个站点的最优规划方案，然后对站点分类并根据区域内公共自行车站点的分布图，将规划路线问题拟化为TSP问题，并用普里姆算法生成最小生成树解决该问题，对路线进行多次优化，得出最终结果。并用价值模型对优化前后路线进行比较。最后通过实例，验证了所设计的模型和算法取得了预期的效果，证明了所用算法符合该模型的求解，且通过该模型所求得的规划方案是合理的。
关键词：逐步遍历；TSP问题；最小生成树；普里姆算法；多次优化
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）14-0098-03
Abstract：The status of the city public bicycle system， and gradually to traverse through to find the optimal planning of each site and then on the site classification and according to the regional public self station distribution map， the route planning problem simulation as traveling salesman problem （TSP）， and prim algorithm to generate the minimum spanning tree to solve the problem， the route was optimized for many times， to obtain the final results. The comparison of the route before and after optimization is made by the value model.. Finally through an example to verify the model and the algorithm designed in this paper has achieved the desired results. It is proved that the algorithm used in this paper conforms to the solution of the model and the model obtained from the planning scheme is reasonable.
Key words：Step through；TSP problem；Minimum Spanning Tree；Prim’s algorithm；Several optimization
随着城市公共自行车的普及，在一定程度上缓解了城市交通压力，对节能减排、减少污染和可持续发展有重大意义，城市公共自行车将会是未来城市发展的重要区域。但是，目前城市公共自行车系统也存在着很多不足，例如无法在高峰期满足用户的需求。所以，对城市公共自行站点进行再规划是非常重要的，不仅能缓解部分交通压力，还能提升整个城市公共交通系统的服务质量，最大限度满足人们对出行便利性的要求。
城市公共自行车站点规划就是在尽可能节省运营成本的前提下，研究对各个站点的公共自行车进行有效调配，使之在时间和空间上达到均衡的最佳状态（即可借还状态）。规划前期对站点信息采集可分为站点位置信息采集和站点实时数据采集，其中位置信息采集通过获取站点的遍布位置并转换为坐标图；实时数据采集包括站点当前车辆数、停车位数量等。通过对历史数据的计算，得到每个时间段每个站点所需调配的自行车数量，统计出每次调配所需的总数量和各个站点所需数量。
1 相关理论
1.1 TSP问题
旅行商问题（Traveling Salesman Problem，即TSP）：对于城市[V={v1，v2，…，vn}]的一个访问顺序为[T={t1，t2，…，tn}]，其中[ti=Vi=1，...，n]，且[tn 1=t1]，则问题[minT∈Ωi=1ndti，ti 1]，其中[Ω]为这n个城市不重复排列的所有可能回路。求解TSP 问题的常用算法为蚁群算法，该算法是一种自适应、正向反馈的方法，可促使整个系统向最优解进化。
1.2 普里姆算法
普里姆算法就是从一个最小的连通子网开始，逐步扩大到最小生成树。即：设 G=（V，E）是连通网络，[V={v0，v1，…，vn}]。不失一般性，设[v0]为起始点，U 是入选子网的顶点集，T 是入选子网的边集。
[U ={v0}；T =Φ；while（U ≠V ）{ c（ u’， v’）=min∪v∈V U{min∪u∈Uc（u，v）}； T=T∪{（u’， v’）}； U=U∪{v’}}]
2 公共自行车站点规划模型构建
构建公共自行车站点规划模型主要分为两部分：一是每个站点的规划方案，二是整块区域的规划路线模型。
2.1 站点规划方案
站点分类后，得到整块区域所有站点的坐标图，将规划路线拟化为TSP问题，通过构建最小生成树TSP方案模型来确定整个区域的规划线路。
通过抽样计算，发现站点之间最近路程约为站点直线距离的[1 32]倍，于是得到：[Dab=（1 3）xa-xb2 ya-yb22]，[Dab]表示[ab]两点间的近似实际最短距离。
因为需要节省人力成本，所以将为每个区域制定一套合理的路线方案，用最小生成树解决来解决不重复的环形TSP问题。用普里姆算法构造最小生成树。在含有n（n>1）个顶点的完全连通无向图中，任意选择一个顶点[Vi]作为起始点，在与顶点[Vi]相关联的n-1条边中，选择一条权值最小的边[ei]，此边可连接[Vi]及图中另一个顶点[Vj]，然后在与[Vi]或[Vj]相关联除[ei]以外的所有边中，选择权值最小的边[ej]，[ej]又可连接另外一个顶点（边的选则还要保证树中没有环的产生）。依次求出所有的可连接n个顶点的n-1条边，因为在此生成树中的每一条边均为不会生成环的，且权值最小的连接顶点的边，因此这棵生成树为含有n（n>1）个顶点的完全连通无向图的最小生成树。由于不同类站点之间可能相距很近，所以得到规划路线后，需再对其二次优化，即人工优化。 通过上述方法得到每条规划路线后，计算每条路线所需时间，要求每条规划路线所花的时间能在规定时间内完成，即：[6030000Dab 2N<90]，其中[N]表示每条路线上的公共自行车站点个数。
2.3价值模型
为了进一步研究各个路线是否具有较大的价值，建立一个表示该站点不健康度的模型。因为各个站点无论是不能归还状态还是不能借出状态都是不理想状态，所以将站点剩余车辆等于该站点总车辆数的一半的情况视作最健康状态，而距离这个状态越远，表示该站点越不健康。得到站点不健康度[Hi]的关系式：[Hi=Zi’-Zi]，其中[Hi]表示第[i]点的不健康度；[Zi’]表示第[i]点的实际可租自行车辆数；[Zi]：表示第[i]点的最佳可租自行车辆数。
然而这个不健康度就是表示需要管理的量，所以价值[Vi]可表示为：[Vi=HiLi]，其中[Vi]表示去第[i]服务点的价值；[Li]表示去[i]站点的距离。整个方案线路的总价值可以表示为：[V?=HiL?]
3 实证分析
根据上述公共自行车规划模型，现以某市某小区某站点为例进行规划模型的验证，其中每个站点都编有数字代号。
1）建立公共自行车站点的位置坐标图，用不同颜色区分，如图1所示。绿色点表示平淡区，代表基本能保持借还平衡，所以每天只需去规划一次。紫色点表示生活区，红色点表示工作区，代表每天需要规划两次，且时间都在早上和傍晚。
2）利用MATLAB求解，得到各区域的一个较优的回路方案，黄色回路表示管理工作区的站点路线，红色回路表示管理生活区的站点路线，蓝色回路表示管理平淡区的站点路线。同时，可以发现每个方案的路线都会出现几个其他方案的点，可对其进行优化，结果如图2所示。
3）将各路程上的站点带入公式
4 结束语
本文旨在研究公共自行车站点选址规划和调度优化方法，并将优化结果再进行人工优化，通过比较得到最好的规划模型，从而降低了规划时间和运行成本，使公共自行车站点能最大程度满足市民的需求。通过研究，创新公共自行车系统运营管理的体制和保障措施，就能更好地促进公共自行车系统及城市公共交通的进一步发展。
参考文献：
[1] 李黎辉，陈华，孙小丽.武汉市公共自行车租赁点布局规划[J].城市交通，2009，7（4）：39-44.
[2] 王剑文，戴光明，谢柏桥，等.求解TSP问题算法[J].计算机工程与科学，2008（30）：72-75.
[3] Krykewycz Gregory R，Puchalsky Christopher M，Rocks Joshua. Defining a Primary Market and Estimating Demand for Major Bicycle-Sharing Program in Philadelphia，Pennsylvania[J]. Transportation Research Record. Octobe，2010：117-124.
[4] Kalten brunner Andreas， Meza Rodrigo， Grivolla Jens. Urban cycles and mobility patterns： Exploring and predicting trends in a bicycle-based public transport system [J]. Pervasive and Mobile Computing，August，2010：455-466.
[5] Maria Bordagaray， Angel Ibeas， Luigi dell’Olio*. Modeling user perception of public bicycle services [J]. Procedia - Social and Behavioral Sciences， 2012：1308-1316.
[6] 潘海啸，汤謁，犮贤敏，等.公共自行车交通发展模式比较[J]. 城市交通，2010，11（6）：40-4.
[7] Liu Xingcai， Rui Song， Li Zhen， et al. Thought of Bicycle Traffic Development under Low - Carbon Background[C]. Proceedings of the Third International Conference on Transportation Engineering，2011：3280-3285.
[8] 余详宣，崔国华，邹海明.计算机算法基础[M]. 2版. 武汉：华中科技大学， 1998.
[9] 喻菡.遗传算法的求解TSP 的研究[D]. 成都： 西南交通大学，2006： 12-15.
关键词：逐步遍历；TSP问题；最小生成树；普里姆算法；多次优化
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）14-0098-03
Abstract：The status of the city public bicycle system， and gradually to traverse through to find the optimal planning of each site and then on the site classification and according to the regional public self station distribution map， the route planning problem simulation as traveling salesman problem （TSP）， and prim algorithm to generate the minimum spanning tree to solve the problem， the route was optimized for many times， to obtain the final results. The comparison of the route before and after optimization is made by the value model.. Finally through an example to verify the model and the algorithm designed in this paper has achieved the desired results. It is proved that the algorithm used in this paper conforms to the solution of the model and the model obtained from the planning scheme is reasonable.
Key words：Step through；TSP problem；Minimum Spanning Tree；Prim’s algorithm；Several optimization
随着城市公共自行车的普及，在一定程度上缓解了城市交通压力，对节能减排、减少污染和可持续发展有重大意义，城市公共自行车将会是未来城市发展的重要区域。但是，目前城市公共自行车系统也存在着很多不足，例如无法在高峰期满足用户的需求。所以，对城市公共自行站点进行再规划是非常重要的，不仅能缓解部分交通压力，还能提升整个城市公共交通系统的服务质量，最大限度满足人们对出行便利性的要求。
城市公共自行车站点规划就是在尽可能节省运营成本的前提下，研究对各个站点的公共自行车进行有效调配，使之在时间和空间上达到均衡的最佳状态（即可借还状态）。规划前期对站点信息采集可分为站点位置信息采集和站点实时数据采集，其中位置信息采集通过获取站点的遍布位置并转换为坐标图；实时数据采集包括站点当前车辆数、停车位数量等。通过对历史数据的计算，得到每个时间段每个站点所需调配的自行车数量，统计出每次调配所需的总数量和各个站点所需数量。
1 相关理论
1.1 TSP问题
旅行商问题（Traveling Salesman Problem，即TSP）：对于城市[V={v1，v2，…，vn}]的一个访问顺序为[T={t1，t2，…，tn}]，其中[ti=Vi=1，...，n]，且[tn 1=t1]，则问题[minT∈Ωi=1ndti，ti 1]，其中[Ω]为这n个城市不重复排列的所有可能回路。求解TSP 问题的常用算法为蚁群算法，该算法是一种自适应、正向反馈的方法，可促使整个系统向最优解进化。
1.2 普里姆算法
普里姆算法就是从一个最小的连通子网开始，逐步扩大到最小生成树。即：设 G=（V，E）是连通网络，[V={v0，v1，…，vn}]。不失一般性，设[v0]为起始点，U 是入选子网的顶点集，T 是入选子网的边集。
[U ={v0}；T =Φ；while（U ≠V ）{ c（ u’， v’）=min∪v∈V U{min∪u∈Uc（u，v）}； T=T∪{（u’， v’）}； U=U∪{v’}}]
2 公共自行车站点规划模型构建
构建公共自行车站点规划模型主要分为两部分：一是每个站点的规划方案，二是整块区域的规划路线模型。
2.1 站点规划方案
站点分类后，得到整块区域所有站点的坐标图，将规划路线拟化为TSP问题，通过构建最小生成树TSP方案模型来确定整个区域的规划线路。
通过抽样计算，发现站点之间最近路程约为站点直线距离的[1 32]倍，于是得到：[Dab=（1 3）xa-xb2 ya-yb22]，[Dab]表示[ab]两点间的近似实际最短距离。
因为需要节省人力成本，所以将为每个区域制定一套合理的路线方案，用最小生成树解决来解决不重复的环形TSP问题。用普里姆算法构造最小生成树。在含有n（n>1）个顶点的完全连通无向图中，任意选择一个顶点[Vi]作为起始点，在与顶点[Vi]相关联的n-1条边中，选择一条权值最小的边[ei]，此边可连接[Vi]及图中另一个顶点[Vj]，然后在与[Vi]或[Vj]相关联除[ei]以外的所有边中，选择权值最小的边[ej]，[ej]又可连接另外一个顶点（边的选则还要保证树中没有环的产生）。依次求出所有的可连接n个顶点的n-1条边，因为在此生成树中的每一条边均为不会生成环的，且权值最小的连接顶点的边，因此这棵生成树为含有n（n>1）个顶点的完全连通无向图的最小生成树。由于不同类站点之间可能相距很近，所以得到规划路线后，需再对其二次优化，即人工优化。 通过上述方法得到每条规划路线后，计算每条路线所需时间，要求每条规划路线所花的时间能在规定时间内完成，即：[6030000Dab 2N<90]，其中[N]表示每条路线上的公共自行车站点个数。
2.3价值模型
为了进一步研究各个路线是否具有较大的价值，建立一个表示该站点不健康度的模型。因为各个站点无论是不能归还状态还是不能借出状态都是不理想状态，所以将站点剩余车辆等于该站点总车辆数的一半的情况视作最健康状态，而距离这个状态越远，表示该站点越不健康。得到站点不健康度[Hi]的关系式：[Hi=Zi’-Zi]，其中[Hi]表示第[i]点的不健康度；[Zi’]表示第[i]点的实际可租自行车辆数；[Zi]：表示第[i]点的最佳可租自行车辆数。
然而这个不健康度就是表示需要管理的量，所以价值[Vi]可表示为：[Vi=HiLi]，其中[Vi]表示去第[i]服务点的价值；[Li]表示去[i]站点的距离。整个方案线路的总价值可以表示为：[V?=HiL?]
3 实证分析
根据上述公共自行车规划模型，现以某市某小区某站点为例进行规划模型的验证，其中每个站点都编有数字代号。
1）建立公共自行车站点的位置坐标图，用不同颜色区分，如图1所示。绿色点表示平淡区，代表基本能保持借还平衡，所以每天只需去规划一次。紫色点表示生活区，红色点表示工作区，代表每天需要规划两次，且时间都在早上和傍晚。
2）利用MATLAB求解，得到各区域的一个较优的回路方案，黄色回路表示管理工作区的站点路线，红色回路表示管理生活区的站点路线，蓝色回路表示管理平淡区的站点路线。同时，可以发现每个方案的路线都会出现几个其他方案的点，可对其进行优化，结果如图2所示。
3）将各路程上的站点带入公式
4 结束语
本文旨在研究公共自行车站点选址规划和调度优化方法，并将优化结果再进行人工优化，通过比较得到最好的规划模型，从而降低了规划时间和运行成本，使公共自行车站点能最大程度满足市民的需求。通过研究，创新公共自行车系统运营管理的体制和保障措施，就能更好地促进公共自行车系统及城市公共交通的进一步发展。
参考文献：
[1] 李黎辉，陈华，孙小丽.武汉市公共自行车租赁点布局规划[J].城市交通，2009，7（4）：39-44.
[2] 王剑文，戴光明，谢柏桥，等.求解TSP问题算法[J].计算机工程与科学，2008（30）：72-75.
[3] Krykewycz Gregory R，Puchalsky Christopher M，Rocks Joshua. Defining a Primary Market and Estimating Demand for Major Bicycle-Sharing Program in Philadelphia，Pennsylvania[J]. Transportation Research Record. Octobe，2010：117-124.
[4] Kalten brunner Andreas， Meza Rodrigo， Grivolla Jens. Urban cycles and mobility patterns： Exploring and predicting trends in a bicycle-based public transport system [J]. Pervasive and Mobile Computing，August，2010：455-466.
[5] Maria Bordagaray， Angel Ibeas， Luigi dell’Olio*. Modeling user perception of public bicycle services [J]. Procedia - Social and Behavioral Sciences， 2012：1308-1316.
[6] 潘海啸，汤謁，犮贤敏，等.公共自行车交通发展模式比较[J]. 城市交通，2010，11（6）：40-4.
[7] Liu Xingcai， Rui Song， Li Zhen， et al. Thought of Bicycle Traffic Development under Low - Carbon Background[C]. Proceedings of the Third International Conference on Transportation Engineering，2011：3280-3285.
[8] 余详宣，崔国华，邹海明.计算机算法基础[M]. 2版. 武汉：华中科技大学， 1998.
[9] 喻菡.遗传算法的求解TSP 的研究[D]. 成都： 西南交通大学，2006： 12-15.