考虑总量和体积双重约束的时间窗车辆路径问题研究

金　叶　丁以中

摘要: 车辆路径问题是被学者普遍研究的一个问题，也是一个经久不衰的研究课题。文章通过对车辆路径问题的改进，基于多种种类的货物，对考虑货物的不同重量和体积限制的带时间窗的车辆路径问题建立模型，通过粒子群算法求解模型，给出合适的解决方案。

关键词: 车辆路径；时间窗；重量；体积；多重约束；粒子群算法

中图分类号: U116.2文献标识码: A

Abstract：VRP is usually studied by researchers from its beginning. An improvement of VRP is studied in this paper. An VRPTW model considering both weight and volume restricts is seted, then solve the problem using PSO（Partical Swarm Optimization）method.

Key words: VPR；time window；weight；volume；mulriple restricts；PSO

0引言

车辆路径的选择对物流配送的成本有很大的影响, 如何在众多的配送路线方案中选择一个较优的方案是物流运行过程中需要解决的重要问题, 也正是车辆路径优化所要解决的问题。由于车辆路径问题的重要性及其复杂性，众多的学者在该领域有过研究。早在1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型。由于车辆路径问题的复杂性，对其求解有很大的困难，因此不断有学者加入此领域的研究。1991年，Gendreau等人将禁忌搜索方法应用于VRP。1996年，J.La wrence将遗传算法用于VRP的研究，并可有效求解带时间窗口的VRP。

车辆路径问题的一般描述是： 对一系列给定的客户（送货点或取货点），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定的约束条件下（如车辆容量限制、行驶里程限制、时间限制、顾客需求量、交发货时间等），达到一定的目标（如路程最短、费用最少、时间尽量少、使用车辆数尽量少等）。如图1所示。

纵观前人对车辆路径问题的研究，绝大多数是对于网络规模的扩大和求解算法的研究，对车辆路径问题模型本身则鲜有改进，本文的研究着眼于对模型的改进，结合被运输货物本身的多样性，考虑在货物多种属性（主要是重量和体积）的影响下车辆路径的选择问题。

1问题描述

在研究车辆路径问题时，深入企业间物流配送运作的实际情况，很多情况下需要考虑被运输货物的多种属性。比如在装运时，有些货物虽然较轻，但是体积较大，在运输作业中成为轻泡货物，假如只考虑车辆的载重量对其的约束，那么一辆车上能够运载很多这样的货物，那显然是不合理的。这只是一个简单的例子来说明运输时同时考虑重量和体积约束的必要性，在实际运载过程中会遇到很多不同种类的货物需要同装一辆车的情况，那么情况就较为复杂了。本文就是基于这个角度出发，对经典的带时间窗的车辆路径问题模型予以改进，考虑货物不同种类造成的其体积和重量双重约束对模型的影响，并且对其进行求解。

2模型建立

目标函数：minZ=cx+PmaxETi-si,0+Pmaxsi-LTi,0

St.xijk=xjik≤1, i=0, k∈{1,2,…,K}（1）

xijk=1, i∈{1,2,…,L}（2）

xijk=1, j∈{1,2,…,L}（3）

gixijk≤q, k∈{1,2,…,K}（4）

vixijk≤V, k∈{1,2,…,K}（5）

ETi≤Si≤LTi, i∈{1,2,…,L}（6）

gi=vi h（7）

其中: 目标函数保证了总成本Z 最小，式中PE，PL分别是指早到的单位惩罚值和晚到的单位惩罚值; 式（1） 确保车辆从配送中心出发回到配送中心; 式（2）、式（3）保证每个客户只能被一辆车服务一次; 式（4）是车辆的载重能力的约束; 式（5）是对车辆容积的限制；式（6）是时间窗约束，这个约束在目标函数中不存在对迟到和早到的罚函数式起效（即硬时间窗约束），在本文中这个约束不起作用，因为本文考虑的是软时间窗的约束; 式（7）中Ph是指不同种类的被运输货物有不同的密度，这样导致同一车内的货物可能属于不同的种类，要求我们同时考虑其重量和体积对模型的影响，h表示有h种不同的货物。

Sj=xijkS+S+t，j∈{1,2,…,L}（8）

Sij=cij /v（9）

K=max+1，+1，为车辆装载吨位利用系数，为车辆装载容积利用系数（10）

式（8）中: Si表示车辆到达任务点i的时间；Sij表示车辆从客户i 到客户j 的行驶时间，如式（9）中所示； ti 表示客户点i的服务时间, i, j∈{0, 1,…,L}, S0=0，t0=0。为了便于求解，模型根据中的运输量事先确定所需要使用的车辆数，其依据是车辆的容积和重量哪个成为瓶颈约束，就考虑按哪个约束确定所需要使用的车辆数。如公式（10）所示，+1是取整的意思，g表示所有需要运送货物的总重量，q表示每辆车所能装载的重量。表示在考虑了车辆的吨位利用率为时，考虑重量的限制所需要的车辆数。同理，+1，v表示所有需要运送货物的总体积，V表示每辆车所能利用的容积，这个式子是指车辆的容积利用率为时，考虑体积的限制所需要的车辆数。

3算法

本模型的求解中采用粒子群优化算法（Partical Swarm Optimization，PSO）。粒子群算法是由Kennedy和Eberhart等于1995年开发得一种演化计算技术, 该算法通过模拟鸟集群飞行觅食的行为, 通过鸟的集体协作使群体达到最优目的。

粒子群群算法简介：

在PSO 系统中, 每个备选解被称为一个“粒子”（Partical）多个粒子共存、合作寻优, 每个粒子根据它自身的“经验”和相邻群体的最佳“经验”在问题空间中向更好的位置“飞行”, 搜索最优解。

假设粒子数为n, 粒子群中第i1≤i≤n个粒子的位置用向量X 表示, 第i 个粒子的速度表示为V。第i 个粒子迄今为止搜索到的最好位置记为Pb, 整个粒子群迄今位置搜索到的最好位置记为Pg。对于每一个粒子，每次迭代之后都要更新其速度和位置，以便能够朝着更优的位置前进。根据如下等式变化:

v[ ]=wv[ ]+c1rand( )(pb-x[])+c2rand( )(pg[]-x[]) （11）

x[ ]=x[ ]+v[ ] （12）

其中加速常数c1、c2 是两个非负值, 称为加速因子; rand（ ）是[0, 1]之间的随机数; ω称为惯性因子, ω较大适于对解空间进行大范围探查（exploration), ω较小适于进行小范围开挖（exploitation）。

算法步骤（如图2所示）。

Step1：初始化微粒群（群体规模为m），包括随机位置和速度；

Step2：评价每个微粒的适应度；

Step3：对每个微粒，将其适应值与其经历过的最好位置pbest 作比较，如果较好，则将其作为当前的最好位置pbest；

Step4：对每个微粒，将其适应值与全局所经历的最好位置gbest 作比较，如果较好，则重新设置gbest 的索引号；

Step5：根据公式（9）和（10）更新微粒的速度和位置；

Step6：如未达到结束条件（通常为足够好的适应值或达到一个预设最大跌代数itermax），则返回Step2。

粒子编码方式及其适应度函数的产生：

本文采用实数编码方式, 将其应用于VRP问题。对L个客户点、K辆车VRP问题, 每个粒子对应一个L+K－1维向量, 其中各元素值的大小顺序表示各客户点在总路径中的配送次序。

例如: 设客户数为8, 车辆数3, 若某粒子的位置向量X见表1。

则按照X的大小排列，得到车辆路径的顺序，结果见表2。

则该粒子对应解的总路径为: 0→4→5→0→3→7→1→0→2→6→8→0, 相应的分路径即为:

车1: 0→8→6→2→0。

车2: 0→1→7→3→0。

车3: 0→5→4→0。

适应度函数是在产生的路径的基础上，按照产生的路径顺序，计算按此路径行走所要耗费的时间或成本，即为适应度函数的值，在迭代过程中既要评价这些新粒子的适应度是否比种群内其他粒子或者原来的适应度更优，否则淘汰此粒子。

4模型求解算例

算例中存在一个配送中心和8个客户点，他们之间的距离关系如表3所示，其中0点表示为配送中心。

各节点需要运送的货物按其密度分可以分为3类，其密度分别为0.5,1.5,2。分别表示为货物类型A，B，C。每个节点需要配送的货物量如表4所示。

算例中所使用的车辆的属性为载重量8，车辆容积12。我们去车辆的吨位利用率为0.8，容积利用率为0.75。根据公式（10）提前确定所使用的车辆数为3。

车辆提前或者延迟到达某一节点所接受的单位惩罚为50。这样我们将原来模型改写，公式（6）的约束条件被取消。转化为目标函数中通过惩罚函数来体现时间窗的限制，亦称为软时间窗。

下面算例采用例子群算法，算法中的各个参数如下所示：

学习因子1, c1=1.4962;

学习因子2, c2=1.4962;

惯性权重, w=0.7298;

最大迭代次数, MaxDT=40;

搜索空间维数（未知数个数），D=10;

初始化群体个体数目, N=20。

经过40次的迭代，目标值收敛到935，其中路上所花费的成本为900，因为延误或者提前到达节点而接受的惩罚值为35，得到的最优解为086701540320。这样路径为:

车1: 0→8→6→7→0;

车2: 0→1→5→4→0;

车3: 0→3→2→0。

5结论

本文通过对车辆路径模型的改进，考虑不同货物种类对车辆路径问题的影响，同时考虑体积和重量的限制，对有时间窗约束的车辆路径模型进行求解，使得模型能跟企业现实问题更加贴切。该模型还存在一定的改进空间，比如可以将所需要使用的车辆类型考虑进去。

参考文献：

[1]Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959,10(6):80-91.

[2]Christofides N. Mingozzi A. Toth P. The Vehicle Routing Problem[C]//Combinational Optimization, New York' Johnly Wiley, 1979.

[3]郭耀煌. 安排城市卡车行车路线的一种新方法[J]. 系统工程学报, 1989,4(2)：70-78.

[4]郭耀煌, 李军. 车辆优化调度[M]. 成都： 成都科技大学出版社, 1994.

[5]李军, 郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京： 中国物资出版社, 2001.

[6]王征. 车辆路径问题的知识表示及智能建模方法研究[D]. 大连： 大连理工大学, 2007.

[7]Desrosiers J, Soumis F, Desrochers N. Routing with time windows by column generation[J]. Networks, 1984,14:545-546.

[8]Lapore G, Nobert Y, Desrochers M. Optimal routing under capacity and distance restrictions[J]. Operations Research, 1985,33:1050-1073.

[9]Fisher M L. Jaikumar R.A generalized assignment heuristic for vehicle routing[J]. Networks, 1981,11:109-124.

[10]Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing[J]. Annals of Operations Reseach,1999,89:319-328.

[11]Mazzeo S, Loiseau I. An Ant Colony Algorithm for the Capacitated Vehicle Routing[J]. Electronic Note in Discrete Mathematics, 2004,18:181-186.

[12]李军. 有时间窗的车辆路线安排问题的启发式算法[J]. 系统工程, 1996,14(5)：45-50.

[13]李军, 谢秉磊, 郭耀煌. 非满载车辆调度问题的遗传算法[J]. 系统工程理论方法应用, 2000,9(3):235-239.

[14]李军, 郭强, 刘建新. 组合运输的优化调度[J]. 系统工程理论与实践, 2001(2):117-121.

[15]李金苹. 现代物流配送系统的运输优化调度方案[J]. 物流技术, 2002(5):11-13.

[16]霍佳震, 张磊. 有时间窗集的集货送货一体化车辆路径规划启发式算法研究[J]. 物流技术, 2004(5):46-66.