带时间窗的同时取送货车辆路径问题求解算法

闫 军，常 乐，王璐璐，赵 彤

(1.兰州交通大学 甘肃省物流与信息技术研究院，甘肃 兰州 730070；2.兰州交通大学 机电技术研究所，甘肃 兰州730070；3.呼和浩特铁路局集团公司包头货运中心，内蒙古 包头 014000)

车辆路径问题 (vehicle routing problem，VRP) 是物流生产活动中的核心环节，也是组合优化和运筹学领域的研究热点[1]。在实际的物流服务中，时间窗和取送货服务是需要满足的现实要求，所以带时间窗的同时取送货的车辆路径问题 (pickup and delivery problem with time windows, PDPTW)得到越来越多的关注[2]。

起初解决多车辆的PDPTW问题主要是依靠精确算法，从1991年Dumas等[3]的列生成算法到Furtado等[4]设计基于特殊有效不等式的分支切线方法。精确算法虽然无法求解大规模客户的实际案例，但丰富了PDPTW的数学模型，为目前的启发式算法求解问题提供基础。本文也以此为基础建立优化模型。Nanry等[5]最早使用响应式禁忌启发搜索算法对PDPTW进行求解，并进行25、50和100个客户规模的数据实验。Li等[6]在禁忌搜素算法的基础上混合模拟退火算法进行研究，而且将其研究的数据集进行公布作为PDPTW的研究基础。吴璟莉[7]使用遗传算法对拥有10个客户规模的多车、多货物仓库进行PDPTW问题的求解。为减少运行的车辆数目，Nagata等[8]运用引导式弹射搜索算法来对问题进行求解，实验证明可以有效减少车辆数。Zou等[9]使用混合粒子群算法对PDPTW进行求解，目的是为优化多目标的PDPTW问题。蚁群算法被用来进行PDPTW问题的求解，首次出现于2017年。Tchoupo等[10]强化蚁群算法局部优化能力后，与以往实验结果进行对比，发现其方法在98.2%的数据实验上取得相同或更好的结果，证明了蚁群算法在此类问题上的有效性。

本文在考虑客户规定时间窗和退送货需求的条件下，研究企业物流配送的最小化成本，建立车辆路径问题优化数学模型。首先运用K-means聚类算法将具有相同属性的客户划分成不同服务区域，综合考虑时间窗、与仓库的相对位置及与其他客户的距离因素；然后在每个服务区域内运用蚁群算法对单个车辆进行PDPTW问题求解，为提高蚂蚁的搜索能力，建立Q-leaning机制来改进蚁群算法内蚂蚁的学习能力。

1 问题描述及模型构建

1.1 问题描述与符号说明

PDPTW定义在图G(N,A)上 ，节点集为N={0,1,···,2n+1}，其中，0和2n+1分别表示起点和终点，它们可以表示同一位置。子集P={1,···,n}⊂N和D={n+1,···,2n}⊂N将一节点划分为取货点和送货点两个节点集。节点i∈N的 需求量为qi，m辆容量为Cap的运输车，从仓库N=0出发，按一定顺序通过所有节点，然后返回仓库，每一辆车只能服务一条线路，当到达节点i时车的负载和时间分别为Qi和Bi， 其中，Bi要 满足时间窗 [ei,li]的 要求。边集为A={(i,j):i,j∈N,i≠j}， 当且仅当车辆从节点i到 节点j时，令xij为 等于1的二进制变量，Cij为运输的成本，tij为i节 点到j节点的车辆行驶时间[11]。

本文研究的PDPTW可描述为在不超过客户规定的时间窗和运输车辆的载货量的约束下，找到不超过m条路径使运输成本最小，并且尽可能地平衡各路径的总长度，通过这样的路径规划为客户提供同时取送货的服务，并且车辆最终返回仓库。

1.2 模型建立

基于以上问题描述与符号，建立以下PDPTW两指标数学模型。

目标函数(1)使总的路径成本最小化。式(2)和(3)保证每个节点仅被访问一次，时间变量和负载变量的一致性分别由式(4)和(5)确保，其中，常数M被定义为足够大的数字，时间窗和车辆容量分别由式(6)和(7)保证。此外，式(4)和(6)消除子路径。式(8)满足取货点和送货点的优先级关系。约束(9)～(13)进行路径信息的索引，保证车辆与路径的配对关系。其中，v表示储存路径信息，当节点i属于第一条路径时vi=1。 最后，约束条件(14)使两指标变量变得完整。

2 聚类处理的蚁群算法设计

算法分为两步：1) 对配送点进行区域划分，根据所划分区域情况明确每一区域具体的取送货量以及整个配送活动的运行车辆数目；2) 根据第1) 步的数据进行具体的单车辆线路规划。具体流程如下。

2.1 基于K-means算法的区域分割聚类处理的蚁群算法设计

本文对于PDPTW问题进行客户节点聚类，与传统的K-means聚类方法不同的是要考虑配送车辆的容量限制、仓库与客户点的位置关系(根据仓库的位置进行客户点的聚类)的影响。因此本文为适应PDPTW的实际需求，在K-means划分区域的基础上进行修正。具体流程如下。

根据拥有的运输汽车数量设定聚类数范围，计算平均BWP也就是avgBWP值来判断整体的聚类有效性。当平均BWP值最大时，对应的聚类数便是最佳聚类数kopt。

2.2 基于Q-learning的蚁群算法

初始的多车辆复杂VRP经过聚类处理后变成简单的单车辆VRP，故求解的计算量减少，所以此阶段需要算法有很强的局部搜索能力。蚁群算法中蚂蚁的转移概率引入强化学习机制，使蚁群算法的收敛能力得到提高[13]。

式中， H E(r,u)是一种启发式函数，在本文中用来评价节点r移动到s的优劣。 δ 、β是权衡学习经验矩阵和启发式函数相对重要性的参数。f是属于[0,1]的随机值，而f0是 大于0小于1的一个参数，当f≤f0时 选择下一个节点s， 否则随机产生属于[0,1]的数s。通过轮盘赌的方式与式(19)所计算的概率值Pk(r,s)进行比较选择下一节点。路径上的信息素依靠学习经验矩阵的循环迭代进行更新，AQ根据式(20)进行更新。

图1 基于Q-learning的蚁群算法结构Figure 1 Ant colony algorithm structure based on Q-learning

3 算例实验与结果分析

为检验设计算法的有效性，本文设计两个实验。实验1为验证加入聚类分析的作用，将普通多车量VRP问题作为模型，运用本文方法和文献中的其他方法分别求解，得出结果进行对比。实验2为验证本文提出的模型和算法在大规模车辆路径问题中的适用性，采取300个节点规模PDPTW问题的算例进行实验分析。

本文算法在Matlab 2018a上进行实验，并在一台搭载1.9GHz的AMD四核A10处理器和8GB内存的计算机上实现，蚁群数设为100，进行50次迭代。算法涉及参数根据控制变量法实验得出，每次只变动某一参数进行实验，确定合适的参数值，具体参数设置如表1所示。

表1 参数设置Table 1 parameter settings

实验1运用Wang等[14]提出的关于VRPSPDTW的标准算例，并且将本文提出的KQ-SA (结合K-means的Q-learning蚁群算法)与Wang等[14]提出的并行模拟退火算法 (parallel-simulated annealing, p-SA)和王超等[15]的离散布谷鸟算法 (discrete cuckoo search, DCS)进行对比实验。本文应用环境为大规模车辆路径问题，所以采用的算例节点数为25、50、100的各3组算例进行实验。节点数为100的算例路径规划如图2和图3所示，图中五角星为仓库位置。

图2 节点聚类结果Figure 2 Clustering results of nodes

图3 节点路线规划结果Figure 3 Node route planning results

每个算例进行10次，取最优结果所需车辆数目(number vehicle, NV)和行驶距离(travel distanced, TD)记录，如表2所示。其中行驶距离单位为km。由表2可知，KQ-AG可以的中小规模中的算例中可以得到与当前国际最优解相近似的解，并且在100个节点的算例中能够得出优于文献中的计算结果。

表2 实验1算法结果对比Table 2 Comparison of algorithm results of Experiment 1

实验2 收集文献中PDPTW问题算例实验结果最优的数据，并将其作为对照组与本文的所建模型和算法进行对比，表3展示了15组300客户规模的实验对比结果。

从表3中数据可以看出，本文模型和求解算法在计算时长上有很突出的进步，这主要是使用了聚类方法简化计算的复杂度。表中标粗数据为总行驶距离最优解，本文提出的方法在15组实验中有6组低于文献的最优解，有5组优于文献的解，其余得出相同解。本文方法在减少行驶距离时的优势不明显，低于文献最优解的实验中发现，仓库在偏离配送点较远的位置，聚类的优势效果没有体现出来。综合15轮实验数据，本问题提出的模型和解决算法可以求解出较优的结果，并且在缩短计算时间方面有较好的表现。

表3 实验2算法结果对比Table 3 Comparison of algorithm results of Experiment 2

4 结语

本文建立两指标的PDPTW问题模型，较三指标体系更简单计算速度更快。为解决大规模算例计算量大的问题，本文对客户节点首先进行聚类处理，然后进行具体路径求解，并且在使用K-means算法时，引入BWP指标来提升聚类的效果。为了提高蚁群算法的搜素能力，使用Q-leaning自适应蚁群算法对单独车辆的路径进行规划。本文提出的方法具有较强的适用性，在中小规模的案例中均能有较好表现，并且在计算大规模的算例时，缩短计算时间有比较大的突破。本文在缩短路径距离方面能力一般，接下来的研究主要是在聚类方面，如何能够解决偏离客户节点的仓库位置对路径规划的影响。

(责任编辑: 刘敏仪)