带时间窗的三维装载物流配送优化方法研究

王 勇, 魏远晗, 蒋 琼, 许茂增

(重庆交通大学 经济与管理学院,重庆 400074)

0 引言

城市物流配送中合理的货物装载方式和科学的车辆路径规划对物流配送活动具有重要作用。城市物流配送中的三维装载问题主要是研究考虑不同体积和不同重量的货物在封闭立体式车厢内进行拼装、叠放和运送的一类问题[1]。现阶段，由于不同客户对商品类型的需求不同，且服务时间窗不一，增加了物流配送中心运输调度的复杂性，进而导致城市三维装载物流配送过程中常出现车辆装载率低和配送车辆路径规划不合理等问题。车厢货物装载方式是否合理，配送车辆路径规划是否科学，直接影响到配送中心的配送效率、成本和效益。根据配送商品类型，对配送车厢进行合理分区，进而优化货物在车厢中的装载方式，可以有效提高配送车辆的空间利用率，减少车辆使用数量；同时结合客户不同的服务时间窗制定科学合理的车辆配送路径方案可以提高配送效率，降低企业的物流运营成本。因此，本文结合城市物流配送车辆车厢货物装载方式和配送车辆路径规划两个方面，研究带时间窗的三维装载物流配送优化问题，有助于物流资源的有效整合与优化配置，进而有利于完善城市物流配送系统。国内外学者在带时间窗的车辆路径优化方面，带三维装载约束的车辆路径优化方面以及两个问题的结合方面进行了一系列研究工作。

在带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows, VRPTW)方面，符卓等[2]针对需求可拆分的带时间窗的车辆路径问题，建立了以最小化车辆使用数和最小化车辆行驶成本为优化目标的数学模型，并设计了禁忌搜索算法来求解模型。Hassan等[3]研究了带时间窗的多目标车辆路径问题，提出一种基于蚁群和禁忌搜索的混合算法进行问题求解。Shi等[4]研究了带时间窗的同时取、送货的车辆路径问题，构建了使配送成本和车辆使用数最小化的双目标数学模型，提出一种基于禁忌搜索的有效算法进行模型求解。Niu等[5]建立了带时间窗的开放式车辆路径问题的数学模型，设计了一种禁忌混合搜索算法进行模型求解。根据上述研究可以发现，混合智能算法常被用于研究带时间窗的车辆路径问题，而带时间窗的车辆路径问题研究为三维装载物流配送优化问题研究提供了方法切入。

三维装载问题和三维装载约束下的车辆路径问题也引起了部分学者的关注。那日萨等[6]应用空间切割法对车厢进行空间区域划分，在水平方向和竖直方向搜索放入货物的最佳位置，使箱体空间利用率最大化。Mahvash等[7]研究了考虑货物不同摆放方位的三维装载问题，并设计了货物在立体式车厢内的顺序放置方式。Gendreau等[8]在2006年首次提出带有三维装箱约束的车辆路径问题优化模型，并设计了禁忌搜索算法进行模型求解研究。Zhang等[9]设计了一种进化局部搜索方法求解三维装载约束下的最小化油耗车辆路径问题。Bortfeldt和Yi[10]在分批配送车辆路径问题的基础上加入了三维装载约束，建立了具有三维装载约束条件的分批配送车辆路径优化模型，并提出了一种由局部搜索算法和遗传算法组成的混合算法求解模型。颜瑞等[11]研究了带三维装箱约束的车辆路径问题提出分别应用模糊遗传算法和引导式局部搜索算法求解车辆路径问题和三维装箱问题。由上述相关研究可知，当前关于三维装载物流配送优化问题的研究集中在问题求解和算法设计方面，而考虑客户不同规格的货物需求和车辆分区空间等方面的研究还有待进一步深入。

本文考虑了客户服务时间窗和货物的三维装载空间约束，研究了带时间窗的三维装载物流配送车辆路径优化问题，并结合客户不同规格的货物需求和服务时间窗特征，进行了合理的车厢空间区域划分研究。首先，构建了物流运营成本最小化和配送车辆空间利用率最大化的双目标优化模型；然后，设计了一种结合遗传和禁忌搜索的GA-TS混合算法求解模型；最后，通过实例研究了带时间窗的三维装载物流配送优化前后以及不同空间分区模式下的平均装载率、车辆使用数和物流运营成本的变化，进而为带时间窗的三维装载物流配送问题提供新的研究思路。

1 问题描述

带时间窗的三维装载物流配送优化问题涉及车辆的货物装载方式和配送过程中考虑客户服务时间窗的车辆路径优化两个方面。为了有效整合物流资源和减少不合理的货物装载方式，需要综合考虑不同规格货物的装载方式和三维装载车辆的物流配送成本进行合理的配送调度。图1出示了带时间窗的三维装载物流配送优化前后对比图。

图1 带时间窗的三维装载物流配送优化前后对比图

图1(a)表示带时间窗的三维装载物流配送优化前，由于客户需求存在不同规格的货物类型和服务时间窗要求，导致现有配送方式往往存在车辆装载率不高和配送线路调度不合理的情况，进而造成违反客户服务时间窗较多和物流运营成本较高的现象。图1(b)表示带时间窗的三维装载物流配送优化后，基于客户不同规格的货物需求和客户服务需求时间窗，结合车辆装载和客户服务时间窗限制进行合理的车厢货物装载顺序设计和客户访问序列优化，进而提高了车辆装载率，降低了物流配送成本。假设单位时间的配送成本为30元，违反时间窗的单位时间惩罚成本是10元，车辆的租赁成本为100元/辆·次。表1出示了三维装载物流配送优化前后物流运营成本与车辆数量的比较，结果表明带时间窗的三维装载物流配送优化后有效提高了车辆装载率，减少了配送车辆使用数和降低了物流运营成本。

表1 三维装载车辆路径优化前后结果对比

2 模型建立

在三维装载物流配送优化问题研究中[1,9,11]，当不同装载空间可运送不同类型的货物，且货物类型数趋向等于装载空间划分数时，装载率最大。当某一空间可装载两种或多种货物类型且可堆叠装载时，空间装载率趋向等于与货物类型数相同的区域划分数的装载率，但当空间划分数小于货物类型数时，货物装载顺序复杂度远大于货物类型数与空间区域划分数相同的货物装载顺序复杂度。

2.1 模型假设

本模型假设条件如下：

(1)每位客户需求的货物类型、货物数量、服务时间窗及货物的长，宽，高均已知；每位客户仅由一辆配送车辆访问；

(2)配送车辆车厢被划分成多个空间区域，每个区域内装载的货物规格大小相同，且货物需要平行于车厢放置；

(3)访问客户的服务时间忽略不计。

2.2 符号定义

本研究涉及的变量和符号如表2所示。

表2 变量定义

2.3 模型构建

本文以配送中心的物流运营成本Z1最小化和配送车辆装载率Z2最大化为优化目标。建立的数学模型如下:

minZ1=G+TC+MC+FC+PC

(1)

(2)

G：配送中心的固定成本

(3)

TC：配送车辆将货物送达客户的配送成本

(4)

MC：配送车辆的维修成本，主要是指配送中心出发的配送车辆在一个工作周期内的平均维修成本。

(5)

FC：配送车辆的租赁成本，主要是指配送中心在一个工作周期内租赁配送车辆的费用。

(6)

PC：配送车辆违反客户服务时间窗早到和晚到的惩罚成本。

(7)

约束条件：

(1)车辆路径约束：

(16)

式(8)表示每个客户点只能由一辆车访问，式(9)表示流量约束，即车辆将货物送达客户后必须离开；式(10)表示车辆从配送中心出发，完成任务后必须返回配送中心；式(11)表示消除子回路约束；式(12)表示车辆上每一区域内货物数量的约束；式(13)表示车辆装载货物的重量不超过车辆的最大装载量；式(14)～(15)表示车辆离开和到达配送中心的时间需要在其服务的时间窗内，式(16)表示车辆配送过程中的时间连续性。

(2)三维装箱约束：

xckdiu≥0

(17)

yckdiu≥0

(18)

zckdiu≥0

(19)

pd·hdc≤hd,∀c∈C,d∈D

(20)

rd·ldc≤ld,∀c∈C,d∈D

(21)

cd·wdc≤wd,∀c∈C,d∈D

(22)

(23)

(24)

xik={0,1},∀i∈I,∀k∈K

(25)

yijk={0,1},∀i,j∈I0且i≠j,∀k∈K

(26)

(27)

式(17)～(19)表示货物必须摆放在车厢内；式(20)～(22)表示配送车辆任一区域内装载的货物不能超出区域范围；式(23)～(24)表示先进后出约束，依次表示为后服务客户的货物不能压在先服务客户货物的上面，后服务客户的货物不能挡在先服务客户货物的前面；式(25)～(27)表示变量约束。

3 GA-TS混合算法

3.1 算法过程描述

本文提出了一种基于遗传算法(GA)和禁忌搜索算法(TS)的GA-TS混合优化算法求解模型，将GA的全局优化与TS的局部搜索的特性相结合。GA-TS混合算法的流程图如图2所示。

图2 GA-TS混合算法操作流程

3.2 算法设计

本研究设计了GA-TS混合算法用于求解带时间窗的三维装载物流配送优化模型。TS算法对初始值依赖性较强，引入GA算法为其找到较好的初始点，可加快收敛速度，提高解的质量[12]。此外，GA具有较好的全局搜索能力，而TS局部搜索能力较强[2]。因此，GA-TS混合算法有效地结合了GA和TS算法的优点，提高了算法的全局收敛性能。

3.2.1 混合算法适应度

本文以配送中心的物流运营成本最小化和配送车辆装载率最大化为优化目标，设计的遗传算法的适应度函数如式(28)所示。

(28)

式(28)中Z1表示配送中心的物流运营成本，Z2表示配送车辆的装载率。

3.2.2 禁忌表和禁忌长度

3.3 算法检验

为了进一步检验GA-TS混合算法的有效性，将GA-TS混合算法与混合遗传算法(HGA)[13]、遗传粒子群混合算法(GA-PSO)[14]进行比较，三种算法均为混合算法且遗传算法是三种混合算法的重要组成部分，相比于本文提出的GA-TS算法，混合遗传算法设计了双层目标优化过程，并以物流运营成本最小化为主优化目标，以配送车辆装载率最大化为次优化目标进行三维装载车辆路径优化研究；而遗传-粒子群混合算法过程针对三维装载车辆路径优化目标设计了遗传算法和粒子群算法间的循环迭代机制，并构建了物流运营成本和车辆转载率的集成适应度函数进行问题研究。本文的测试数据是在Solomon测试数据集的基础上增加了客户不同需求商品类型的货物来构建的。20个不同数据集的实验数据如表3所示。

结合表3的实验数据，分别从物流成本、车辆平均装载率和算法求解时间三个方面比较三种算法的优化结果。三种算法的各项参数设置如下：GA-TS、HGA和GA-PSO算法中的种群规模popsize=100，最大迭代次数maxgen=200，选择概率Ps=0.9，交叉概率Pc=0.9，变异概率Pm=0.1；GA-TS算法中禁忌搜索迭代次数tsin=40，禁忌表长度TL=28；GA-PSO算法中的惯性权重w=0.9，学习因子c1=1.2，c2=1.4。将每种算法分别运行30次，选取最优的物流运营总成本和平均装载率以及对应的算法求解运行时间，如表4所示。

表3 实验数据参数表

表4 不同算法优化结果的比较

由表4可知，GA-TS算法、HGA算法与GA-PSO算法的最小物流运营成本的t检验和p值的比较结果表明GA-TS算法的最小物流运营成本与其他两种算法相比具有明显差异。此外，在物流运营成本和装载率方面，GA-TS在大多数情况下均优于HGA和GA-PSO求解的结果。在计算时间方面，GA-TS算法比GA-PSO算法需要更多收敛时间，但在物流运营成本最小化方面优于后者。

4 算例分析

4.1 算例相关数据

以重庆市某配送中心(DC)及其服务的110个客户点(C1-C110)进行研究。该配送中心服务的商品类型有4种，其相应的长、宽、高及重量如表5所示，且C1-C50是具有单一商品类型需求的客户点，C51-C90是具有2种不同商品类型需求的客户点，C91-C110是具有3种不同商品类型需求的客户点。

表5 各种类型的货物规格

假设每辆配送车辆的车厢可以近似看成箱体，且每一个车厢有4个大小不同的分区，每个区域只能装载相应类型的货物。每个区域的大小及可装载货物的数量如表6所示。

表6 各个区域规格大小及可装载货物的数量

4.2 结果与分析

在现有文献[3,9,10]和多次实验计算的基础上，相应参数设置如下：L=420cm，W=180cm，H=200cm，Qk=1300kg，Vk=15.12m2，K=25，g=0.2，T=52，ck=0.8，fk=200，mk=16000，φ1=15，φ2=20，popsize=100，maxgen=200，Ps=0.9，Pc=0.9，Pm= 0.1，tsin=40，TL=28。GA-TS混合算法求解带时间窗的三维装载物流配送优化前后结果的对比如表7所示。

表7 三维装载车辆路径优化前后结果对比

由表7可知，应用GA-TS混合算法优化后的配送方案相比优化前的方案，配送时间减少了37.5%，早到和晚到时间共减少了71.88%，车辆数节省了50%，时间窗惩罚成本减少了80.28%，配送成本减少了32.33%，物流成本节约了44.71%，平均装载率提高了42.92%。

此外，本文选取平均装载率最高的配送车辆9和平均装载率最低的配送车辆14的各区域装载率和整车厢装载率，如表8所示。

表8 车辆9和14的各区域装载率和整车厢装载率

由表8可知，在配送车辆9和14中，两车区域1的装载率均为88.1%，区域2的装载率均为92.5%，而车辆9区域3，区域4和整车厢的装载率分别比车辆14的相应区域和整车厢的装载率高15.5%，22.5%和15.3%。

4.3 分析与讨论

为进一步探讨不同空间分区模式对优化结果的影响，将车厢空间区域分别平均划分为2个区域，3个区域，4个区域，5个区域，车厢空间不分区域以及按货物类型划分成4个区域六种情况。讨论不同空间分区模式下物流运营成本、配送车辆使用数和车辆平均装载率等的变化，计算结果如表9所示。

表9 不同车厢分区模式下优化结果对比

由表9可知，按货物类型把车厢空间划分为4个区域时配送车辆的平均装载率最高，车辆使用数最少，物流运营成本最低。相比车辆车厢空间不分区域、分成2个区域、3个区域、4个区域和5个区域五种情况，按货物类型把车辆车厢空间划分为4个区域空间的车辆数分别减少了15辆、13辆、7辆、13辆和14辆；车辆平均装载率分别提高了42.92%、39.86%、27.32%、39.86%和41.44%；物流运营成本分别节约了44.71%、37.73%、21.64%、34.87%和39.50。因此，根据客户不同规格型号的货物需求，合理划分配送车辆车厢的区域进行货物配送，可以有效提高车辆装载率，减少车辆使用数和降低物流运营成本。

5 结论

本文研究了带时间窗的三维装载物流配送优化问题，结合客户不同规格货物和服务时间窗的需求进行合理的配送路线调度和货物装载方式优化，建立了包含配送中心的固定成本、配送车辆的运输成本、维修成本、租赁成本和违反时间窗惩罚成本的物流运营总成本最小化和配送车辆空间利用率最大化的双目标优化模型。结合车厢分区模式、货物装载方式与配送路线调度，设计了一种GA-TS混合算法求解模型，该算法有效结合了GA算法的全局搜索性能和TS算法的局部搜索性能，拓展了优化解空间的搜索能力。将GA-TS混合算法与HGA算法、GA-PSO混合算法进行了物流运营成本，平均车辆装载率和求解运行时间的对比分析，进一步验证了本研究提出的混合算法的有效性和合理性。

本文以重庆市某配送中心及其物流配送网络为例，验证了模型和算法的有效性。计算结果表明，三维装载物流配送优化后相比于优化前的方案，物流运营成本和车辆使用数分别减少了44.71%和50%，平均装载率提高了42.92%。此外，不同空间分区模式下物流运营成本、车辆使用数和平均装载率等的对比结果表明，当客户需求商品种类数与车辆的空间区域划分数相等且按货物类型进行空间区域划分时，配送中心的物流运营成本最低，配送车辆使用数最少，车辆平均装载率最高。本研究可为三维装载的物流配送优化问题提供新的研究思路，并有较强的现实意义和应用价值。