第5卷第1期 智能系统学报 Vol.5 No.1 2010年2月 CAAI Transactions on Intelligent Systems Feh.2010 doi:10.3969/i.issn.1673-4785.2010.01.013 定位-运输路线安排问题的 改进离散粒子群优化算法 彭扬，陈子侠，吴承键 (浙江工商大学计算机与信息工程学院，浙江杭州310018) 摘要：定位-运输路线安排问题(LRP)是集成物流中的一个NP-hard难题，为求解一类特殊的LRP问题，提出改进 的离散粒子群优化算法.该方法采用整体优化的思想，将LAP和VP集成在一起.通过合适的粒子编码方式，并改 进粒子的运动方程，引入相应的变异算子和趋同扰动算子等，使得算法的适用性和性能获得了改善.通过仿真实验 及与另2个典型算法的比较分析，证明了该算法的有效性. 关键词：定位-运输路线安排问题；离散粒子群优化；变异算子；进化算法 中图分类号：TP301文献标识码：A文章编号：16734785(2010)01007406 Improved discrete particle swarm optimization algorithm for location-routing problems PENG Yang,CHEN Zi-xia,WU Cheng-jian (College of Computer Science Information Engineering,Zhejiang Gongshang University,Hangzhou 310018,China) Abstract:The location-routing problem (LRP)is an NP-hard problem in integrated logistics systems.An improved discrete particle swarm optimization (PSO)algorithm was developed to tackle a special kind of LRP.It adopted the principle of whole optimization,integrating the location-allocation problem (LAP)with a vehicle routing problem (VRP).First,a novel code for the particle was introduced.Next,the particle's motion equation was improved, and the mutation operator and the disturbing operator against the population identical tendency were proposed, which improved the applicability and performance of the algorithm.A comparison of simulation results with those from two other typical algorithms showed the effectiveness of the proposed method. Keywords:location routing problem;discrete particle swarm optimization;mutation operator;evolution algorithm 物流管理领域一般有3个决策层次：战略层、战LRP是LAP与VRP的集成，目的是根据它们之间 术层和运作层.通常选址与分配问题(location-allo- 的复杂关系来相应地进行物流系统的整体优化 cation problem,LAP)属于战略层次的问题，而传统 LRP显然是NP-hard问题2)，国外有相关的文献阐 的选址分配决策模型不考虑运作层的车辆路径(ve 述其精确算法的求解，但只限于小规模的LRP.启发 hicle routing problem,VRP)、库存控制等问题；但是 式方法似乎是惟一可行的求解实际大规模LRP的 由于选址分配与车辆路径等问题的相互影响，因而 方法，如Tuzun等3)]提出两阶段禁忌启发式算法， 导致结果的次优化现象.定位-运输路线安排问题 Liu[4采用先解决VRP再优化LAP的两阶段启发式 (location routing problem,LRP)正是基于这样的背景 算法，Wu等5应用两阶段模拟退火启发式算法求 产生的，Nag认为LRP不是一个像旅行商问题 解具有多车型且数量给定的LRP问题等，国内张潜 (travelling salesman problem)那样能很好定义的概 等6]提出基于最小包络分析的遗传算法的两阶段 念，它应该被认为是一组问题集合.一般理解 启发式算法，张长星)采用树状编码的遗传算法， 并将LRP作为一个整体而不是分阶段进行求解.由 收稿日期：2008-0630. 于LRP问题的复杂性，各种求解方法都存在一定的 基金项目：国家自然科学基金资助项目(70671096)：浙江省科技计划 重点资助项目(200723090). 局限，探索新的更有效的算法是十分必要的. 通信作者：彭扬.E-mail:pengyang(@mail.jgsu.edu.cm. 粒子群优化算法(particle swarm optimization