改进量子遗传算法求解MDVRPPD问题-南京师范大学学报.PDF

第37卷第1期 南京师大学报(自然科学版) Vol.37 No.1 2014年3月 JOURNAL OF NANJING NORMAL UNIVERSITY(Natural Science Edition) Mar,2014 詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨詨 改进量子遗传算法求解MDVRPPD 问题 赵摇 超,吕摇 真 (河南牧业经济学院计算机应用系,河南 郑州450044) [摘要]摇 带集货和送货的多站点VRP 问题作为VRP 问题的一个分支,有着重大的研究价值.本文采用量子遗 传算法求解MDVRPPD问题,并提出一种新的旋转门策略使得量子遗传算法的进化速度大大加快.实验证明,本 文提出的改进算法和优化策略对比过去使用的启发式求解以及传统的量子遗传算法有较大优势,在时间控制上 以及最优解的求解上都取得了满意的效果. [关键词]摇 量子遗传算法,多站点,车辆路径问题,物流配送 [中图分类号]TP393摇 [文献标志码]A摇 [文章编号]1001-4616(2014)01-0099-05 Improved Quantum Genetic Algorithm for MDVRPPD Problem Zhao Chao,L俟Zheng (Department of Computer,Henan University of Animal Husbandry and Economy,Zhengzhou450044,China) Abstract:Multi鄄site VRP problem with collection and delivery as a branch of the VRP problem,has its significant researchvalue.Thispaperusesquantumgeneticalgorithmfor solvingMDVRPPDproblem,andproposesanewrevolving鄄 door policy whichmakesquantumgeneticalgorithmevolvefaster.Experimentshaveshownthatproposedimprovementsin algorithms and optimization strategy contrasting the past using quantum genetic algorithm of heuristic as well as traditional algorithms has a comparatively large advantage,and has achieved satisfactory results on optimal solutions to solve at the time control. Key words:quantum genetic algorithm,multi鄄site,vehicle routing problem,logistics 随着现代电子商务的兴起,诞生了越来越多的C2C(客户到客户)交易,这种物流的特点是发货点零 散,收货点也零散,相对于传统的电子商务一般都是一个指定卖家而多个买家的单向送货,C2C 的交易导 致了集货和送货的路径安排越来越重要,物流公司在同一个城市的里的每一天都要处理大量的集货和送 货请求,因此研究车辆路径问题(Vehicle Routing Problem,VRP)的同时考虑集货和送货这一分支犹其有实 [1] 际价值 .另一方面物流渠道即使是在同一城市里,也往往不止一个中心送货集货点,相对于在城内上门 集货送货而言,在城市与城市之间将货送到城内的哪一个中心点成本相差并不明显,所以在可利用的前提 下,研究多站点的VRP 问题是很有意义的. VRP 问题是NP鄄Hard 问题,求解该问题的算法非常多,大体上可以分为精确算法、启发式算法和现代