带油耗率的车辆路径问题的改进量子遗传算法研究.pdf

《带油耗率的车辆路径问题的改进量子遗传算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、东莞理工学院学报第22卷第3期JOURNALOFDONGGUANUNIVERSITYOFTECHNOLOGYVo1．22NO．32015年6月Jun．2015带油耗率的车辆路径问题的改进量子遗传算法研究汪婷汤雅连。(1．广东技术师范学院天河学院，广州510540；2．广东工业大学自动化学院，广州510006)摘要：针对实际生活中车辆油耗会随着运载量的变化而变化，建立带油耗率车辆路径问题的数学模型，以最小化总成本为目标函数。将运输过程中随运载量变化的油耗率转化成交叉概率，自适应地改变交叉概率，提高算法的全局搜索能力；考虑车辆满载率，设计一种与运载量相关的变异概率

2、，使其逐渐减小并使群体迅速集中，可以抑制早熟。基于以上方法构造的一种自适应遗传算法，实例进行仿真表明，提出的算法在收敛速度和寻优结果两方面略优于自适应遗传算法和遗传算法。关键词：车辆路径问题；量子进化算法；遗传算法；自适应；油耗率；运载量中图分类号：TP301文献标志码：A文章编号：：1009—0312(2015)03—0047—09车辆路径问题(VehicleRoutingProblem，VRP)¨-2]自1959年Dantzig和Ramser首先提出以来就引起了人们的高度重视，它属于经典的组合优化问题。VRP的实用性强，且应用广泛。车辆路径问题一般定义为：

3、对一系列送货点和收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、送发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用极小、时问尽量少、使用车辆数尽量少等)。量子进化算法(QuantumEvolutionaryAlgorithm，QEA)是20世纪90年代后期新兴的一种进化算法。由于其良好的性能，已广泛应用于诸多领域，如物流运输调度、智能交通领域、网格入侵检测、网格任务调度、非线性规划等。MohammedA．M．等人提出了基于量子遗传的量子交叉算法(Quan．turnCrossov

4、er—basedQuantumGeneticAlgorithm，QXQGA)对非线性规划问题求解；蔡延光等人针对量子进化算法计算量大、收敛速度慢以及容易出现早熟等问题，提出混沌混合量子进化算法，并证明其可较好地应用在智能交通领域。研究车辆路径优化问题(VehicleRoutingProblem，VRP)是研究IVRP的基础。目前，国内外采用QEA及其改进算法对VRP或其扩展问题的研究文献不少，有一定的借鉴意义。CuiL．等人提出了一种带混合局部搜索的改进量子进化算法(ImprovedQuantumEvolutionAlgo—rithm，IQEA)对带容量约束的

5、VRP(CapacitatedVehicleRoutingProblem，CVRP)求解；WangL．等人提出了一种改进量子进化算法(Quantum—InspiredEvolutionaryAlgorithm，IQEA)对带时间窗的VRP(VehicleRoutingProblemwithTimeWindows，VRPTW)求解；葛显龙等人根据随机需求信息把动态配送问题转换成一系列静态配送问题，设计基于并行节约算法动态插入随机需求信息的混合量子遗传算法，对动态模型实时再优化；之后，葛显龙等人又采用量子比特位设计染色体结构，改进遗传算法中交叉与变异算子，避免优秀

6、基因被破坏，设计快速寻优机制与最优保留机制，增强求解效率对以配送总费用最小为优化目标的数学模型求解；ZhangJ．等人提出了一种自适应网格多目标量子进化算法(Multi—objectiveQuantumEvolutionaryAgorithm，MOQEA)对带客户满意度的多目标VRP(Multiob-ectiveVehicleRoutingProblemConsideringCustomerSatisfaction，MVRPCS)求解；MichalletJ．等人研究了非常严格的带时问窗的周期性VRP，并提出了混合整数线性模型和多起点迭代局部搜索算法；Cris—

7、pinA．等人提出了一种量子模拟算法对带容量约束的VRP求解；ZhengT．等人l提出了量子差分进化算法对调度问题求解；ZhouL．等人针对传统的遗传算法不能保证收敛到最优解的最大概率，提出了对小规模求解具有快速收敛和良好搜索能力的量子遗传算法，对VRP求解；NingT．等人¨结合量收稿日期：2014—07—13作者简介：汪婷(1988一)，女，江西鹰潭人，讲师，硕士，主要从事物流信息技术及组合优化研究。东莞理工学院学报2015往子粒子群优化算法和模拟退火算法，提出了混合量子粒子群优化算法对带时间窗的VRP求解；彭典军在其硕士论文中，主要研究了一种量子进化算法

8、在车辆路径问题中的应用，具体求解了有能