基于改进量子进化算法的车货供需匹配方法研究

doi:10.16381/j.cnki.issn1003-207x.2016.12.019

中国管理科学 ›› 2016, Vol. 24 ›› Issue (12): 166-176.doi: 10.16381/j.cnki.issn1003-207x.2016.12.019

• 论文 • 上一篇

基于改进量子进化算法的车货供需匹配方法研究

牟向伟, 陈燕, 高书娟, 姚思雨

大连海事大学交通运输管理学院, 辽宁大连 116026

收稿日期:2016-01-28 修回日期:2016-05-31 发布日期:2017-03-07
通讯作者: 牟向伟(1982-),男(汉族),辽宁人,大连海事大学交通运输管理学院,博士,研究方向:数据挖掘、知识发现,E-mail:muxiangwei@dlmu.edu.cn. E-mail:muxiangwei@dlmu.edu.cn
基金资助:
国家自然科学基金资助项目（71271034）；国家科技支撑计划课题（2014BAH24F04）；中国博士后科学基金资助项目（2014M551063）；辽宁省教育厅科技研究项目资助（L2014203）；辽宁省社会科学规划基金项目（L14BGL012）；中央高校基本科研业务费专项资金资助（3132016046）

Vehicleand Cargo Matching Method Based on Improved Quantum Evolutionary Algorithm

MU Xiang-wei, CHEN Yan, GAO Shu-juan, YAO Si-yu

Transportation Management College, Dalian Maritime University, Dalian 116026, China

Received:2016-01-28 Revised:2016-05-31 Published:2017-03-07

摘要/Abstract

摘要： 为了提高货运供需匹配效率，建立了一种车货供需匹配数学模型，描述了车货匹配问题的目标与相关约束，对量子进化算法进行设计与改进用于对此问题求解，提出了有约束惩罚的适应度衰减方法，解决了量子群初期无强可行解时最优量子个体的选择问题，引入量子群成熟度对量子进化算法的退出机制进行改进。在实验中，使用改进的量子进化算法和标准遗传进化算法进行对比，并对算法参数进行优化，实验中量子进化算法表现出更好的收敛速度，准确性和稳定性，但是量子群规模存在“瓶颈问题”，更大规模的量子群对算法优化效果并不明显且需要耗费更长的计算机时间，量子旋转角增量与算法收敛速度正相关，与全局搜索能力负相关。结果表明，改进的量子进化算法可以高效地搜索到较为优秀的车货匹配方案，为车主和货主推荐较为合理的车货供需信息资源。

关键词: 车货匹配, 量子进化算法, 物流信息平台

Abstract: In order to solve the logistics supply and demand information asymmetry and improve the efficiency of logistics business docking, a lot of public logistics information platforms or systems have been built to post and share the logistics information. There exists relative research about how platforms passively response user's query for logistics supply and demand information, but the research about how to match vehicle and cargo information proactively and intelligently is very few.Vehicle and cargo matching problem is regarded as a kind of combinatorial optimization problems in this paper, a mathematical model has been established, and the model declares two decision variables:the constraints and the objective function. A kind of quantum evolutionary algorithm has been designed and proposed to solve the vehicle and cargo matching problem, which is improved by the method of the attenuation fitness with constraint punishment. An index, Quantum Swarm Maturity Value (QSMV), is introduced as a reference criteria for the quantum evolutionary algorithm exit. Vehicle and cargo matching problem based on quantum evolutionary algorithm can be solved into six steps, including:quantum group initialization, fitness calculation, selection of the optimal quantum individual, the judgment of algorithm exit, quantum group evolution and the optimal individual decoding. In the experiment, experimental data is given a set composed of 5 vehicles and 7 cargos. The exact solution is obtained by using the traversal method, which takes 6 hours and the fitness is 0.283226. An optimal solution is obtained by the quantum evolutionary algorithm, which takes 0.656 seconds and the fitness is 0.2832. Furthermore, the improved quantum evolutionary algorithm is compared with the standard genetic algorithm, experiment results show that quantum evolutionary algorithm's convergence speed is increased by 58%, average error is reduced by 86% and stability is increased by 32%. Experiment results also show that quantum group scale has "bottleneck" problem, larger quantum group scale does not improve the algorithm performance obviously, and quantum rotation angle increment is positive correlation to algorithm convergence speed, and negatively correlated to global search ability.The results show that the improved quantum evolutionary algorithm can efficiently get the optimal solution for the vehicle and cargo matching problem, and enable the public logistic information platform to intelligently recommend reasonable supply or demand information for different users, and help users reduce the idle vehicles rate and empty-run rate, and improve the utilization ratio of logistics information resources.

Key words: vehicle and cargo matching, quantum evolutionary algorithm, logistic information platform

中图分类号:

U116.2

牟向伟, 陈燕, 高书娟, 姚思雨. 基于改进量子进化算法的车货供需匹配方法研究[J]. 中国管理科学, 2016, 24(12): 166-176.

MU Xiang-wei, CHEN Yan, GAO Shu-juan, YAO Si-yu. Vehicleand Cargo Matching Method Based on Improved Quantum Evolutionary Algorithm[J]. Chinese Journal of Management Science, 2016, 24(12): 166-176.

参考文献

[1] Namjoshi J, Gupte A. Service oriented architecture for cloud based travel reservation software as a service[C]//Proceedings of 2009 IEEE International Conference on Cloud Computing. Bangalore, September 21-25, 2009.

[2] 李永平. 基于物联网技术的甩挂物流信息平台建设研究[D].西安:长安大学,2014.

[3] 汪传雷,朱绍平,万一荻,等. 基于Web3.0的物流信息平台社区模型构建研究[J]. 情报理论与实践,2016,39(7):127-135.

[4] 李俚,周晓蓉. 物流陆运业务交易平台撮合算法研究与实现[J]. 制造业自动化,2013,35(9):88-90+101.

[5] 顾佳婧. 基于语义网技术的车货匹配系统[D].北京:清华大学,2013.

[6] 梁艺多,翟军,袁长峰. 基于本体推理的物流配送系统的构建[J]. 物流技术,2015,34(5):255-258.

[7] 李慧. 配载型物流信息服务平台的车货供需匹配研究[D].北京:北京交通大学,2015.

[8] 孙承志,杨祎,吴建彬,等. 云物流供需匹配智能决策模式的分析与设计[J]. 物流技术与应用,2014,19(4):130-132.

[9] 李俚,周晓蓉. 物流陆运业务交易平台撮合算法研究与实现[J]. 制造业自动化,2013,35(9):88-90+101.

[10] 杨珺,冯鹏祥,孙昊,等. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学,2015,23(9):87-96.

[11] 葛显龙,许茂增,王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学, 2013,21(1):125-133.

[12] 陈玉光,陈志祥. 基于准时送货和最小耗油的配送车辆路径问题研究[J]. 中国管理科学, 2015,(S1):156-164.

[13] Errico F, Desaulniers G, Gendreau M, et al. A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times[J]. European Journal of Operational Research, 2016, 249(1): 55-66.

[14] Lv Xuan, Liu Xianhui, Zhao Weidong, et al. Design and implementation of detection and tracking system for bagged cargo[C]//Proceedings of the 2nd International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Washington D C, August 26-28, 2010.

[15] 胡贵彦,杜志平,孙卫华,等. 货物配载方法最优化的研究[J]. 物流技术,2009,28(8):86-88+107.

[16] 靳志宏,于波,侯丽晓. 厢式货车配载与配送的联合优化[J]. 交通运输工程学报, 2010,10(3): 95-100.

[17] Xu Xiaofeng, Zhang Wei, Li Ning, et al. A bi-level programming model of resource matching for collaborative logistics network in supply uncertainty environment[J]. Journal of the Franklin Institute, 2015, 352(9): 3873-3884.

[18] 周正威,涂涛,龚明,等. 量子计算的进展和展望[J]. 物理学进展,2009,29(2):127-165.

[19] 张建明. 基于改进量子进化算法的生产调度问题研究[D].上海:华东理工大学,2013.

[20] 国强,孙宇枭. 改进的双链量子遗传算法在图像去噪中的应用[J]. 哈尔滨工业大学学报,2016,48(5):140-147.

[21] 樊富有,王瑞锦. 三值量子遗传算法及其应用[J]. 电子科技大学学报,2016,45(1):123-128.

[22] Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 Congress on Evolutionary Computation,IEEE,July 16-19, 2000, 2: 1354-1360.

[23] Wang Ling, Wu Hao, Tang Fang, et al. A hybrid quantum-inspired genetic algorithm for flow shop scheduling[C]//Huang Deshuang, Zhang Xiaoping, Huang Guangbin: Advances in intelligent computing, Berlin Heidelberg: Springer, August 23-26,2005: 636-644.

[24] Li Binbin, Wang Ling. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(3): 576-591.

[25] Wang Ling, Li Lingpo. An effective hybrid quantum-inspired evolutionary algorithm for parameter estimation of chaotic systems[J]. Expert Systems with Applications, 2010, 37(2): 1279-1285.

[26] Yan Jun'an, Zhuang Zhenquan.Research of quantum genetic algorithm and its application in blind source separation[J]. Journal of Electronics(China),2007,20(1):62-68.

[27] 王宇平,李英华. 求解TSP的量子遗传算法[J]. 计算机学报,2007,30(5):5748-5755.

[28] 吴斌,钱存华,董敏,等. 具有同时集送货需求车辆路径问题的混沌量子进化算法研究[J]. 控制与决策,2010,25(3):383-388.

[29] 何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践,2013,33(5):1255-1261.

[30] Wang Ling, Li Lingpo. An effective hybrid quantum-inspired evolutionary algorithm for parameter estimation of chaotic systems[J]. Expert Systems with Applications, 2010, 37(2): 1279-1285.

[31] 刘春秀.量子进化膜计算在辐射源信号分析中的应用[D].成都:西南交通大学,2010.

基于改进量子进化算法的车货供需匹配方法研究

Vehicleand Cargo Matching Method Based on Improved Quantum Evolutionary Algorithm

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

Metrics

本文评价

推荐阅读 10