带时间窗物流配送车辆路径问题摘要本题是一个带有时间窗的车辆路径安排问题（VRPTW问题）。

根据题目条件，本文建立了一个求解最小派送费用的VRPTW优化模型，采用遗传算法，给出了该模型的求解方法。

然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。

模型一（见5.1.2）针对问题一，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。

模型一的求解采用遗传算法（见5.1.3），对题目给出的实际问题进行求解，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。

模型一的思路清晰，考虑条件全面。

但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。

模型二的想法比较合理，易于实施，但还有待改进。

关键词：规划 时间窗 物流 车辆路径 遗传算法一、 问题重述一个中心仓库，拥有一定数量容量为Q 的车辆，负责对N 个客户进行货物派送工作，客户i 的货物需求量为i q ，且i q Q <，车辆必须在一定的时间范围[],i i a b 内到达，早于i a 到达将产生等待损失，迟于i b 到达将处以一定的惩罚，请解决如下问题：（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。

并具体求解以下算例：客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量i q （单位：吨）、装货（或卸货）时间i s （单位：小时）以及要求每项任务开始执行的时间范围[],i i a b 由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短； （2）进一步请讨论当客户i 的货物需求量i q 为随机参数时的数学模型及处理方法。

二、 问题分析本题主要在两种不同情况下，研究使派送费用最小的车辆行驶路径问题。

车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。

为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。

当客户i 的货物需求量i q 固定时，首先，我们根据题意，取若干辆车进行送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。

进一步讨论，当客户i 的货物需求量i q 为随机参数时，我们首先可以简化随机模型，根据客户i 的货物需求量的期望与方差，确定每天应该运送给客户i 的货物量，即i q ，再根据第一题，确定最佳的车辆派送方案。

但考虑到客户的储存能力有限及货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束的方案，考虑以单位时间的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。

三、模型假设（1）每个客户的需求只能由一辆配送车满足；（2）每辆车送货时行驶的路程不超过它所能行驶的最远路程；（3）中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；（4）从配送中心到各个用户、各个用户之间的运输距离已知；（5）配送中心有足够的资源以供配送。

四、符号说明五、模型的建立和求解5.1 问题一模型的建立及求解：5.1.1问题的分析中心仓库为了给N个客户派送货物，供发出m辆车，为了派货的节约和方便，每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物，见图一：图一中心仓库派送货物图中心仓如上图库派送货物时，必须满足约束条件：（1）各个客户群的总需求小于或等于运输车的装载量；（2）每个客户都必须且只能由一辆运输车运输所需货物；（3）运输车为每位客户开始服务的时间必须尽可能在时间窗内。

根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下：图二 最优路径产生图5.1.2模型的建立（1）中心仓库使用车辆数量的确定 设配送中心需要向N 个客户送货，每个客户的货物需求量是gi （i ＝1，2，…..N ），每辆配送车的载重量是Q ，且gi<Q 。

首先为了安排路线需要对要使用的车辆数有一个估计。

在现实情况中，货物装（卸）车越复杂，约束条件越多，一辆车的实际载货量就越小。

在本文中使用文献[1]的公式来确定需要的车辆数m ：1/Ni i m g aQ ==∑[ ]表示取整，a 为参数，0<a<1。

约束条件越多，货物装（卸） 越复杂，a 值越小。

参考文献[2]，取a 为0.85。

（2）引入0—1变量：1)ijs x 表示车辆s 是否从客户i 行驶到客户j 。

定义其为0—1变量，则⎩⎨⎧=01x ijs否则行驶到客户从客户车辆j i s 1,,s m =2)is y 表示客户i 的任务由车辆s 完成。

同样定义其为0—1变量，则⎩⎨⎧=01is y否则完成的任务由车辆客户s i 1,,s m =（3） 非线性规划模型的建立： a ．目标函数的确定。

题目要求所选行车路径产生的总费用最小，我们确定总费用为目标函数，记为Z 。

总费用由运输成本A 、等待损失B 和迟到所收惩罚C 组成，根据题意有：111NN mij ijsi j s A c c x====∑∑∑1*max{,0}Ni i B d D ==∑1*max{,0}Ni i C e X ==∑所以，总费用Z 最小化为：00111min *max{,0}*max{,0}NN mN Nij ijsi i i j s i i Z c c xd De X ======++∑∑∑∑∑b ．约束条件的确定。

约束1：车辆k 的运送总重量应不超过车辆的最大载重，即车辆有一定的运送能力，则可引入约束条件，1Ni isi q yQ =≤∑ (},,2,1{m k ∈∀)约束2：每个客户只能由一辆车来配送，则可引入约束条件，11mis s y m=⎧=⎨⎩∑ 1,2,3,...0i N i == 约束3：保证到达一个客户的车辆也离开该客户，则可引入约束条件，111m Nijss i x===∑∑ (1,2,3,,;j N =)111m Nijks j x===∑∑ (1,2,3,,;i N =)c ．变量之间关系的确定由上可确定等待时间i D ，超时时间i X 为：i i ii i iD a t X t b =-=- 1,2,....1,2,....i Ni N ==车辆k 从客户i 到客户j 需经过两段时间ij t 为：/ij ij t c v = ,1,2,....i j N =设车辆为客户i 运送完货物后即为客户j 运送，则到达客户i 处时间i t 和到达客户j 处时间j t 之间的关系为：11(max{,0})Nmj ijs i i ij i i s t x t D t s ===+++∑∑d ．此非线性规划模型为：00111min *max{,0}*max{,0}NN mN Nij ijsi i i j s i i Z c c xd De X ======++∑∑∑∑∑..t s1Ni isi q yQ =≤∑ m s ,,2,1 =11miss y m=⎧=⎨⎩∑ 1,2,3,...0i N i == 111m Nijss i x===∑∑ 1,2,3,,;j N =111mNijks j x===∑∑ 1,2,3,,;i N =i i ii i iD a t X t b =-=- 1,2,....1,2,....i Ni N ==/ij ij t c v = ,1,2,....i j N =11(max{,0})N mj ijs i i ij i i s t x t D t s ===+++∑∑5.1.3模型的求解我们采用遗传算法解决上面的问题： 1．编码采用自然数编码，即序数编码。

货物运输路线可以编成长度为N+m 的染色体11121s 21210,,,,0,,,0,,0,,,)t m mw i i i i i i i (，，其中，ik i 表示第ik i 项任务。

0表示车场，m 表示完成任务所需的车辆数。

2.出生初始群体初始群体随机产生，即产生N 项货物运输任务点的全排列，如12,,,N i i i ，如果11s ijj qQ -=≤∑，且1sij j q Q =>∑，将s 至N 的数向后移动一位，将0插入第s 位。

接着，继续上述操作，直到m 个0全部插入为止。

这样就构成了一条初始染色体。

用这种方法构造一个群体的染色体。

如：82576314，该编码插零之后变成0825*******。

它代表着需要三辆车运输货物。

其中，第1辆车行走路线为08250，即从仓库出发到依次到8、2、5商店再回到仓库。

第2辆车行走路线为07630，第3辆车行走路线为0140。

3.适应度函数适应度函数取'k kbz f z =，其中k f 为染色体k v 的适应度，b 为常数，'z 为初始种群中最好的染色体的运输成本，k z 为染色体k v 对应的运输成本。

4.遗传算子选取最佳保留的轮盘赌复制法进行染色体的复制。

变异算子采用反转变异。

交叉算子用最大保留交叉，其操作过程为：a) 若染色体交叉点处的两个基因都为0，则直接进行顺序交叉运算； b) 若染色体交叉点处的基因不全为0，则将交叉点左移（右移），直到左右两个交叉处的基因都为0，再进行顺序交叉运算。

5.算法的实现步骤Step1：采用自然数编码的方式，构造表示可行车路线的染色体；Step2：设置控制参数，包括交叉率0.7c p =、变异率0.1m p =、群体规模10n =； Step3：初始化，令0d =，随机产生初始群体(0)p ，群体中包括n 个染色体，每个染色体代表一条行车线路；Step4：令1i =；Step5：将群体()p d 中的第i 个染色体译为线路长度； Step6：计算适应度；Step7：若满足算法终止条件，则停止，否则继续； Step8：1ii =+；Step9：若i n ≤，回到step5，否则，转step10；Step11：进行最大保留交叉、基于位的变异和倒位操作； Step12: 1dd =+；Step13：若满足算法终止条件，则停止，否则转step4。