基于粒子群算法的物流配送车辆优化调度研究.pdfVIP

第32卷第 6期 武 汉 科 技 大 学 学 报 Vo1．32，No．6 2009年 l2月 JournalofWuhanUniversityofScienceandTechnology Dec．2009 基于粒子群算法的物流配送车辆优化调度研究 刘 志 雄 。 (1．武汉科技大学机械 自动化学院，湖北 武汉 430081；2．天津港 (集团)有限公司博士后科研工作站 ，天津 300461) 摘要：应用粒子群算法求解物流配送系统的车辆优化调度 问题 ，针对车辆调度 问题 中需要考虑车辆容量和车 辆行驶路径 的限制等要求 ，提 出一种基于收货点、粒子位置次序和粒子位置取整操作的三维粒子编码方法，采 用惯性权重线性递减粒子群算法对两个算例进行计算，并与遗传算法的计算结果进行 了比较。结果表明，粒 子群算法能够有效地对物流配送车辆调度问题进行优化 。 关键词：物流配送 ；车辆调度 ；粒子群算法；编码 中图分类号 ：U492．3 文献标志码 ：A 文章编号 ：1674—3644(2009)06—0615-04 物流配送车辆调度问题包括集货线路优化 、 中心仓库 ，拥有K辆车，容量分别为q(尼一1，2， 货物配装及送货线路优化等 ，是物流配送系统优 … ， K)；有 L个收货点的运输任务需要完成 ，各收 化的关键口。配送车辆调度问题是一个 NP完全 货点的货运量为g(i一1，2，…，L)，并且 max{g} 问题，通常采用一些启发式算法和智能优化算法 ≤max{q}；配送车辆优化调度的 目标是满足货 进行求解 ，例如单亲遗传算法口j、双种群遗传算 运需求的车辆行驶路径最短。 将车辆任务点编号为 0，l，…，L，其 中：0为 法 ]、模拟退火算法和遗传算法相结合的混合智 中心仓库 ；1，2，…，L为收货点。定义变量如下 ： 能算法 j、蚁群算法 和免疫算法 等。 f1 车辆走从任务点i行驶到任务点 — 粒子群算法是一种基于群体智能的进化类算 eok一10 否则 法 。与其他进化算法不同，粒子群算法具有显 式的计算模型，其编程容易、实现过程简单 ，一经 ： 1{收货点的 车辆是完成；为从任 0 否则 一 … ’ 提出便得到广泛的应用，特别是在求解连续 函数 务点i到任务点 的运输成本，其含义可 以是行 优化问题时显示了较好的优化性能l8]。粒子群算 驶距离 、运输费用和行驶时间等，在本文中，车辆 法也被用于求解车辆调度 问题 。雷秀娟等_9将遗 优化调度的 目标是车辆行驶路径最短 ，因此 ，将 传操作引入粒子群算法，用于求解公交车辆排班 定义为行驶距离；Z为所有车辆的行驶距离总 问题，但没有介绍其粒子编码方法。黄天赦等l1 和。则非满载车辆优化调度的数学模型为 将量子行为和遗传算法思想 弓I入粒子群算法，用 于求解车辆调度 问题 ，提出了一种用 自然数表示 、 minz一∑—J．∑—．J∑—一J‘‘ = 0 ，= 0 女= 1 针对客户和车辆的分段编码方法。