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

《物流系统优化与设计-有时间窗约束非满载车辆调度问题的c-w节约启发式算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、物流系统优化与设计题目:有时间窗约束非满载车辆调度问题的C-W节约启发式算法姓名:宋静敏学院:专业:物流工程班级:物流84班学号:指导老师：2011年6月29日7有时间窗约束非满载车辆调度问题的C-W节约启发式算法物流工程专业学生宋静敏摘要：本文引用了一个实际案例，假设了相应的时间约束与各配送点的任务量，采用C-W节约启发式算法求解和分析了此种带有时间窗约束的非满载车辆优化调度问题，得到了最优路线，从而在一定程度上达到了总运行费用最少的目标，实现了非满载车辆的优化调度。关键词：车辆调度；C-W节约算法；时间窗；非满载；配送路线相对一般的集货或送货非满载VSP来说，对于有时间约

2、束的集货或送货的非满载VSP问题越来越受到人们的关注。本文针对多点配送调度问题，引用了一个实际案例，对旅行商的C-W算法进行修正，采用C-W节约启发式算法对带有时间要求的硬时间窗车辆优化调度问题进行了求解和分析，得到了满足货运需求的费用最小的运输路线，从而在一定程度上实现了非满载车辆的优化调度。1案例问题描述与情景假设本文以南京浦口区部分苏果超市的实际分布为例，假设了某个物流配送中心在一天时间内的送货任务，并用驾车的最短距离近似地表示点对间的实际行驶距离。具体情景假设为：某物流配送中心正常上班时间为7：30，现有11项送货任务，编号为1，…，11，各任务的货运量为gi（单位：

3、吨)。卸货时间为Ti（单位：小时）以及要求每项任务开始执行的时间范围为[ETi，LTi]（单位：时刻）由表1给出。这些任务由配送中心0发出的容量为8吨的车辆来完成，配送中心0与各任务点间和各个任务点之间的距离（单位：公里）由表2给出。表1任务的特征及要求任务i1234567891011gi(吨)222.5343.51.54.5343Ti小时0.30.20.20.150.250.250.30.250.30.350.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.

4、7][0.3,0.7][0.5,0.9]7表2点对之间的距离012345678910110026.135.325.717.419.117.332.32417.117.227.3105.912.111.613.313.13.413.810.412.99.2206.367.47.33.78.15.37.23.5301.34.439.25.50.92.84403.31.79.42.421.54.3502.111.53.15.32.25.26010.41.73.70.856.57011.37.810.26.8802.80.754.7905.93.41005.6110这里，假设车辆的行

5、驶时间与距离成正比，每辆车的平均行驶速度为40公里/小时，则从点i到j的行驶时间，tij=dij/40就不另列表给出了。又把各点之间的距离作为费用，即cij=dij（i,j=0,1,…,11）,如何安排车辆的行驶路线，使总运行费用最少。1优化方法描述2.1算法原理此算法对旅行商问题的C-W算法进行修正，在连接点对时，考虑时间约束，是一种解决时间窗问题的有效启发式算法。以cij表示车辆从点i到点j的费用，由C-W算法得到点i和点j连接在一条线路上的节约值：s(i,j)=ci0+c0j-cij。上述案例问题描述已经假设ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟开始

6、时间。以si表示车辆到达点i的时间，tij表示车辆由点i行驶到j的时间，则有下列关系式：s0=0，ETi≤si≤LTi。以EF表示连接点i和点j所在的线路后，车辆到达j的时间比原线路上车辆到达j点时间的推迟（或提前量），则EFj可表示为：EFj=si+Ti+tij-sj。显然，EFj7<0时，车辆到达j点任务的时间提前；EFj=0时，到达时间不变；EFj>0时，到达时间推迟。为说明问题方便，定义参数如下：Δ-j——车辆在线路上j点后面的各任务均不需要等待的j点的到达时间的最大可以提前量；Δ+j——线路上j点后面的任务不违反时间窗约束的j点的到达时间的最大允许推迟量。分别可以按

7、下式计算：Δ-j=min{sr-ETr}Δ+j=min{LTr-sr}r≥j当考虑连接点i和点j所在的线路时，需检查是否违反时间窗约束。（1）当EFj<0时，若有

8、EFj

9、≤Δ-j，车辆在j后面的任务处不需要等待，否则，要等待；（2）当EFj>0时，若有EFj≤Δ+j，则j后面的任务的执行不会延迟，否则，要延迟进行。2.2算法步骤根据前述算法原理，设计具体求解步骤如下：Step1:计算s(i,j),令M={s(i,j)

10、s(i,j)>0};Step2:在M内按s(i,j)从大到小的顺序排列；Step3: