《物流系统优化与设计-有时间窗约束非满载车辆调度问题的C-W节约启发式算法》.doc

物流系统优化与设计 题 目: 有时间窗约束非满载车辆调度问题的 C-W节约启发式算法 姓 名: 宋 静 敏 学 院: 专 业: 物 流 工 程 班 级: 物 流 84 班 学 号: 指导老师： 2011年 6 月 29日 有时间窗约束非满载车辆调度问题的C-W节约启发式算法 物流工程专业学生 宋静敏 摘 要：本文引用了一个实际案例，假设了相应的时间约束与各配送点的任务量，采用C-W节约启发式算法求解和分析了此种带有时间窗约束的非满载车辆优化调度问题，得到了最优路线，从而在一定程度上达到了总运行费用最少的目标，实现了非满载车辆的优化调度。 关键词：车辆调度；C-W节约算法；时间窗；非满载；配送路线 相对一般的集货或送货非满载VSP来说，对于有时间约束的集货或送货的非满载VSP问题越来越受到人们的关注。本文针对多点配送调度问题，引用了一个实际案例，对旅行商的C-W算法进行修正，采用C-W节约启发式算法对带有时间要求的硬时间窗车辆优化调度问题进行了求解和分析，得到了满足货运需求的费用最小的运输路线，从而在一定程度上实现了非满载车辆的优化调度。 案例问题描述与情景假设 本文以南京浦口区部分苏果超市的实际分布为例，假设了某个物流配送中心在一天时间内的送货任务，并用驾车的最短距离近似地表示点对间的实际行驶距离。 具体情景假设为：某物流配送中心正常上班时间为7：30，现有11项送货任务，编号为1，…，11，各任务的货运量为gi （ 单位：吨)。卸货时间为Ti（单位：小时）以及要求每项任务开始执行的时间范围为[ ETi，LTi]（单位：时刻）由表1给出。这些任务由配送中心0发出的容量为8吨的车辆来完成，配送中心0与各任务点间和各个任务点之间的距离（单位：公里）由表2给出。 表1 任务的特征及要求 任务i 1 2 3 4 5 6 7 8 9 10 11 gi(吨) 2 2 2.5 3 4 3.5 1.5 4.5 3 4 3 Ti 小时 0.3 0.2 0.2 0.15 0.25 0.25 0.3 0.25 0.3 0.35 0.4 [ETi, LTi ] [0.5,0.8] [0.8,1] [0.7,1] [0.4,0.7] [0.4,0.8] [0.3,0.6] [0.9,1.2] [0.7,1] [0.4,0.7] [0.3,0.7] [0.5,0.9] 表2 点对之间的距离 0 1 2 3 4 5 6 7 8 9 10 11 0 0 26.1 35.3 25.7 17.4 19.1 17.3 32.3 24 17.1 17.2 27.3 1 0 5.9 12.1 11.6 13.3 13.1 3.4 13.8 10.4 12.9 9.2 2 0 6.3 6 7.4 7.3 3.7 8.1 5.3 7.2 3.5 3 0 1.3 4.4 3 9.2 5.5 0.9 2.8 4 4 0 3.3 1.7 9.4 2.4 2 1.5 4.3 5 0 2.1 11.5 3.1 5.3 2.2 5.2 6 0 10.4 1.7 3.7 0.85 6.5 7 0 11.3 7.8 10.2 6.8 8 0 2.8 0.75 4.7 9 0 5.9 3.4 10 0 5.6 11 0 这里，假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为40公里/小时，则从点i到j的行驶时间，tij=dij/40就不另列表给出了。又把各点之间的距离作为费用，即cij=dij（i,j=0,1,…,11）,如何安排车辆的行驶路线，使总运行费用最少。 优化方法描述 2.1 算法原理 此算法对旅行商问题的C-W算法进行修正，在连接点对时，考虑时间约束，是一种解决时间窗问题的有效启发式算法。 以cij表示车辆从点i到点j的费用，由C-W算法得到点