求解车辆路径问题的离散粒子群算法  

Discrete Particle Swarm Optimization Algorithm for Vehicle Routing Problems

作　　者：魏明[1] 靳文舟[1] 

机构地区：[1]华南理工大学土木与交通学院,广州510640

出　　处：《计算机科学》2010年第4期187-191,共5页Computer Science

基　　金：国家"863"高技术计划项目(2007AA11Z201);国家自然科学基金(50878089)资助

摘　　要：考虑车辆行驶时间和顾客服务时间的不确定性,建立了以车辆配送总费用最小为目标的机会约束规划模型,将其进行清晰化处理,使之转化为一类确定性数学模型,并构造了求解该问题的一种离散粒子群算法。算法重新定义了粒子的运动方程及其相关离散量运算法则,并设计了排斥算子来维持群体的多样性。与标准遗传算法和粒子群算法比较,该算法能够有效避免算法陷入局部最优,取得了满意的结果。A fuzzy programming model was built to optimize total cost of vehicle routing problem, where vehicle travel time and customer service time were fuzzy. The mode was firstly converted into a deterministic one, and then it was solved by a discrete particle swarm optimization algorithm which redefined the equation of particle motion and algorithms of discrete variables and designed exclusion operator to maintain the population diversity. In comparison with both standard genetic algorithm and standard particle swarm optimization algorithm, it can effectively avoid the search being trapped into local optimum and achieve satisfactory results.

关 键 词：车辆路径问题 模糊旅行时间 离散粒子群算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] U116.2[自动化与计算机技术—计算机科学与技术]