公共自行车优化调度算法研究

为了缓解日益加大的交通压力、提倡绿色出行理念, 公共自行车作为一种新兴的交通方式受到人们广泛的支持。但是如何使租赁站点的自行车数量与用户相匹配成了亟待解决的问题, 即如何进行车辆调度使车辆少的站点得到迅速的补充、车辆多的站点得到迅速的排解。为了更好的解决这个问题, 国内外学者对公共自行车调度系统做出一系列研究。Vogel和Mattfeld等[1]提出了一种模式化方程用来评价公共自行车动态调配对于服务水平的提升作用并为系统调配规划提供帮助;Chemla等[2]研究了公共自行车的静态系统调度问题, 建立了以成本最小的单目标多约束调配模型;董红召等[3]针对公共慢行系统中存在的公共自行车在时间与空间上分布不均衡的问题, 研究了公共慢行系统调度过程中租赁点的动态特征及其模糊时间窗约束, 建立了以满意度最大化的调度多约束调度模型。上述研究在公共自行车调度方面取得了一定的进展, 但考虑的约束条件较少且未能很好的处理调度方案与租赁点需求量的不一致性也即调度问题的动态性。

在现实生活中, 每一站点的自行车数量处于不断变化的状态, 相应的调度需求量随着时间的变化也在时刻变化, 并且在不同的时间需要进行调度的站点也是不同的。这些情况构成了车辆调度问题中的动态性, 使之具有与动态调度问题截然不同的特征。因此必须依据动态调度的特征构建相应的调度方案。从实用性的角度出发, 为了能够及时、准确地完成公共自行车调度任务, 本文针对公共自行车时空分布不均衡的问题, 从静态调度问题着手考虑系统动态性 (需求量与需求站点的动态性) , 基于顾客满意度最大化, 成本最小化提出了一种新的处理动态调度问题的算法。

一、问题描述

公共自行车调度问题是指在调配频率、调配量均不确定的情况下, 确定运输车辆进行车辆调配的路径选择, 以及各个租赁点需要调出和调入自行车的规模, 从而达到各个自行车租赁点车辆数在空间上的平衡, 满足市民的出行需。

公共自行车的调度是解决在时间和空间上的需求不均衡引发的问题。在时间上, 公共自行车借还需求与城市居民出行规律和生活节奏密切相关;在空间上, 公共自行车借还需求与租赁点用地性质及周围交通发生源出行需求密切相关。在早晚高峰时段, 各个租赁点自行车不断流动, 因此会导致一部分租赁点自行车饱和, 即无车位停车, 同时也会导致另一部分租赁点无车可租, 早晚高峰时段以历史骑行数据基础进行确定。

车辆路径问 (Vehicle R outingProblem, VRP) 是城市公共自行车运营中车辆调度问题的重要理论基础之一, 即对一系列已知的租赁点, 从车场出发, 有序的通过各租赁点, 最后返回车场, 并在满足如车辆载运量、租赁点需求量、以及有无时窗限制等约束条件下, 满足如使用车辆数最少、行驶路程最短或者时间最短的总运输成本最小的目标来确定运输路线。如图1所示。

二、模型建立

(一) 动态调度模型的处理

车辆调度优化问题依据不同的性质分为不同的种类。根据信息是否固定可分为静态优化问题和动态优化调度问题。本文研究问题中各站点的信息是动态变化的, 因此属于动态调度问题。本文从货车司机角度出发, 货车司机每完成一个租赁点的调度, 再实时地为其分配下一租赁点。由于货车司机发出分配下一租赁点的请求时, 整个调度系统可看作静态的, 故本文将为货车司机分配下一租赁点的过程看作静态调度问题, 在每一个静态调度的过程中假定此时调度需求站点与站点的调度需求量保持不变。保证每一步调度均为最优即可使得整体的调度为最优。本文将所有站点分为三类:关键点、非关键点与非调度点。关键点是指调度车辆刚好达到或将要到达的站点;非关键点为需要调度的车辆中除去关键点后剩下的站点;非调度点, 顾名思义, 是指当前不需要进行调度的站点。如此相应的将所有站点分成了三个集合S1、S2、S3。本文依据如下的策略构建调度方案:t=0时收集各个站点的信息 (包括现有自行车数量、需要调度的站点及其数量等) 依照静态优化调度模型构建调度方案;当某一调度车辆到达第一个配送站点后, 收集各站点信息并更新S1, S2, S3然后针对S2中的站点再次基于静态调度模型构建调度方案。如此就将一个完全动态的优化调度问题转化为分阶段的静态优化调度问题。

(二) 模型假设

为将现实中的公共自行车优化调度问题抽象为数学模型, 需满足以下假设:

1. 配送货车无最长行驶距离和时间限制。

2. 配送中心和各个租赁点的位置和距离已知, 并与道路形成完整的网络, 且网路不变。

3. 运输车辆从车场出发并最终回到车场。

4. 车场的货车数一定且货车的型号均相同。

5. 货车在配送过程中匀速行驶、不受交通状况影响。

(三) 静态调度模型

在公共自行车系统服务范围内, 有一个车场, 车场拥有容量为Q (辆单车) 的货车M辆, 负责对N个租赁点进行公共自行车调入与调出的运输工作。每启动一辆货车的固定成本包括车辆使用费u0和司机薪资v0, 每辆货车单位时间的运输成本为w0, 第k辆货车的运输时长为Tk (k=1, 2, …, M) 。租赁点i的车桩数为pi, t时刻的自行车数为qi (t) , 当大于阈值e1或小于阈值e2 (0表示需要调出自行车。租赁点i期望的服务时间窗为[ETi, LTi], 可接受的服务时间窗为[ai, bi]。

已知车场及各个租赁点的位置、每辆货车的容量、每个租赁点的车桩数, 要求在一定的约束条件下, 满足目标函数, 合理的对各租赁点进行调配以及运输车辆路线做出决策。

设M辆货车的编号为{n+1, n+2, …, n+m}, 待服务的n个租赁点编号为{1, 2, …, n}, 为构造数学模型, 定义以下变量的取值:

符号说明:

Q为货车的容量;M为货车总数;N为租赁点总数;u0为每辆货车的车辆使用费;v0为每辆货车司机的薪资;w0为每辆货车单位时间的运输成本;Tk (k=1, 2, …, M) 为第k辆货车的总运输时长。

ti为货车到达租赁点i的时间t0;从车库出发的时间为pi租赁点i的车桩数;qi为租赁点i的自行车数;e1、e2为 (qi/pi) 的两个阈值;ri为租赁点i的最佳自行车数;xi=ri-qi为租赁点i的需求量;fi=exi为租赁点i的服务时长 (e已知, 即fi与需求量xi成正比) ;[ETi, LTi]为租赁点i期望的服务时间窗;[ai, bi]为租赁点i可接受的服务时间窗;tij为租赁点i与j之间的运输时间。

1. 目标函数

根据以上分析, 调度模型的目标函数由式 (1) 、 (2) 构成:

其中

式 (1) 为第一优化目标, 表示调度的总成本最低, 式子右边第一项为调度的固定成本, 第二项为可变成本。

式 (2) 为第二优化目标, 表示调度的总顾客满意度最高。

式 (3) 表示第k辆货车的总配送时间。

式 (4) 表示租赁点i的顾客满意度, 的图像如下:

本文将式 (1) 、 (2) 中的两个目标函数转化为单目标函数, 即

其中, 。

2. 约束条件

为保证该调度模型符合实际运营情况, 特作以下约束:

式 (6) 表示货车在运输过程中的运载量大于等于0且不超过最大载货量。

式 (7) 表示每个租赁点仅由一辆货车服务且从租赁点i到j的货车仅有1辆。

式 (8) 表示所有从车场出来的货车均会回到车场。

式 (9) 表示从车场出发与回去的车辆数相等。

式 (10) (11) 表示每辆货车只到达所服务租赁点1次且只从所服务租赁点出发一次。

式 (12) 表示货车到达租赁点j的时间等于到达租赁点i的时间加上在租赁点i的服务时间再加上从租赁点i到租赁点j的运输时间。

(四) 高峰期的处理

本文对高峰期的调度算法不同于非高峰期, 基于徐建闽等的《公共自行车多层次分区调度方法研究, 对系统中所有租赁点分区, 并在高峰期采用多层次分区调度方法。在高峰期调度过程中, 首先将每个小区看作一个租赁点并按照上述模型为货车分配下一小区, 再对小区中的租赁点按照最短路径算法设计路线即可。

(五) 信号器

由于本文采取分阶段的方式处理动态优化调度问题, 可能会出现某一个或几个站点迟迟等不到车辆调度的情况。因此我们在每个站点设置一个信号器, 其初始值为0。当站点有调度需求但在一次调度过程 (我们将任一调度车辆从出发到下一个站点的过程叫做一次调度过程) 中没有调度车辆满足其调度需求, 信号器的值加1, 当信号器的值达到某一限度时就将派距其最近的车辆前去服务。

三、算法设计

由于本文将动态调度优化问题转化为分阶段的静态调度优化问题, 因此本文主要研究静态调度优化问题的相关算法。本文根据模型的特点, 设计相应的遗传算法求解。遗传算法是模仿生物进化优胜劣汰的规则而发展的具有良好的全局优化能力的算法。下对遗传算法的各个环节的设计进行介绍:

(一) 编码

用0代表车场, 1、2、……、n代表自行车租赁站点。

(二) 初始化

随机生成一组1到n的排列。以5个站点, 3辆配送车为例说明, 本位将解的形式写为12345代表车辆1只负责1这个站点, 车辆2的路径为由站点2到站点3, 车辆3的路径为站点4到站点5。随机将k辆车插入排列中生成一组待检验解并检验其是否符合约束条件, 若不符合则重新生成一组待检验解。直到生成一个初始种群 (解的集合) 。

(三) 适应度函数

适应度函数是衡量个体优劣, 执行算法优胜劣汰的根本依据。一般的适应度函数选取为模型的目标函数, 本模型的目标函数为双目标函数, 本文利用权重法将其转变为单目标函数, 转化后的函数即为算法的适应度函数。

(四) 选择

选择是指从群体中选取优质个体, 淘汰劣质个体的操作过程。首先计算出初始种群每个个体的适应度并按照一定的比例选取适应度最高的个体直接进入下一代, 并参与下一代适应度的比较与变异操作, 确保优秀个体不会在种群进化过程中丢失。

(五) 交叉

本文采用顺序交叉方法, 随机挑选出两个个体依据交叉概率决定是否交叉。若不交叉则不产生新个体, 若交叉则随机产生交叉点进行交叉。例如父代的两个个体为M=435126, N=621543。随机产生的交叉点为3, 则按照如下操作进行交叉:

将M的前三个基因放在N的前面, 将N的前三个基因放在M的前面。如此构成了M1=621435126, N1=435621543, 在由后至前将重复的基因去掉构成了一组新的个体。

(六) 变异

为了避免最终的结果陷入局部最优, 还需要对种群执行变异操作。与交叉操作类似的, 随机选取一个个体根据变异概率决定是否变异, 若执行变异操作则将某一位置的基因与本个体中随机选取的基因进行位置交换。

(七) 终止遗传

在经过选择、交叉、变异操作后形成了新一代种群, 如此继续下去在达到最大的遗传代数时或适应度函数值变化很小时算法终止并输出最终结果。

四、实验及结果分析

以美国明尼苏达州的自行车租赁系统为研究对象。该区域内有205个自行车系统服务点。由于没有明确的调度中心及调度车辆, 本文设调度中心在自行车租赁服务点中心并有3辆服务车辆。假定车辆使用费u0=100元/天、司机薪资v0=25元/h、单位时间运输成本为w0=40元/h、调度服务车辆的容量为20辆且平均速度为20km/h。

通过对某一天内所有站点以1小时为时间间隔的总借车数据和总还车数据进行分析, 可知每小时租赁的需求情况。其中无论在什么时刻借车数总是超过还车数的, 这要求租赁站点有一定的车辆储备且有合适的调度方案来应对供需不平衡的局面。同时在8-9点、12-13点、17-18点借还车数量都出现了锐增, 达到了一定时段内的高峰时刻。由于不同时刻的自行车租赁情况具有不同的特征:普通时刻自行车的租赁情况较为分散而高峰时刻的租赁情况较为集中, 因此本文将整体的调度方案分为高峰期的调度方案和普通时刻的调度方案。

对于高峰时期, 将所有的站点分为上层调度区域, 其中每个调度区域内有相应的小区, 小区表现为相同的特征 (缺车或多车) 。针对高峰时期8-9点具体的分区方案如表1所示。

针对小区内的调度方案, 按照分区的原理可知小区内的站点间距离短同时考虑到小区内站点较少, 故直接采用最短路径算法求解。对于小区间的调度方案将每个小区视为一个站点, 将小区内的调度问题转化为6个站点间的调度方案, 采用遗传算法求解。调度方案如表2所示。

对于普通时刻, 考虑到实际情况以时刻6-7点为例求解, 6点时主要站点数据如表3所示。主要站点间的距离通过各站点的经纬度测量得出, 如表4所示。

由于本文建立的静态调度模型中采用的是双目标多约束规划, 在具体的计算过程中需要将多目标转化为单目标规划方法。多目标转化为单目标的方法多种多样, 主要有优选法、线性加权法、平方和加权法、分层序列法等, 为了方便直观地处理此问题本文采用线性加权法将由满意度和成本构成的双目标转化为单目标。

具体地, 对成本函数做消除量纲处理取成本满意度的权值分别为0.7和0.3.将站点相关数据代入分阶段的静态调度模型, 根据遗传算法计算调度方案。具体的调度方案如表5所示。

由图4可见, 运算结果在迭代次数0-25次之间骤降, 在25次之后虽略有波动但总体趋于平稳因此将遗传代数设置为300是合理的。具体的调度方案如表5所示。

由表5的调度方案可知, 调度需求较大的站点基本上都被纳入了调度方案, 且总体的满意度较高。因此基本认为该方案可以应对动态调度问题, 是解决动态调度问题的可行方案。

五、结束语

针对城市公共自行车系统在调度问题上存在的时间与空间上的不平衡, 从静

态调度问题入手进行研究, 通过分析调度过程中动态性的来源探究合理的动态调度方案。将动态调度问题分解为一系列的静态调度问题, 在静态调度问题上, 建立了以调度成本最低和服务满意度最大为目标的求解调度方案的调度模型。通过遗传算法求解一系列的静态调度方案构建所要求的动态调度方案, 为调度方案的确定提供了一种较为合理的方法。

摘要：近年来公共自行车越来越多, 其调度方式直接影响着企业的经济效益, 因此公共自行车优化调度成为了企业十分关心的问题。本文基于遗传算法提出了一种新的处理动态调度问题的方法。通过实时更新各个租赁点的状态, 确定特殊时刻的调度策略, 本文将动态调度问题转化为静态调度问题进行求解。本文又考虑到高峰期可能存在调度滞后的问题, 在高峰期采用不同于非高峰期的多层次分区调度方法进行调度。

关键词：遗传算法,多层次分区调度,优化调度最短路径算法

参考文献

[1] Vogel, Patrick, Torsten Greiser, and Dirk Christian Mattfeld. Understanding bikesharing systems using data mining:Exploring activity patterns.[M] Procedia-So-cial and Behavioral Sciences20, 2011:514-523.

[2] Chemla, Daniel, Frédéric Meunier, and Roberto Wolfler Calvo. Bike shar-ing systems:Solving the static rebalancing problem.[M]Discrete Optimization10, 2013, no. 2:120-146.

[3] 吴满金, 董红召, 刘冬旭等.公共自行车多目标动态调度建模与算法研究[J].机电工程, 2015, 32 (7) :1006-1010.

[4] 张建国.城市公共自行车车辆调配问题研究[D].成都:西南交通大学, 2013.

[5] 段凤华.带软时间窗约束的开放式车辆路径问题及其应用[D].长沙:中南大学, 2009.

[6] 徐建闽, 秦筱然, 马莹莹.公共自行车多层次分区调度方法研究.[J]交通运输系统工程与信息, 2017, 17 (1) :212-219