《公共自行车交通系统调度算法》由会员分享，可在线阅读，更多相关《公共自行车交通系统调度算法（7页珍藏版）》请在金锄头文库上搜索。
1、公共自行车交通系统调度算法刘登涛;方文道;章坚民;郭明泽 【摘 要】针对公共自行车交通系统的静态车辆调度问题,以运输成本最少为目标建 立公共自行车交通系统调度模型,提出了一种将模拟退火算法融合到遗传算法中的 混合启发式算法来求解该模型,增强算法的全局搜索能力和效率.通过实例结果表明, 优化后运输车辆行驶路程比优化前减少了50,说明遗传模拟退火算法具有良好的 鲁棒性和收敛性，适合解决车辆的优化调度问题For the public bicycle system static vehicle scheduling problem, this paper proposes a public bicyc
2、le scheduling model with the target of transportation costs at least. It proposes an algorithm with simulated annealing algorithm integrated into genetic algorithm and it enhances the global search capability and efficiency. The example result shows that the optimized route with a reduction of 50%.
3、It shows that the genetic simulated annealing algorithm has a good robustness and convergence and it is better for solving vehicle scheduling problem.【期刊名称】计算机系统应用年(卷),期】2011(020)009【总页数】5页(P112-116)关键词】 公共自行车交通系统;车辆调度;遗传算法;模拟退火作 者】 刘登涛;方文道;章坚民;郭明泽【作者单位】杭州电子科技大学电子信息学院,杭州 310018;杭州电子科技大学电 子信息学院,杭州 31
4、0018;杭州电子科技大学电子信息学院,杭州 310018;杭州电子 科技大学电子信息学院,杭州 310018【正文语种】中文公共自行车交通系统（Public Bicycle System , PBS ）是指由公司在大型居住区、 商业中心、交通枢纽、旅游景点等客流集聚地设置公共自行车租赁点，随时为不同 的人群提供适于骑行的公共自行车，并根据使用时间的长短征收一定额度费用，以 该服务系统和配套的自行车路网为载体，提供公共自行车出行服务的城市交通系统1。PBS由公共自行车租赁点、公共自行车、调度中心、运输车辆、运输车辆停 车场以及通信系统等组成。作为城市交通的组成部分，PBS能有效解决公交系统 “
5、最后一公里”难题，并具有以下优点:1）无污染；2）机动灵活；3）停放方便，停 车场占地面积少。杭州市从2008 年5月开始运行公共自行车交通系统以来，公共 自行车已经成为市民和游客出行的重要交通工具，目前杭州市已有1000 多个公共 自行车租车点。但是，由于公共自行车的流动性，杭州市公共自行车交通系统存在 时间和空间上分布不均匀的问题2，具体表现在:1）某些租赁点在某些时刻自行车 数量过少，用户不能及时借到自行车；2）某些租赁点在某些时刻自行车数量过多， 用户不能及时归还自行车。因此，如何合理调度公共自行车，均衡公共自行车对完 善公共交通体系、提升城市交通的服务水平具有重要的意义。根据调度前信
6、息是否完全已知，可以将车辆调度问题分为静态车辆调度问题和动态 车辆调度问题3-5。公共自行车交通系统的调度问题是一种动态车辆调度问题， 由于动态车辆调度问题的复杂性，许多学者已经提出将动态车辆调度问题转化为静 态车辆调度问题进行求解，李兵6等引入虚拟任务点与相关约束后，将客户需求 随时间变化的动态车辆路径规划问题划分为一系列的静态车辆调度问题。Jia Yongji采用滚动时调度方法在公共自行车车辆调度中起着关键作用。本文主要研 究某区域某时刻（早高峰之前）的公共自行车调度问题，属于静态车辆调度问题， 以运输成本最小为目标建立公共自行车调度模型，利用遗传模拟退火算法进行求解1 问题描述 已知杭州
7、市某区域各租赁点一个普通工作日早高峰之前的自行车调度需求如表 1， 其中正数表示该租赁点需要供出自行车，数值为多余的自行车数量，负数表示该租 赁点需要供入自行车，数值的绝对值表示缺少的自行车数量。各个租赁点的位置及 道路情况如图 1，租赁点位置在图中用带圆圈的数字所示，圆圈中数字代表租赁点 序号。字代表路线长度（单位:米）。其中6号和30号租赁点紧邻运输车的停车场 如果从这两个停车场中派1辆运输车去各个租赁点采集多余的自行车并分配给缺 少车辆的租赁点，最后返回其中任意一个停车场，则该选择什么样的行车路径和工 作顺序（已知一辆公交车最多可同时存放 60辆自行车）2 模型的建立拥有最大负荷为q的辆
8、运输车，从指定的停车场出发，负责对各租赁点进行自行 车的需求调度服务，完成任务后回到某个停车场，各个租赁点之间的距离以及各自 的需求量预先都已知。设G二1,2,3.n为所有租赁点的集合，n为租赁点的数目，停车场为6号和30号 租赁点附近；V二1,2,3.m，m为运输车辆的数目。C为运输车辆的固定成本， Qi为车辆的最大载重量；如果车辆i被使用，则二进制变量ui为1,否则为0。 租赁点i需要请求的量为li，在服务租赁点i之前，即将服务的车辆j的当前载重 量为 rij（1i m,1j n）o表1 自行车调度需求表租赁点序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 自
9、行车 需求量 12 16 -20 -42 -25 26 31 -12 -20 -13 -20 -18 -7 -19 62租赁点序号 1617 18 19 20 21 22 23 24 25 26 27 28 29 30 自行车需求量 22 -18 -11 -1 2 -2115 17 -16 0 -14 32 6 -19 55图1 各租赁点的位置及道路情况对于两个不同的租赁点i和j来说，a ij表示两者之间的最短距离8。如果车辆k 在服务完i后再服务j，则为1,否则为0。模型的目标函数即运输成本包括车辆的固定成本与行驶成本。运输成本(记为Z) 的数学模型如下:式(1)是目标函数，表示最小化运输成
10、本；式(2)规定了从停车场出来的车辆数量最 大不超过m ;式(3)规定了每条路径的起点和终点都必须是停车场；式(4)和式(5)规 定了每个租赁点都服务一次且只服务一次；式(6)规定了每次服务都能完成并且不 能超过车辆的最大载重量。由于 15号租赁点的数值为62 ，即需要供出的自行车 数量为62辆，所以不可能一次性完成任务，因此在设计算法的时候要另行考虑。3 算法设计在智能优化算法中，遗传算法(Genetic Algorithm，简称GA )具有收敛速度快 的优点，但是具有局部搜索能力较差并容易早熟收敛的致命弱点。相反，模拟退火 算法(Simulated Annealing，简称SA )能通过概
11、率突跳方式避免陷入局部最小 并最终趋于全局最优，但是收敛速度比较慢。基于GA和SA具有很强的互补性， 将SA和GA有机结合则能增强算法的全局搜索能力和效率。本文采用一种改进的 遗传模拟退火算法来求解公共自行车调度问题。3.1 遗传模拟退火算法的结构流程 本文提出的遗传模拟退火算法思想是以遗传算法运算流程为主体流程，融入模拟退 火机制来调整优化群体9,10 。其流程如图2所示。图2 遗传模拟退火算法流程3.2 适应度函数 由于要求的是最少的运输成本，是一个最小值问题，因此在设计适应度函数时要把 原始目标值转换为适应度值，以确保优秀个体具有大的适应值。通过下式的尺度变 换可以将目标值转换为适应度值
12、，即:其中，I为当前种群的第i个染色体，Fitness(I )为适应度函数值，D max为当前 种群的最小目标值，D min为当前种群的最小目标值，Di为需要转换的目标值， a为开区间(0,1)内的正实数。使用a可以防止上式被整除，还可以将选择行为 从适应度值比例选择调整为纯随机数选择。如果染色体间适应度值的差距较大，则 采用适应度值比例选择；如果区间相对较小，则选择趋向于在相互竞争的染色体中 进行随机选择。3.3 选择、交叉和变异操作采用轮盘赌操作对适应度值进行选择。首先生成随机数a(0a1),然后再按 照下式进行选择。其中，x j为群体中的第j个个体，f(xj)为第j个个体的适应度值，n为
13、自行车租赁 点数量，pop- size为群体大小，通过该操作可以选择出需要繁殖的父代群体。采用单点交叉和均匀变异算子，交叉、变异概率采用自适应的pc和pm，计算表 达式如下:式中，fm ax是群体中最大的适应值，favg是每代群体的平均适应度值， f是要交叉的二个个体中较大的适应度值，f是要变异个体的适应度值，且Ov k1,k2,k3,k41。3.4 模拟退火操作首先选取一个足够大的初始温度TO,因为要使得算法在合理的时间内搜索尽可能 大的解空间，只有足够大的T0才能满足这个要求；接着设定一个合理的退火率， 温度控制参数Tk的下降函数为Tk +1=aTk，其中衰减参数是一个略小于1的系 数；最
14、后终止温度Tf应该设置为足够小。3.5 算法说明由于 15号租赁点需要供出的自行车数量为 62，超出运输车的最大载运量，所以 需要分两次对15号租赁点的自行车进行运送。基于此，本文将15号租赁点的自 行车数量设为0,然后增加两个租赁点（31号和32号租赁点），其坐标与15号 租赁点重合，且满足31号和32号租赁点的自行车数量之和为62。3.6 参数设定 在使用智能优化算法求解问题时,参数的控制十分重要。对以上遗传模拟退火混合 算法进行多次测试后,最终选择算法的参数如下表（表2 ） 。表2 算法参数种群大小（ pop-size ） 100迭代系数（ g ） 200初始温度（ T0 ）1000降温
15、速度（a） 0.95交叉概率（pc ） 0.30变异概率（pm ） 0.40初始接收概 率（pr） 0.9994 实例验证 实例要求从两个停车场中任意派1辆运输车辆去各个租赁点采集多余的自行车并 分配给缺少车辆的租赁点,最后返回其中任意一个停车场。因此,总共有4种情 况,如表3所示。表3 运输车行驶路线运输车行驶路线 初始行驶路程 优化后的行驶路程 优化后的 行驶路线30号租赁点附近停车场出发,返回原停车场 51540 27340 30-26-2120-19-28-27-29-24-18-10-7-8-6-1-9-11-2-3-13-31-5-32-4-16-23-22-17- 12-14-3
16、030号租赁点附近停车场出发,返回6号租赁点附近停车场6号租赁点附 近停车场出发,返回30号租赁点附近停车场52840 27140 30-26-21-20-19-17-22-23-16-4-13-32-5-31-14-12-28-27-29-24-18-6-7-9-11-10-2-3-1-8- 655340 29040 6-1-8-7-9-10-11-2-3-31-5-30-17-12-14-16-32-13-4-23-22- 21-28-27-29-24-18-19-20-26-306号租赁点附近停车场出发，返回原停车场 56640 27940 6-1-2-3-5-31-14-32-13-4-16-23-22-17-12-20-21-30-26-24- 29-27-28-19-18-10-11-7-9-8-6 由表3可以看出，无论是哪一种情况，优化后
