基于TLV 三维约束的多配送中心VRP 问题

王长琼，王艳丽，邱 杰，曹乜蜻，刘晓宇

（武汉理工大学 物流工程学院，湖北 武汉 430063）

1 引言

随着互联网的普及，电子商务随之快速发展，相比于传统的物流配送，电子商务配送的配送网点位置分散、配送物品大小各异、配送服务时间要求也更加严格。传统物流配送VRP（Vehicle Routing Problem）问题中的单配送中心车辆调度问题已经被证明是NP难题，多配送中心车辆调度问题使本来就具有NP复杂性的调度问题的求解更增添了难度。因此，对电子商务环境下多配送中心VRP问题的研究具有更重要的现实意义。Yu B，Yang ZZ，Yao BZ采用蚁群和禁忌搜索的混合算法对带有硬时间窗约束的车辆调度问题进行求解[1]。郭森、秦贵和等采用改进的粒子群算法对多目标车辆路径问题进行了求解[2]。殷胭，叶春明采用聚类分析最短距离分配法将多配送中心车辆调度问题分解为多个单配送中心车辆调度问题进行求解[3]。金涛、叶勇等分别采用改进差分进化算法和狼群算法对多配送中心的车辆调度问题进行了求解[4-5]。在电子商务配送方面，杨浩熊、李金丹等采用聚类分析法划分配送区域，建立电子商务环境下的VRPTW模型，并用遗传算法进行求解[6]。覃运梅、毛海军等提出了基于自动快递机的快递配送新模式，采用元胞遗传算法对该优化模型进行求解[7]。

目前，关于电商配送的VRP问题的研究虽已成为学术界研究的热点问题，但大多数研究为单配送中心问题，关于多配送中心问题的研究主要集中在将各个客户需求点固定地划分给每个配送中心，从而将多配送中心问题转化为多个单配送中心问题。除此之外，在对配送车辆的载重量进行约束的基础上融入对车辆体积约束的研究也相对较少。为了使电商配送VRP问题的模型更接近实际情况，本文建立了一种基于TLV三维约束的多配送中心车辆路径优化模型，该模型根据具体的配送任务，动态的将客户划分给不同的配送中心，并利用遗传算法对该模型进行求解。

2 问题描述

电子商务配送呈现出新的特点，配送物品主要针对的是快递包裹，而快递包裹的重量和体积都存在明显的差异。另外，配送网点位置分散，配送时间要求更加严格。因此电商配送中的VRP问题可具体描述如下：

假设某区域有多个配送中心，为该区域内多个快递网点进行配送。根据不同的配送任务，每个快递网点可被任意一个配送中心服务。各快递网点的坐标位置已知、快递大小件需求量已知，且有时间窗要求，各配送中心坐标已知，有多台车完成配送服务，配送车辆在时间窗外抵达快递网点都须支付一定的惩罚费用，在每个快递网点都需要一定的卸车时间，配送过程中每辆车的快递总量不得超过车辆的载重和额定容积。每辆车只执行一次配送任务，一个快递网点仅能由一辆车服务一次，每辆车从某一配送中心出发，配送完成后必须返回该配送中心。

需要解决的问题是：如何合理地部署各配送中心的车辆，安排各车辆的配送路径，尽量满足各快递网点的需求和时间窗限制，并使总配送成本最低。

3 模型构建

3.1 模型假设

为了便于问题的描述和构建相应的数学模型，针对该多配送中心三维约束模型提出了如下假设条件：

（1）配送区域内，每个配送中心至少服务一个快递网点。

（2）所有配送车辆同一车型，载重量和额定容积已知。

（3）单个快递网点的需求量不大于车辆的装载量，每个快递网点可以由任意配送中心的车辆进行配送。

（4）一个快递网点的货物只能由一辆车完成，且所有客户都应该得到服务。

（5）其他假设：道路通畅，货物在运输途中不会变质损坏。

3.2 符号说明

Kh：每个配送中心的车辆数；

Phk：每台车辆的载重量；

Bhk：每台车辆的额定容积；

Qhi：第h个配送中心服务的第i个客户的大件快递需求量；

qhi：第h个配送中心服务的第i个客户的小件快递需求量；

[ahi,bhi]：要求货物送到的时间范围；

a1，a2：每件小件快递和大件快递的重量；

c1，c2：每件小件快递和大件快递的体积；

dij：客户i到j的距离；

nhk：第h个配送中心第k台车辆配送的客户数（nhk=0表示未使用第k台车辆）；

Rhk：第h个区域中的第k条路径；

rhki：客户rhki在第h个区域中的路径k中的顺序为i（不包括配送中心）；

Shi：车辆到达客户i的时刻；

thi：车辆在客户i的等待时间；

ta：在每个客户点的卸车时间；

tij：配送车辆从客户i到j的旅行时间；

w1,w2,w3,w4：分别为单位运输成本、早于时间窗到的惩罚成本、晚于时间窗到的惩罚成本、单位固定车辆成本。

3.3 模型建立

（1）目标函数。以运输距离最短、时间成本最小、车辆使用成本最小为目标函数。即：

式（2）保证每条路径上各快递网点货物的重量之和不超过配送车辆的载重量；式（3）保证每条路径上各快递网点货物的体积之和不超过配送车辆的额定容积；式（4）表示每条配送路径上配送车辆到达下一个快递网点的时刻=到达当前快递网点的时刻+配送车辆在当前快递网点的等待时间+配送车辆在当前快递网点的卸货时间+从当前快递网点到下一个网点配送车辆的行驶时间；式（5）表示配送车辆在某个快递网点的等待时间取决于车辆到达该客户的时刻与该客户时间窗开始时刻的关系。

（3）其他约束条件

式（6）表示每条路径上的快递网点数不超过总网点数；式（7）表示每个配送中心至少要服务一个快递网点；式（8）表示每个快递网点都要得到配送服务；式（9）表示每条路径客户的组成；式（10）限制每个客户仅能由一台车辆送货；式（11）表示决策变量。

4 实例验证

在武汉市5家快递公司官网选取了291个快递网点，利用百度地图的坐标拾取系统确定了各个快递网点的位置坐标，另外选取武汉市某快递公司的3个集散中心位置坐标作为本算例的配送中心位置坐标。由于在该模型的约束条件中考虑到了车辆体积的约束，因此将每个网点的需求量划分为两部分，即：大件快递需求量以及小件快递需求量。并为每个快递网点设置相应的时间窗上限及下限。借助Matlab软件用遗传算法进行编程，以配送运输成本最小、时间窗惩罚成本最小以及车辆固定使用成本最小为目标函数，对武汉市快递配送网点进行车辆路径优化。前20个快递网点数据见表1。

4.1 各点距离计算和参数设置

由于该快递网点和配送中心的坐标是在百度地图中选取的经纬度坐标值，传统的距离公式已不再适用，当已知两点的经纬度分别为(ix,iy)、(jx,jy)，需采用以下公式将经纬度坐标转化为实际距离，该算

表1 前20个快递网点相关数据

例中其它参数设置见表2。

表2 模型相关参数设定

4.2 遗传算法参数设置

利用遗传算法对该算例进行求解，算法参数的设定对算法的性能及运行效率有极大影响，该算例中相应的遗传算法参数设置如下：

（1）对个体的编码进行设计，采用实数编码方法构造染色体，针对不同配送中心进行编码，然后将每个配送中心的编码进行串联，每个配送中心的编码格式为：[车辆数 顾客数 顾客访问顺序 车辆分配顺序]。

（2）种群初始化。设定种群规模为2 500、进化代数为250、交叉概率0.8、变异概率0.1，随机产生2 500个个体，组成初始种群。

（3）适应度评价。采用倒数法将目标函数转换成适应度函数，通过适应度函数评价每条染色体的适应度函数值。

4.3 实验结果

该算例中编号1、2、3分别代表三个配送中心，编号4～294分别代表291个快递网点。通过matlab程序运行，该算例的运行收敛图如图1所示，说明该遗传算法可以有效的解决本文所构建的车辆调度优化模型。具体的车辆路径优化结果见表3。

利用matlab程序运行，可得到总配送成本为：10 659.46，第一配送中心需6辆车，为66个快递网点进行配送服务。第二配送中心需要9辆车，为92个快点网点进行配送。第三配送中心需要10辆车，为133个快递网点进行配送。

图1 遗传算法收敛图像

4.4 灵敏度分析

为了分析单位运输成本w1和单位车辆固定成本w4带来的影响，在保持其他参数不变的情况下，分别将 w1和 w4增大10%、30%、50%、80%，运行8次程序，计算结果见表4。可以看出w1和w4对车辆的路径分配均会产生影响，且当参数在某一范围内发生变化时，各配送中心的车辆数量及车辆的路径分配结果不会发生改变。说明该模型针对不同的参数变化能够及时作出相应调整的同时也具有一定的稳定性。

表3 车辆路径优化结果

表4 单位运输成本和固定车辆成本对车辆路径的影响

5 结论

本文根据电子商务环境下的配送特点，针对快递包裹配送构建了一个基于软时间窗、车辆载重量、体积TLV三维约束的多配送中心车辆路径优化问题的模型。在该模型中将快递包裹划分为大件快递和小件快递两个变量，从而对快递包裹的体积进行约束，并采用遗传算法对该模型进行求解。利用matlab对具体实例进行验证，表明了该模型的有效性，可以为配送站点合理安排配送车辆及配送路径提供一定的依据。

[1]Yu B,Yang ZZ,Yao BZ.A hybrid algorithm for vehicle routing problem with time windows[J].Expert Systems with Applications,2011,38(1):435-441.

[2]郭森,秦贵和,张晋东,等.多目标车辆路径问题的粒子群优化算法研究[J].西安交通大学学报,2016,50(9):97-104.

[3]殷脂,叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报,2014,(4):602-606.

[4]金涛.多配送中心物流车辆调度的改进差分进化算法[J].计算机工程与应用,2014,50(3):232-235.

[5]叶勇,张惠珍.多配送中心车辆路径问题的狼群算法[J].计算机应用研究,2016,28(2):67-71.

[6]杨浩雄,李金丹,张浩.电商配送中的车辆调度问题优化研究[J].计算机工程与应用,2015,51(15):32-37.

[7]覃运梅,毛海军,黑秀玲.基于自动快递机的快递配送车辆路径优化研究[J].公路交通科技,2015,32(10):134-140.

[8]Huang Y,Zhao L,Woensel T V,et al.Time-dependent vehicle routing problem with path flexibility[J].Transportation Research Part B Methodological,2017,95:169-195.

[9]缪朝炜,苏瑞泽,张杰.越库配送车辆调度问题的自适应遗传算法研究[J].管理工程学报,2016,30(4):166-172.