基于客户共享的车辆路径问题研究

□ 文 军

(兰州交通大学 交通运输学院，甘肃 兰州 730070)

1 引言

随着城市物流规模的逐渐扩大，由物流运输车辆所带来的道路拥堵、环境污染、噪音污染等一系列问题日益突出，为了提升物流配送效率，加大物流企业利润空间，加强城市的社会效益，如何高效合理地安排运输车辆路径问题尤为重要。

基于客户共享的车辆路径问题，其实质是在共同配送的理念下[1]，研究关于多配送中心的车辆路径问题，为了提高客户满意度，加入软时间窗的条件约束，构成了带软时间窗的多配送中心车辆路径问题(Mutli-Depot Vehicle Routing Problem with Soft Time windows，MDVRPSTW)，是一个标准的NP-难问题。

目前，相对国内学者，国外学者对MDVRP研究比较充分。对于MDVRPSTW的研究主要集中在智能算法方面，国外Giosa[2]，Tansini[3]，Li J[4]以及Ebadati[5]采用不同智能算法求解都取得了较好的研究成果；对于MDVRP的研究主要在于模型的重构及求解，Hong[6]和Kuo[7]分别从模糊时间旅程和装载成本对该问题模型重构并取得了较好的解。虽然国内外学者对MDVRPSTW的研究比较多，但现实中，该问题属于大规模问题且是NP-难问题，用不同的方法寻找更优的解仍具有现实意义。

2 模型建立

2.1 问题描述

假设某城市拥有多个物流配送中心，每个配送中心拥有相同数量的运输车辆，需要为该市多个客户提供服务。已知：①货物充足且运输车辆的载量相同；②任意两点之间均可顺利到达，且距离已知并具有对称性；③为提高客户满意度，为每个客户提供服务软时间窗；④运输车辆在完成配送任务之后必须回到始发配送中心。

问题的目标是：在客户共享的条件下，通过合理设计各运输车辆的运输路径以满足客户需求，实现运输总费用最低的目标。

2.2 符号定义

P={p|1,2,3,…,P}表示配送中心个数；

G={g|1,2,3,…,g}表示客户数量；

K={k|1,2,3,…k}表示运输车辆数；

dij表示任意两点之间的欧式距离，∀i,j∈P∪G；

c表示车辆运输的单位距离成本；

c1表示早到车辆的单位时间消耗成本；

c2表示迟到车辆的单位时间惩罚成本；

c3表示车辆的固定成本；

Z表示物流配送产生的总成本；

Q表示车辆满载量；

qi表示客户i的需求量；

[Ei,Li]表示客户i要求的服务时间窗；

ti表示对客户i进行服务的时间；

Ti表示车辆到达客户i的时间；

V表示车辆行驶的平均时速。

2.3 模型建立

根据上述问题描述和符号定义，创建如下带软时间窗的多配送中心VRP的混合整数规划模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

其中，表达式的含义为：

目标函数(1)代表最小化运输成本与客户等待时间成本之和，即使物流配送总成本最小化；

约束条件(2)表示各配送中心始发的运输车辆总数小于拥有的车辆数；

约束条件(3)-(5)表示每个客户只能被一辆运输车辆配送一次；

约束条件(6)表示每辆车服务客户的需求总和不大于其最大负载；

约束条件(7)表示运输车辆到达客户j的时间；

约束条件(8)表示完成配送任务的运输车辆，必须回到始发配送中心；

约束条件(9)表示决策变量的0-1约束。

3 算法设计

结合赵喜贵等[8]提出的基于蚁群算法的K-Means聚类雷达信号分选算法和陈美军等[9]提出的自适应多态蚁群算法相关原理，将聚类的多态蚁群算法用来求解MDVRPSTW问题，其设计步骤如下：

①将配送中心位置设置为初始中心，观察问题中客户的位置点分布，对位置点进行k均值聚类处理。

②设位置点可以聚成c1,c2,…，cm个类，其中m为配送中心点的个数，且o1,o2,…,om分别为每个类的中心点，把Om看成一个MDVRPSTW问题。

③置m的初始值为1。

④初始化参数Q、C、α、β、ξ和ρ，并设置最大迭代数为MAXGEN等。

⑤根据类中的客户点的数量放置不同数量的侦察蚁，每只侦察蚁以所在客户点i为中心，对相应类中其他客户点进行侦察，计算并记录总侦察表，将结果赋予sij。

⑥在初始时设置每条路径的信息量，并且进化代数Nc初始值为0；

图1 算法流程图

⑦随机选择每只搜索蚁k的初始位置，并将该位置放在与每只搜索蚁对应tabuk表中；

⑧计算每只搜索蚁k将要移动的位置，假如要移动的位置为j，上一个位置假设为i，则将j放在与搜索蚂蚁k对应的tabuk表中，当每只搜索蚁完成一个循环，即相应获得一个解；

⑨计算各搜索蚁的目标函数值f(Z)，并记载目前最优解；

⑩执行2-opt局部优化算法；

(B11)如果到达最大进化代数MAXGEN，转(B14)，若在达到最大进化次数之前获得的解，在最近若干次的迭代中没有显著改进，则调整挥发系数ρ，转(B13)，否则转(B12)；

(B13)NC←NC+1，转⑦；

(B14)得到类中的最优解；

(B15)m←m+1，转⑤；

(B16) 输出各个类中的最优解相加之和。

结合k-means算法的多态蚁群算法流程图如图1所示：

4 实例仿真

本文采用Matlab R2015a仿真软件来求解优化结果。设计配送中心数量为3，各配送中心拥有的车辆数为2，客户点数量为20，每个节点分散在100*100的正方形区域，其具体数据见下表1：

表1 位置点数据

其中，标号为1-20的位置点为客户点的相关数据，标号为Ⅰ、Ⅱ、Ⅲ的位置点为配送中心的相关数据。

根据距离的影响因素采取的k-means聚类算法，取得如下的聚类成效：

①配送中心Ⅰ对六个客户进行配送，客户标号分别为：4、5、10、13、16、19；

②配送中心Ⅱ对七个客户进行配送，客户标号分别为：2、7、9、12、15、18、20；

③配送中心Ⅲ对七个客户进行配送，客户标号分别为：1、3、6、8、11、14、17；

根据上述聚类结果，结合以往经验，为算法中的相关参数赋予初始值：α=1，β=2，ρ(t0)=1，N=23，Q=100，C=3，max(Pc)=10，最大迭代次数为50。模型中车辆的相关系数设定值为：单位运输成本c=1，早到的消耗单位成本c1=0.2，迟到的惩罚单位成本c2=2，最大装载量Q=6，平均时速V=40。模型求解得到的最小总成本为459.78，车辆的行驶路径情况如下表2所示：

表2 最优车辆配送路径

通过软件仿真实例所得的车辆最佳配送路线和收敛速度如图(a)和(b)所示：

(a)配送车辆路线

(b)收剑曲线图2

5 结束语

本文在基于共同配送的理念下，提出了关于客户共享的车辆路径问题，其本质是多配送中心的车辆路径问题，为提高客户满意度，加入软时间窗的条件约束，在解决带软时间窗的多配送中心车辆问题的时候，首先，应用了一种依据欧式距离聚类客户点的k-means聚类算法；其次，对通过聚类算法划分的子问题采用了多态蚁群算法进行求解计算，为了进一步提高算法的收敛速度，结合了2-opt局部优化算法；最后，构建了一种带聚类的多态蚁群算法，该算法适用于大规模的城市物流配送问题。对于具有明显的聚类特征的客户点的分布，算法的优越性也得到很好的体现。