基于floyd算法的城市配送最快路径选择

《基于floyd算法的城市配送最快路径选择》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于Floyd算法的城市配送最快路径选择唐克虫钱民段丽梅王滨昆明冶金高等专科学校摘要：提出Y—种棊于车辆通行时间大数据选择最快路径的方法，充分考虑道路拥堵和交叉路口红绿灯等待时间的因素，用通行时间代替距离，采用改进的Hoyd算法来发现最快的配送路径，研宄发现该方法可以提高城市配送的效率，降低时间成木，具有较高的应用价值。关键词：大数据;城市配送;最快路径;时间成本;Floyd算法;作者简介：唐克生(1974-)，男，云南华宁人，讲师，工学硕士，主要研宂方向:物流工程技术、智能数据处理。收稿日期：2017-08-03基金：云南省教育厅项目(2015Y550)SelectionofFa

2、stestRouteinUrbanDistributionBasedonFloydAlgorithmTangKeshengQianMinDuanLimeiWangBinKunmingMetallurgyCollege;Abstract：Inthispaper,weproposedamethodfortheselectionofthefastestroutebasedonthebigdataonvehicletravellingtime,thenhavingfullyconsideredroadcongestionandthewaitingtimeatcrossroadsandtra

3、fficlights,substituteddistancewithtravellingtimeandattheend,usedtheimprovedFloydalgorithmtoidentifythefastestdistributionroute.Keyword：bigdata;urbandistribution;fastestroute;timecost;Floydalgorithm;Received：2017-08-031引言目前“最后一公里”的城市配送的效率问题己成为影响物流业发展的一个重要因素。配送路径的选择对配送的效率和成本起着关键的作用。过去，我们会选择一条最短路

4、径作为配送路径，最短路径算法主要有Dijkstra广度搜索算法、Floyd算法、A*启发式算法以及在搜索节点时加入蚁群算法和遗传算法以提高搜索的效率xn。现在，随着城市交通拥堵的加剧，人们意识到最短路径并不等于最快路径，基于对配送效率和时间成本的考虑，倾向于在配送时选择•-条最快路径。类似的研宄成果主要有对交通拥堵可能发生进行提前预测m、建立考虑天气状况、道路容量等动量的动态交通网络对出行道路进行规划和中途调整位1、引入道路拥堵因子的基于动态规划法的配送路径动态选择U1、基于交通信号的路U延迟和时间最短路径(TLBSP)的计算模型实现交通信号控制下各车最短时间路径的计算m、基于Ca

5、peCod方法计算最短时间路径的最优出发时间M等。Dijkstra广度搜索算法，是一种贪心算法，能够搜索出一条单源最短路径，即在阁中求出给定节点到其它任一节点的最短路径。其计算复杂度为0(n)cEloyd算法，能够搜索出图上的所有节点对的最短路径。其计算复杂度为o(n)，可以一次求解无向图和有向图。本文提出了一种基于道路通行时间大数据来选择最快配送路径的方法，即通过记录自有配送车辆在配送过程屮所经过的每条道路的通行时间，区分通行时段、天气条件、交通信号路口数量等影响通行时间的因素，以道路的通行时间代替距离，使用Floyd算法计算完成一趟配送任务的最快路径，即得出一条从配送中心到一次

6、配送任务的多个客户且返回配送中心的最快路径。2影响道路通行时间的2.1天气条件一些特殊的天气条件会直接影响到道路的通行速度，比如能直接导致能见度降低的大雾和沙尘天气，导致路面湿滑的雨雪天气。在城市道路的通行实例中，由于特殊天气条件导致道路通行速度降低而发生拥堵的情况较为常见。2.2通行时段机动车辆的通行速度直接和该时段的交通流量直接相关。比如高峰时段，由于交通流量增大，道路宽度等条件不足以容纳，往往造成通行缓慢，直至发生拥堵;正常时段，交通流量没有达到拥堵所需的量，则会道路通畅，不易发生拥堵。2.3交通路口数量机动车行驶到路口需要降低速度通过，且由于交通信号灯等待延误时间，常导致车

7、辆的通行时间直接增加。由于交通信号灯的红绿灯显示是动态变化的，不能提前预测，也不能加以控制，故每个路口的等待时间取值红灯等待时间的一半较为合适。如果红灯等待时间为lmin,则路门延误时间取30s,具体的取值可以视不同的城市而有所不同。本文中，天气条件、通行时段对通行的影响可以通过该种条件下通行时间的长短得到反映，交通路U的等待时间则单独标记。3最快路径选择随着城市拥堵的加剧，城市配送时选择一条最短路径已经不具有现实意义，为了提高效率和降低配送的时间成本，往往需耍选择一