□ 文 军

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

1 引言

据中国物流与采购联合会统计显示，2017年中国社会物流总费用为12.1万亿元，其中运输费用为6.6万亿元，占比高达54.5%。因此，在物流系统优化过程中，怎样经济高效地选择车辆配送路径依然是一个极其重要的问题。

基于车辆共享的多配送中心车辆路径问题其实质就是开放式车辆路径问题，它是1981年由Schrage[1]首次提出的一类经典NP难问题。为提高客户满意度，本文还添加了软时间窗的限制，其相当于带软时间窗的多配送中心开放式车辆路径问题(Multi-Depot Open Vehicle Routing Problem with Soft Time Windows，MDOVRPSTW)，因此对其求解更加困难。

目前，国内外学者对VRP研究充分，但在MDOVRPSTW问题的研究上，还相对缺乏。对该问题的研究主要集中在智能算法方面，如遗传算法[2][3]、禁忌搜索算法[4]、蚁群算法[5-7]等。但多态蚁群算法在MDVRPSTW中的应用中，仍存在着许多未解决的问题。为此，本文设计了一种结合2-opt局部优化算法的自适应多态蚁群算法进行求解，采用实例验证该算法在求解MDOVRPSTW问题中的可行性和有效性。

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表示晚到车辆的单位时间罚金成本；

Z表示运输车辆配送时产生的总成本；

Q表示运输车辆最大装载量；

qi表示客户i的所需货物量；

[Ei,Li]表示客户i限制的提供配送服务时间窗；

ti表示对客户i提供物流配送服务的时间；

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

xijk表示运输车辆顺利从点i到达点J时为1，未顺利到达则为0，∀i,j∈G；

yijk表示车辆从配送中心i到客户j或者从客户i到配送中心j时为1，否则为0，∀i,j∈P∪G；

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

2.3 模型建立

根据以上的问题阐述和符号定义，构造如下带软时间窗的多配送中心开放式VRP的混合整数规划模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

∀i∈G,∀j∈P,∀k∈Kor∀i∈P,∀j∈G,∀k∈K

(10)

其中，表达式的含义为：

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

约束条件(2)表示每个客户只能被一辆运输车辆进行配送服务一次；

约束条件(3)表示为客户j提供配送服务的车辆数在到发方面保持一致；

约束条件(4)表示运输车辆服务客户的需求量之和不大于其最大装载量；

约束条件(5)表示运输车辆抵达客户j的时刻点；

约束条件(6)表示运输车辆在完成相应的物流配送服务后，可选择任一配送中心停靠；

约束条件(7)和(8)表示运输车辆在完成相应的物流配送服务后，一定得选择一个配送中心停靠；

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

3 算法设计

3.1 算法设计的总体思路

本文基于传统的TSP蚁群算法，结合具有软时间窗的多配送中心开放式车俩路径问题的具体约束条件，适当改进了选择、更新以及协调等机制，同时添加了自适应的转移策略和信息素更新策略。由蚁群具有多样社会分工的特性，使侦察蚂蚁在侦测过程带有特定的约束；让搜索蚂蚁来完成搜索满足目标函数可行解的任务。通过不同种类蚂蚁的分工协作，最后将信息素自适应策略与多态蚁群算法相结合，改进的算法有效地加快了基础蚁群算法收敛速度，克服了早熟现象的发生。

3.2 自适应多态蚁群算法步骤

根据陈美军等提出的自适应多态蚁群算法相关原理[8]，本文加入2-opt局部优化算法，将其应用于解决本文构建的带软时间窗的多配送中心开放式车辆路径模型上，其求解步骤如下：

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

②在N个客户点放置N只侦察蚁，把所在客户点i看作相应侦察蚁的中心，对其他N-1个客户点进行侦察，计算并记录总侦察表，将结果赋予Sij。

③在初始时设置每条路径上的信息量。

④设置进化代数NC初值为0。

⑤将搜索蚁k的初始位置定为虚拟配送中心点，并将该位置放在与搜索蚁k相对应的禁忌表tabuk中。

⑥搜索蚁k用轮盘赌方法挑选下一个访问的客户点，相应的禁忌表tabuk加入该客户点。

⑦对还没有访问到的客户点集合进行刷新，并再次计算可选客户点的集合。

⑧若还有客户点没有访问到而这些客户点都是不可选的，则说明虽然还有没提供配送服务的客户点，但是这些客户点都不符合约束条件。此时搜索蚁k返回虚拟配送中心点，相应的在禁忌表tabuk的末尾加入该点，构成以虚拟配送中心为始末位置的一条闭环路线。返回步骤⑤，直到还没用访问到的客户点的集合为空，转入下一步。

⑨计算每条路径中第一个和最后一个客户与实际配送中心之间的距离，用合适的实际配送中心代替虚拟配送中心，连接第一个客户的首端和最后一个客户末端，形成完整的路径。

⑩计算每只搜索蚁的目标函数值f(Z)，并记录当前最佳解。

结合2-opt局部优化算法的自适应多态蚁群算法的流程图见图1。

4 实例仿真

本文采用Matlab R2015a仿真软件来计算优化结果。设计3个配送中心位置点，各配送中心拥有的车辆最大数是3，20个客户位置点，每个位置点分散在一个100*100的正方形区域。其具体数据见表1。

图1 算法流程图

表1 位置点数据

其中，标号为1-3的位置点为配送中心的相关数据，标号为4-23的位置点为客户的相关数据。

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

表2 最优车辆配送路径

通过实验所得的配送车辆路径最佳图和最优解收敛曲线图如图2(a)和(b)所示：

图2(a)配送车辆路径图

图2(b)收敛曲线图

5 结束语

根据城市物流实际配送中遇到的多配送中心、多任务车辆调度优化问题，为降低整个配送过程中配送所产生的物流成本，提高城市的社会物流效益，本文从运输、时间等方面出发构建了一个基于物流配送车辆共享的开放式车辆路径问题数学模型。对于该模型，使用自适应多态蚁群算法来优化求解，并且将2-opt算法用于局部优化以加速算法的收敛。最后，该算法由Matlab R2015a仿真软件实现，并通过实例验证了自适应多态蚁群算法在处理基于车辆共享的开放式车辆路径问题是有效且可取的。