基于遗传算法的公共自行车调度优化

刘兆仁，徐冠宇，尹 航

（1.西南交通大学 经济管理学院，四川 成都 610031；2.四川旅游学院 信息与工程系，四川 成都 610100）

基于遗传算法的公共自行车调度优化

刘兆仁1，徐冠宇1，尹 航2

（1.西南交通大学 经济管理学院，四川 成都 610031；2.四川旅游学院 信息与工程系，四川 成都 610100）

伴随着低碳经济的发展和人们环保意识的不断增强，城市居民对于绿色出行越来越重视，城市公共自行车逐渐在各大中型城市普及，如何高效调度公共自行车成为亟待解决的问题。在对公共自行车调度问题进行分析的基础上，利用遗传算法建立VRP模型，最后采用标准算例针对算法进行检验，结果表明遗传算法具有较高效率，能够有效求解自行车调度模型。

公共自行车；遗传算法；VRP；调度优化

1 引言

中国是典型的人口大国，是世界上拥有自行车数量最多的国家。截至2016年底，全国自行车保有量达3.7亿辆，自行车在中国人民的日常生活中扮演重要的角色。近年来，随着居民财富不断增加和生活质量的不断提高，私家车出行成为许多居民首选的交通方式。然而，私家车的增加给城市发展造成诸多问题，交通拥堵、环境恶化等已经成为我国大中型城市亟待解决的问题。

为此，许多城市开始大力发展公共交通，并采取诸如建设公交专用道、换乘免费等一系列措施引导市民选择公共交通方式出行。这些措施对于缓解交通拥堵问题起到不错的效果。但由于公交站点的数量总是有限的，很难保证乘客走出家门或到站后就能马上到达目的地，这也就形成了“城市最后一公里”问题。为改善乘客公共交通出行质量，提高公共交通选择粘性，国内部分城市开始试行“城市公共自行车租赁系统”。欧美等发达国家的实践表明，发展城市公共自行车租赁系统能够与公共交通相辅相成，从根本上解决城市交通拥堵问题。

公共自行车交通系统（Public Bicycle System，PBS）一般由政府和自行车企业合作构建、运营。其中，政府起主导作用，负责制定PBS宏观规划；自行车企业则着眼于微观，负责布点、调度、运行和维护。租赁点大多设置在人流较大的地方，如居住区、公共交通或轨道交通站点附近、旅游景点、学校等等，主要服务于短途出行。自2008年以来，我国一、二线城市开始普及公共自行车，公共自行车逐渐成为城市居民出行的重要组成板块。与此同时，城市公共自行车系统在发展过程中也面临诸多问题，如运营模式、布局选址和车辆调度等。能否妥善解决城市公共自行车系统发展过程中遇到的难题对于发展我国城市公共交通具有重大意义。

为解决城市公共自行车调度问题，本文运用遗传算法，建立解决静态VRP问题模型，并采用标准算例进行优化求解。

2 公共自行车调度分析

公共自行车调度是指在租赁点处自行车过多或不足的情况下，使用调度车辆有序通过这些租赁点进行自行车补给或调出，目标是保证城市公共自行车系统能够达到持续、相对稳定的均衡状态。本文采用静态调度的方式，每天晚上由营运商派出车辆将公共自行车站点的车辆复原，以便市民出行[1]。

2.1 发展机遇

（1）交通需求。随着社会经济的高速发展和居民生活水平的不断改善，城市私家车拥有量急剧增长，尽管近年来一、二线城市普遍采取限号出行措施，但交通拥堵问题依然未能很好地解决。虽然我国近年来不断开发城市公共交通，地铁和快速公交的开通一定程度上缓解了城市交通压力，但公共自行车的发展是对于现有公共交通的补充，对于完善“最后一公里”出行具有重要的意义，城市公共自行车系统的出现是应当前交通发展的需求而生，具有广阔的市场[2]。

（2）政策支持。发展绿色出行交通受到当前环保政策的支持，国家“十二五规划”明确提出保护环境的方针政策，发展城市公共自行车系统符合当前社会发展的趋势[3]。

2.2 存在的问题

（1）运营模式。目前公共自行车运营模式随着各地区经济文化的差异而采取了不同的方式，有的城市采用政府主导模式，政府在运营中发挥主导作用，但往往技术更新方面存在缺陷；有些城市采用企业主导模式，能够最大化经济效益，但会在一定程度上忽视居民需求。

（2）网络规划。大部分城市目前的公共自行车租赁点较少，网络规划不充分，不能够完全满足日益增长的群众需求，也在一定程度上影响了运营公司在后期阶段的车辆调度。

（3）运营调度。当前城市自行车车辆调度措施仍然存在一定的问题，在车辆使用密集时段经常会出现无车可借的尴尬情况，在部分集中站点，也会出现无处还车的情况。车辆的调度对于客户满意率造成极大影响。

2.3 运营调度的特性

城市公共自行车具有时间分布性和空间分布性两大特点。时间分布性是指在同一个区域，自行车流量峰值一天内将会达到四次，其中两次大峰值出现在早晚上下班高峰期，两次小峰值则出现在中午前后。城市公共自行车系统是为了迎合城市居民出行的需求而建立的，其运营时间与城市居民出行的时间有极强的相关性。在早高峰阶段，自行车的流向大多数是写字楼、产业园等；与之相反，在晚高峰时，自行车则从写字楼、产业园流向居住区。可见，自行车流具有较为明显的潮汐性特点[4]。

空间的分布性是指同一时间内不同空间自行车需求量的不同。早晨设立于住宅区和郊区的自行车租赁站点的租用需求较大，位于地铁口和商业区的租赁点还车需求较大，相反，到晚上，市民由商业区和公交枢纽向住宅区流动。随着时间的变化，整个城市范围内的自行车会有明显的空间位移，在不同的时间段，会有不同的空间分布，具有一定的规律可循。

通过以上分析，在两次大高峰时段，不同租赁点之间实现了公共自行车的循环流动，但由于早晚高峰之间时间间隔过长，自行车流动方向性和时间性过于集中，导致一些租赁点公共自行车出现饱和、而其他租赁点却没有自行车可以租用的情况。因此，针对这一现实问题，对公共自行车调度进行优化，以促进公共自行车调度实现全面智能化，不仅能够有效节约道路资源、缓解交通拥堵以及由此产生的一系列社会问题，而且对于促进城市健康发展有重要的意义。

3 构建公共自行车系统静态调度问题模型

3.1 问题描述

静态公共自行车调度问题是指租赁点的自行车调度不是根据动态需求实时改进，而是在每一天的特定时刻，统一对城市区域内的所有站点进行调度，以满足租赁点的需求。由于现在城市公共自行车系统与大数据系统紧密结合，运营商对于租借出去的车辆流向以及租赁点剩余车辆有精确的实时统计，能够根据租赁点的不同需求进行分类服务。

本文假设运营商对于车辆供给不足的租赁点进行统一配送，由中心车场进行逐一访问，并且最终返回车场。

（1）每个站点只允许被访问一次；

（2）所有车辆从中心车场出发，然后再返回到起点；

（3）每个站点的调度任务必须由一辆车完全满足。

3.2 模型构建

本文将以成本最低为目标建立模型，成本主要包括车辆的旅行距离，车辆行驶的距离越长，成本越高。

为了方便叙述，本文引入以下符号：

N0租赁站点数集合{1,...,n}；

N站点集合，包括车场和租赁站点{0,1,...,n,n+1}；

k配送车辆集合{1,...,k}；

C配送车辆的容量上限；

T配送车辆运行时间上限；

在上述条件基础上，以成本函数最低为目标，建立以下模型：

Z表示该模型的目标函数，该模型以成本最低为目标函数，即车辆在路程中的消费最低；约束（1）表示所有的站点都将被访问；约束（2）、（3）表示车辆将从配送中心出发，并将返回配送中心；约束（4）表示车辆流守恒；约束（5）表示避免子环约束，该模型中不存在子循环路径；约束（6）表示配送车辆所配送数量不能超过被访问站点的需求总和；约束（7）表示为0-1整数变量。

3.3 模型求解策略

以往的调度方法主要分为两种：基于优先规则的启发式算法和基于搜索的算法。然而，这两者在解决公共自行车优化调度问题时缺点都比较明显，即它们在解决小规模调度问题时是有效的，但面对规模较大的调度问题时却无能为力。

遗传算法[5]由美国J.H.Holland教授在20世纪70年代提出。该算法是基于生物进化理论的自适应随机搜索算法，对于求解车辆调度问题十分有效。车辆调度问题是遗传算法应用十分成熟的领域，该算法求解车辆调度问题的基本步骤为：编码操作、产生初始种群、计算适应度函数、遗传算子（包括选择、交叉和变异）、终止规则。

3.3.1 编码。车辆调度问题的编码方式分为两种：路径表示法和相邻表示法。本文采用第一种编码方式。举例说明：设某区域共设有9个自行车租赁点，其中一个可行闭合路径为[1 4 3 7 2 5 8 6 9 1]，则对应的染色体编码可表示为1 4 3 7 2 5 8 6 9。

3.3.2 产生初始种群。初始种群是进行遗传进化操作的第一代种群，由N个个体组成。本文初始种群通过随机方式生成，将初始种群规模设定为N=30，由此则随机生成30个个体，每个个体代表了一个初始解，由于暂没有进行遗传进化，因此这一代种群中个体适应度值偏低。3.3.3 计算适应度函数。适应度函数是目标函数在遗传算法中的反映。在遗传算法中，适应度值大的个体将有更大概率将优良基因信息传递给下一代。本文的目标函数是成本最低，因此本文采用成本的倒数作为适应度函数，分母中加1的作用是为了避免成本为0的特殊情况。个体的适应度值可表示为

3.3.4 遗传算子

选择：本文依据种群中不同个体的适应度值采用轮盘赌方式进行选择，该方案能够保证适应度高的个体以更大的概率被选中。

交叉：在遗传算法中，新个体的产生主要依靠交叉操作。本文进行交叉操作时，为使子代依旧为可行解，采用部分匹配交叉法（PMX）：对两个父代随机产生2个位串交叉点，两点间为交叉匹配区域，然后基于匹配区域内基因的映射关系重新排列区域外重复基因。举例如下：

父代染色体

父代1：138丨27丨4965 父代2：726丨45丨8139

交叉匹配

匹配1：138丨45丨4965 匹配2：726丨27丨8139

子代染色体

子代1：138丨45丨2967 子代2：546丨27丨8139

其中，子代1和子代2即为通过部分匹配交叉法获得的新一代个体。

变异：交叉操作能够使子代保持父代的优良特性，但也会导致算法过早收敛，陷入局部最优。变异操作能够弥补这一缺点，扩大遗传算法的搜索空间。本文采用对换变异法：首先，随机选择染色体的两个基因，然后交换位置，完成对换变异，举例如下：

变异前：2 3 8 6 7 1 9 5 4

变异后：2 3 9 6 7 1 8 5 4

3.3.5 终止条件设定。遗传算法本质上是随机搜索算法，因此难以找到准确的收敛性判别标准。本文采用遗传算法进化代数作为终止条件。当进化代数达到预先设定值3 000代时，算法终止，并输出适应值最大的个体作为最优解。

4 实证分析

根据上述模型，本文采用标准算例（数据来源于Rainer-Harbach等的标准实例）来进行分析。首先建立公共自行车系统调度优化模型，然后利用遗传算法进行求解。本文的遗传算法采用C语言开发，其测试与运行均利用CPU 2.5G、内存为6G和Windows 7操作环境下的计算机进行。另外，由于不同的参数设置对遗传算法性能有较大影响，因此测试了不同参数组合下的运算效果，最终选择种群规模为30、交叉率为0.7、变异率为0.05。通过运行，得到该问题的解。其中车辆行驶距离采用标准算例，各站点自行车需求数量由算法随机生成，设站点需求总量为100辆，设装配车辆容量为40，表1为租赁站点距离矩阵及需求表。

将遗传算法运行20次，其中最优结果为537，最差结果为543，遗传算法最优调度计划见表2，通过观察可以发现，该算法具有稳定性，能够有效解决公共自行车配送问题。

表1 租赁站点距离矩阵及需求表

表2 遗传算法最优调度计划

5 结论

本文针对城市公共自行车系统的调度问题，利用遗传算法建立了VRP模型，通过遗传算法对车辆调度模型进行求解，发现遗传算法在求解城市公共自行车调度问题上具有良好的效率。未来还可以进一步研究在静态调度问题上扩展，考虑动态需求下的车辆调度情形，还可以考虑调配车辆同时兼有装货和卸货功能，完成同一个站点的装卸货问题。

[1]Dantzig G B,Ramser J H.The truck dispatching problem[J]. Management science,1959,6(1):80-91.

[2]丁涛,向升斌,李表奎,等.基于改进粒子群算法的生鲜电商冷链终端配送车辆路径问题研究[J].物流技术,2016,35(2):68-72.

[3]何博,卢青.城市公共自行车系统运营模式浅析[J].交通企业管理,2012,27(4):49-51.

[4]Erdogan G,Laporte G,Wolfler Calvo R.The static bicycle relocation problem with demand intervals[J].European Journal of Operational Research,2014,238(2):451-457.

[5]Lenstra J K,Kan A H G.Complexity of vehicle routing and scheduling problems[J].Networks,1981,11(2):221-227.

[6]周磊.基于节约里程法的配送路线优化研究—以苏宁电器为例[J].物流技术,2016,35(1):109-116.

Study on Optimal Public Bike Dispatching Based on Genetic Algorithm

Liu Zhaoren1,Xu Guanyu1,Yin Hang2
(1.School of Economics&Management,Southwest Jiaotong University,Chengdu 610031; 2.Department of Information&Engineering,Sichuan Tourism College,Chengdu 610100,China)

In this paper,on the basis of an analysis of the dispatching of public bikes,we used the genetic algorithm to build the VRP model,then applied it to a standardized numerical example for verification and at the end,according to the findings,demonstrated the efficiency and validity of the genetic algorithm in solving the bike dispatching model.

public bike;genetic algorithm;VRP;dispatchingoptimization

U484;O224

A

1005-152X(2017)02-0078-04

10.3969/j.issn.1005-152X.2017.02.019

2017-01-08

刘兆仁（1990-），男，硕士研究生，主要研究方向：项目优化调度；徐冠宇（1992-），男，硕士研究生，主要研究方向：物流与供应链；尹航（1985-），通讯作者，男，博士，工程师，主要研究方向：项目管理。