基于变异的粒子群算法的MDVRPTW研究

• 作 者: 陈婷
• 发表日期: 2010年期
• 关键词: 粒子群 变异 编码 多车场 时间窗

物流配送是现代化物流系统的一个重要环节,在现代物流系统中具有突出的地位。一方面通过物流配送成本的降低可以实现物流总成本较大地降低,是实现物流总成本优化的重要途径之一。另一方面物流配送是物流过程中客户感受最直接的部分,因此物流配送服务的质量是影响客户对物流服务整体质量评价的关键因素,是提高客户满意度的重要手段之一。而物流配送面临的环境条件越来越复杂,如道路网复杂、服务目标客户分散且不均匀等。因此,设计合理、有效的物流配送方案,尽量降低配送成本和提高服务水平就成为非常实际和关键的问题,鉴于从事物流配送尤其是城市配送主要是以汽车运输为主,因此如何有效地使用车辆并决定最经济合理的行驶路径成为需要解决的核心问题,即如何应用现代数学方法及计算机快速对该问题进行求解是一个十分值得研究的课题。应用粒子群算法是被认为求解NP难题的有效手段之一,为解决MDVRPTW(带时间窗的多车场车辆路径)的优化问题,本文在求解物流配送车辆路径优化问题时提出将粒子群算法与变异操作相结合的求解方式:通过设计一个随群体适应度方差的变化而变化的变异算子,将聚集在局部收敛点附近的粒子打散,进而增强算法跳出局部最优的能力和全局寻优的几率。文章在应用粒子群算法时,采用特定方法而非随机获取初始解,从而提高了搜索到最优解的概率并且加快了收敛速度。文章还针对带时间窗的多车场车辆路径问题构造了一种新的编码方式,目的在于降低了非法解出现的次数,最终达到减少算法的无效迭代的目的。仿真结果表明,新算法的全局搜索能力有显著提高且能有效避免早熟收敛问题。