协同物流网络中带有时间窗的车辆路径问题研究

□ 刘 玺

(中国石油大学(华东)，山东 青岛 266580)

1 引言

协同物流网络(Collaborative Logistics Network)是近年来基于协同理论发展起来的现代物流网络，它能够实现物流企业之间的协同，共同完成配送任务。因此，如何规划多供应商协同配送下路径，最大限度地降低成本的就显得尤为重要。

车辆路径问题(VRP，Vehicle Routing Problem)由Dantzig和Ramser于1959年提出[1]，并引起了广泛关注，属于典型的NP-hard问题。随后，不同学者使用各类算法对单对多、多对多车辆路径问题进行了求解[2-5]。本文从物流集成服务商的角度出发，研究协同物流网络中多供应商协作下，带软有时间窗的车辆路径问题(VRPTW，Vehicle Routing Problem with Time Window)。通过对实际问题的分析，构建数学模型，设计智能优化算法和算例，证明本文设计模型的合理性和算法的有效性。

2 问题描述与假设条件

2.1 问题描述

在协同物流网络中，多个供应商与多个客户点信息共享，物流集成服务商选择供应商为客户进行货物配送，安排车辆为客户进行要求运输车辆在客户的时间窗内完成配送任务。但配送过程存在如下问题：①配送车辆与客户时间窗不匹配，产生时间窗等待或者延迟成本；②车辆行驶路径决策不科学，导致配送成本增加。

具体问题描述如下：多供应商多客户组成的协同物流网络由G=(O∪I，A)表示，路线集合A={(i,j)|i，j∈N∪O,i≠j}，区域内多供应商集合为O{o|o=1,2,…,|O|}，共同为客户集合N{n|n=1,2,…,|N|}提供货物配送服务，各个供应商和各个客户之间道路互通，容量为H的配送车辆集合为K{k|k=1,2,…,|K|}。客户i的配送时间窗为[tei,tli]，λi表示客户i时间窗的紧急程度，tki为车辆k到达客户i的时间，ω1为车辆的等待成本，ω2为延迟成本。ck为车辆k的单位配送成本，Fk为车辆k的固定调用成本。协同运作的供应商与客户之间为N-N匹配关系，决策变量选择如下：

2.2 条件假设

①每个客户的一类货物只由一辆车供给，需求不可拆分；

②每辆车必须从供应商出发，完成配送任务后返回该供应商；

③配送成本只与车辆启用次数和配送距离有关。

3 模型构建

模型目标选择为总成本最小，成本包含配送车辆的固定调用成本、变动成本和时间窗成本。其中配送成本由车辆的固定调用成本和变动成本构成，第i个加客户的配送成本可以表示为：

(1)

时间窗成本：

(2)

模型构建如下：

(3)

s.t.:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

其中，目标函数(3)表示的是整个配送过程中总成本最小；约束条件(4)表示某类货物的配送量不能配送车辆的装载容量；约束条件(5)表示一个客户的某类货物需求任务只由一辆配送车辆完成；约束条件(6)表示一个客户的某类货物需求任务只由一个供应商提供；约束条件(7)为车辆使用数量限制；约束条件(8)表示配送车量从供应商出发，完成任务后返回该供应商；约束条件(9)表示消除子回路；约束条件(10)表示车辆到达客户的时间；约束条件(11)和(12)表示两个决策变量均为0-1变量。

4 算例分析

4.1 算法设计

遗传算法由于其全局优化性能良好、适应性强，在复杂的线性、非线性问题上表现出优秀的空间搜索能力，所以本文选用遗传算法进行求解。

①编码。

当遇到各种多决策变量情况，如组合服务、循环路径、多任务等时，一维编码方案表现能力大打折扣。因此Gottlieb等提出了矩阵编码[6]，矩阵编码是指采用矩阵的形式来对个体进行编码。根据问题描述，对模型进行编码设计，供应商数目为n，客户数目为m，行表示出发点，列表示到达点，车辆旅行路径可用一个矩阵表达。

②初始种群及适应度函数。

设置种群规模为θ，按照编码规则随机生成θ个满足路径约束、时间窗约束和配送量要求的染色体，适应度函数选择F=minC。

③选择、交叉与变异操作。

选择操作部分，本文采用轮盘赌法，适应度值越大的个体，被选择几率越高。交叉操作部分，本算法采用多点交叉的方式，随机选择矩阵中多列进行交叉，交叉的概率取值范围通常为[0.4，0.99]。变异操作部分随机选择矩阵，对其列进行变异操作。

④本文设置了遗传算法的迭代次数，当遗传操作达到该次数时，即终止操作。

4.2 实例分析

本文选取青岛市某副食配送网络，物流网络内共有3个供应商和20个客户，每个客户订货量已知，车辆行驶速度为40km/h，固定调用成本为30元。供应商坐标分别为Ⅰ(120.335，36.134)、Ⅱ(120.217，36.072)、Ⅲ(120.135，36.066)，按照优先级，将客户坐标分为λ1：(120.414，36.430)、(120.243，36.193)、(120.403，36.151)、(120.304，36.361)、(120.473，36.405)、(120.189，36.921)、(120.456，36.130)；λ2：(120.425，36.151)、(120.339，36.176)、(120.512，36.395)、(120.495，36.334)、(120.181，36.430)、(119.853，36.258)、(120.880，36.320)；λ3：(120.362，36.233)、(120.511，36.371)、(120.282，35.770)、(120.251，36.528)、(120.102，35.801)、(120.108，36.235)。

参数设置完毕后，在Matlab R2017b上进行算法的求解。遗传算法中的参数设置如下：种群初始规模为50，迭代次数为300，交叉概率为0.6，变异概率为0.08。多次求解得到最终结果为配送方案A，启用5辆配送车，总路程630.5km，总成本970.75元，其中时间窗成本为0。另外改变约束条件，求解原单供应商固定分区配送下方案B，启用6辆配送车，总路程776km，总成本1110.9元，其中时间窗成本为70元。对比如表1所示。

表1 配送方案对比表

通过对比可以看出，三个供应商协同配送方案A相比传统配送方案B的旅行距离节约18.75%，配送成本节约12.62%，时间窗匹配度增加10%。从整体角度看，共同配送的方式能够最大化配送效益，减少车辆配送距离。

5 总结

本文构建了带有软时间窗的协同物流网络中的车辆路径问题模型，采用矩阵编码的遗传算法对问题进行了求解，并与传统配送方式进行了对比。由于传统配送方式下，供应商往往只能送达某一分区的客户，多个分区独立运行，导致成本较高。多供应商协同配送并考虑客户时间窗的要求更符合实际情况，且能够最大化协同物流网络的整体效益。