共享单车的调度算法

2018-05-11 07:28尹诗颖骆虎周骏申佳讯
课程教育研究 2018年11期

尹诗颖 骆虎 周骏 申佳讯

【摘要】共享单车极大方便了公众短距离出行和公共交通换乘,更好地满足公众出行需求、有效解决城市交通出行“最后一公里”问题、缓解城市交通拥堵等方面发挥了积极作用,推动了分享经济发展。因此,本文对共享单车进行数据分析与建模,研究如今共享单车的调度问题。

【关键词】共享单车静态调度模型 遍历网络结构图 A?鄢算法

【中图分类号】F270.7 【文献标识码】A 【文章编号】2095-3089(2018)11-0256-01

1.共享单车供应能力

通过实际收集的数据,我们通过正态分布模拟出不同的骑行情况,从而求解出了总的单车供应能力最大时的分布情况。

2.共享单车静态调度模型的建立

我们以骑行时长为各区域间距离的衡量标准,得到了各区域间估计的距离。本文将以总成本费用最低建立共享单车静态调度模型。这里的总成本费用分为两个部分:第一是调度车辆从中心车场到各区域的总路程费用;第二是工作人员装载和投放共享单车的工资。

为了简化模型,我们近似认为中心车场在某一区域附近。以调度车辆运行总成本最低为目标函数,建立共享单车静态调度模型如下:

3.共享单车静态调度模型的求解

3.1 A?鄢算法原理

算法思想:

A?鄢算法的核心部分,在于估价函数的设计。在选择当前结点的下一个考察节点时引入了估价函数f(x)。

f(x)=g(x)+h(x)

f(x)表示从起始节点x到节点的一条最佳路径的实际代价加上从结点x到目标节点的一条最佳路径的代价之和。g(x)就是从起始节点到节点x之间最小代价路径的实际代价,h(x)则是从x节点到目标节点路径的估计代价。

A?鄢算法流程

(1)生成一个只包含开始单车网络分布节点n0的搜索图G,把n0放在一个叫OPEN的列表上。

(2)生成一个列表CLOSED,它的初始值为空。

(3)如果OPEN表为空,则失败退出。

(4)选择OPEN上第一个节点,把它从OPEN中移入CLOSED,该节点为n。

(5)如果n是目标节点,顺着G中,从n到n_{0}的指针找到一条车辆运输路径,获得解决方案,成功退出(该指针定义了一个搜索树,在第7步建立)。

(6)扩展节点n,生成其后继结点集M,在G中,n的祖先不能在M中。在G中安置M的成员,使他们成为n的后继。

(7)从M的每一个不在G中的成员建立一个指向n的指针(例如,既不在OPEN中,也不在CLOSED中。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m,如果到目前为止找到的到达m的最好路径通过n,就把它的指针指向n。对已在CLOSED中的M的每一个成员,重定向它在G中的每一个后继,以使它们顺着到目前为止发现的最好路径指向它们的祖先。

(8)按递增f?鄢值,重排OPEN(相同最小f?鄢值可根据搜索树中的最深节点来解决)。

(9)返回第3步。

3.2 A?鄢算法求解模型

我们根据A?鄢算法,使用C++编程求解单车调度总成本最小值,就能给出投放单车的具体方式和路径。

4.结论

我们客观上构建了共享单车静态调度模型。每一天的单车使用情况都存在很大的不确定,但是在短时间内满足正态分布,这是我们能给求解出最低单车调度费用的出发点。还有,我们使用的A?鄢算法比较适合于处理大量數据,这使我们的模型能适用于分析大量骑行数据下的单车调度问题。

参考文献:

[1]李锦霞.公共自行车调度优化研究[D].长沙理工大学.2013.