基于蚁群算法的动态共享单车调度优化
|
摘要
随着共享经济的发展,共享单车逐渐走进人们的生活。为解决因共享单车出行的潮汐性而导致的资源浪费和供求关系不平衡的问题,将各调度区域内车辆数量的初始值及其变化速率考虑进约束范围,并对蚁群算法改进其禁忌表的节点选取方式,使其能够适用于求解动态共享单车调度问题,最终得到一条从调度中心出发的路径,同时能够保证调度量的最大化。实验结果表明,改进后的蚁群算法相比离散差分进化算法,在精确性和执行效率上有着显著的优势,尤其是在问题规模较大的情况下。在分别运行50次的条件下,蚁群算法成功寻得最优解的次数相较于离散差分进化算法提高了94%;在寻得最优解的条件下,蚁群算法的评价次数相较于离散差分进化算法减少了65. 4%。
With the development of shared economy,shared bikes have gradually entered people's lives. In order to solve the problem of resource waste and imbalance between supply and demand caused by the tides of sharing bicycle trips,the initial number of vehicles in each dispatching area and their changing rate are taken into account. The ant colony optimization( ACO) is modified by improving the way it selects the nodes of its taboo table so that it can be applied to solving the dynamic shared bicycle dispatching problem. Finally,a route starting from the dispatching center is obtained,while guaranteeing the maximization of scheduling capacity. The experimental results show that the improved ACO has significant advantages in accuracy and execution efficiency compared with the discrete differential evolution algorithm( DDE),especially when the scale of the problem is large. Under the condition of 50 runs respectively,the number of times that the ACO succeeds in finding the optimal solution is 94% higher than that of the DDE,and the number of evaluations of the ACO is 65. 4% less than that of the DDE under the condition of finding the optimal solution.
With the development of shared economy,shared bikes have gradually entered people's lives. In order to solve the problem of resource waste and imbalance between supply and demand caused by the tides of sharing bicycle trips,the initial number of vehicles in each dispatching area and their changing rate are taken into account. The ant colony optimization( ACO) is modified by improving the way it selects the nodes of its taboo table so that it can be applied to solving the dynamic shared bicycle dispatching problem. Finally,a route starting from the dispatching center is obtained,while guaranteeing the maximization of scheduling capacity. The experimental results show that the improved ACO has significant advantages in accuracy and execution efficiency compared with the discrete differential evolution algorithm( DDE),especially when the scale of the problem is large. Under the condition of 50 runs respectively,the number of times that the ACO succeeds in finding the optimal solution is 94% higher than that of the DDE,and the number of evaluations of the ACO is 65. 4% less than that of the DDE under the condition of finding the optimal solution.
引文
[1]周传钰.共享单车投放量测算和调度方法研究[D].北京:北京交通大学,2018.
[2]王涵霄,董明,张大力.考虑维修的共享单车调度优化研究[J/OL].工业工程与管理:1-9.https://doi.org/10.19495/j.cnki.1007-5429.2019.02.001.
[3]冯杰,史立.生鲜产品的纯电动冷藏车配送路径问题研究[J].计算机工程与应用,2019,55(09):237-242
[4]吕游,袁杰红,孙杨,等.战时物流配送车辆路径优化问题[J].控制与决策,2019,34(01):121-128.
[5]Dorigo M,Member S,IEEE,et al.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transaction on Evolutionary Computation,1996,1(1):53-66.
[6]王雷震,汪定伟,王素欣.多起讫点货物转运配送车辆调度模型及其粒子群、蚁群算法混合求解[J].信息与控制,2018,47(05):564-572
[7]李秀娟,杨玥,蒋金叶,等.蚁群优化算法在物流车辆调度系统中的应用[J].计算机应用,2013,33(10):2822-2826.
[8]张翠军,张敬敏,王占锋.基于车辆路径问题的蚁群遗传融合优化算法[J].计算机工程与应用,2008(04):233-235.
[9]郭咏梅,胡大伟,陈翔.改进蚁群算法求解带时间窗的应急物流开环车辆路径问题[J].长安大学学报:自然科学版,2017,37(06):105-112.
[10]薛羽,庄毅,顾晶晶,等.自适应离散差分进化算法策略的选择[J].软件学报,2014,25(05):984-996.
[11]贺毅朝,王熙照,张新禄,等.基于离散差分演化的KPC问题降维建模与求解[J/OL].计算机学报,2018:1-15.http://kns.cnki.net/kcms/detail/11.1826.TP.20181127.1348.002.html.
[12]Bhandari A K,Kumar A,Chaudhary S,et al.A new beta differential evolution algorithm for edge preserved colored satellite image enhancement[J].Multidimensional Systems and Signal Processing,2017,28(2):495-527.
[13]Ali Payldar Akgüngr,Ersin Korkmaz.Estimating Traffic Accidents in Turkey Using Differential Evolution Algorithm[J].Selected Scientific Papers-Journal of Civil Engineering,2017,12(1):75-83.
[14]Sakr W S,El-Sehiemy R A,Azmy A M.Adaptive differential evolution algorithm for efficient reactive power management[J].Applied Soft Computing,2017,53:336-351.
[15]龚建华.深度优先搜索算法及其改进[J].现代电子技术,2007(22):90-92.
[2]王涵霄,董明,张大力.考虑维修的共享单车调度优化研究[J/OL].工业工程与管理:1-9.https://doi.org/10.19495/j.cnki.1007-5429.2019.02.001.
[3]冯杰,史立.生鲜产品的纯电动冷藏车配送路径问题研究[J].计算机工程与应用,2019,55(09):237-242
[4]吕游,袁杰红,孙杨,等.战时物流配送车辆路径优化问题[J].控制与决策,2019,34(01):121-128.
[5]Dorigo M,Member S,IEEE,et al.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transaction on Evolutionary Computation,1996,1(1):53-66.
[6]王雷震,汪定伟,王素欣.多起讫点货物转运配送车辆调度模型及其粒子群、蚁群算法混合求解[J].信息与控制,2018,47(05):564-572
[7]李秀娟,杨玥,蒋金叶,等.蚁群优化算法在物流车辆调度系统中的应用[J].计算机应用,2013,33(10):2822-2826.
[8]张翠军,张敬敏,王占锋.基于车辆路径问题的蚁群遗传融合优化算法[J].计算机工程与应用,2008(04):233-235.
[9]郭咏梅,胡大伟,陈翔.改进蚁群算法求解带时间窗的应急物流开环车辆路径问题[J].长安大学学报:自然科学版,2017,37(06):105-112.
[10]薛羽,庄毅,顾晶晶,等.自适应离散差分进化算法策略的选择[J].软件学报,2014,25(05):984-996.
[11]贺毅朝,王熙照,张新禄,等.基于离散差分演化的KPC问题降维建模与求解[J/OL].计算机学报,2018:1-15.http://kns.cnki.net/kcms/detail/11.1826.TP.20181127.1348.002.html.
[12]Bhandari A K,Kumar A,Chaudhary S,et al.A new beta differential evolution algorithm for edge preserved colored satellite image enhancement[J].Multidimensional Systems and Signal Processing,2017,28(2):495-527.
[13]Ali Payldar Akgüngr,Ersin Korkmaz.Estimating Traffic Accidents in Turkey Using Differential Evolution Algorithm[J].Selected Scientific Papers-Journal of Civil Engineering,2017,12(1):75-83.
[14]Sakr W S,El-Sehiemy R A,Azmy A M.Adaptive differential evolution algorithm for efficient reactive power management[J].Applied Soft Computing,2017,53:336-351.
[15]龚建华.深度优先搜索算法及其改进[J].现代电子技术,2007(22):90-92.