基于dijkstra算法的城市公共自行车调配优化分析

《基于dijkstra算法的城市公共自行车调配优化分析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于Dijkstra算法的城市公共自行车调配优化分析晋民杰黄智韩智强张栩太原科技大学交通与物流学院为提高城市公共自行车的利用率，优化公共自行车调配车行车路径的交通规划。基于Matlab的Dijkstra算法，以学校周边公共自行车站点公共交通为依托工程，建立调配车辆路径优化方案，并计算分析某两点最短路径。研究成果可为公共自行车调配车最短路线选择提供参考。关键词：交通规划;公共交通;Dijkstra算法;路径优化;OptimizationAnalysisoftheAllocateRouteinUrbanPublicBicy

2、cleBasedonDijkstraAlgorithmJINMin-jieHUANGZhiHANZhi-qiangZHANGXuSchooloftransportationTransportationandlogisticsLogistics，TaiyuanUniversityofScienceandTechnology;Abstract：Inordertoimprovetheutilizationefficiencyofurbanpublicbicyclethepublicbicycleallocatecardriv

3、ingpathisoptimized.,thedeploymentofvehicleroutingoptimizationschemeusingDijkstraalgorithmunderMatlabweresetupbasedonschoolsaroundpublicbicyclesiteproject,andtheshortestpathattwopointswereanalyzedandcalculated.Researchresultscanprovidereferencefortheselectionofal

4、locationcarshortestrouteofpublicbicycle.Keyword：transportationplanning;publictransport;dijkstraalgorithm;pathoptimization;随着城市的快速发展，城镇化规模、居民消费发生较大变化，居民的交通需求增长较快，机动交通出行工具逐渐增加，给城市道路带来巨大压力，交通堵塞问题越来越严重。这种背景下，公共自行车作为一种节能、低碳、环保、快捷和经济的公共绿色交通工具应运而生［1-2］。但是，目前城市道路车辆繁多，尤其

5、在高峰时段，公共自行车的调配存在一定滞后，给居民出行带来不便。因此，本文基于Dijkstra基本理论［3］，以学校周边公井自行车站点为依托工程，分析其最短路径，旨在提高城市公共自行车的利用率。:短路径理论研宄在网络图分析中，分析起始节点和目标节点间总权和最小的路径即为最短路径［3］。1.1Dijkstra算法的提出对公共自行车城市租赁站点间进行调配安排中最为基础的工作是计算城市道路网屮各公共自行车租赁点的运行时间及租赁点间的最短距离。通过调研［4-5］,本文主要采用Dijkstra算法进行分析。Dijkstra算法M，

6、是用于寻找加权图中的任意两点之间最短路径的算法，该算法的主要思想为通过测量各租赁点间的距离，做出加权图的距离权值矩阵，由此得到加权图中每两个租赁点间的最短路径矩阵然后输出。由加权图的邻接矩阵戸化(i,j)］nXn初始，做n次递归计算，即由矩阵A(0)=B，按照相同的算法，得出矩阵A(1)=0;同理可由A(1)构造出A(2);由六(n-1)构造出A(n)函数为止。加权矩阵的i行及j列中的元素就表示从顶点i到顶点y的最短路径矩阵中的权值之和，称为加权图的距离矩阵，此外引入一个表示任意两租赁点间最短路径的后继节点矩阵R.1.

7、2调配车辆运行方式分析在调配车辆工作过程中，其行进到各个租赁点需遵守交通规则。因此，假设公共自行车调配车在行进至各交叉口处时允许U型转弯。公共自行车调配车辆在对路网屮具体行进方式的实现屮，需分析路网屮某条路段中租赁点以及路口的位置关系，对于某租赁点，引入关键前后点的概念，如图1所示。图1中不规则图形代表公共自行车租赁站点的位置，长方形代表公共自行车调配车，根据交通规则调配车靠右行驶。当租赁点1需要调配吋，调配车辆须驶入该路段，才能对租赁点进行调配服务。所以，通过定义路门A和B为路段

8、Aj租赁点的关键前后点XII。调配车

9、靠右行驶，其必定要先经过路口A再对租赁点1进行服务，因此定义路口A是租赁点1的关键前点，定义路口B是租赁点1的关键后点。如果调配车以租赁点2作为服务对象时，路UB就是租赁点2的关键前点,路门A就是租赁点2的关键后点。图1调配车服务示意图Fig.1Theservicediagramoftheschedulingcar2实例分析2.1