基于时间窗指派的污染路径问题

葛显龙,冉小芬

(1.重庆交通大学 经济与管理学院，重庆 400074；2.重庆交通大学 智能物流网络重庆市重点实验室，重庆 400074)

0 引言

为提高物流配送效率、响应国家减排政策，学者们对长期固定的物流配送方案中需求时间窗的合理性展开研究。现有的分销网络中，很多零售商店对货物的交货时间几乎总是在一周的同一天的同一时间，并且会维持一年时间[1]。大多交货的时间是在预定的时间窗之内，这样预定的时间窗一般是因为长期的合作后约定俗成的一种决策，而在不确定客户需求情况下指派的时间窗，称为时间窗指派问题。在固定的时间进行配送，对客户或者零售商而言，可以对库存进行有效管理和人员的合理安排;对物流企业或经销商而言，可以减少配送的可变性，提高配送效率，进而节省成本[2]。而当今的物流配送，不只是考虑单方面(如配送时间、预期成本要求)的配送目标，企业也增强了减排意识，运输领域是温室气体最大的来源之一，是有关节能减排战略方面必须关注的一个环节，而在污染路径问题中，车辆油耗是碳排放的一个重要标准。为此，本文基于时间窗指派对污染路径问题进行研究。

据文献分析，Spliet等[1]引入了时间窗指派车辆路径问题(Time Window Assignment Vehicle Routing Problem,TWAVRP)，该问题是在不确定客户需求的情况下对客户进行指派配送时间窗，当得知客户需求后，对客户进行有目标的车辆配送，以最小化期望总运输成本对连续的时间窗指派车辆路径问题进行研究;Spliet等[2]以最小化期望总运输成本离散的时间窗指派车辆路径问题进行研究，并使用分支定价和切割算法对问题进行求解;Dalmeijer等[3]在时间窗指派车辆路径问题中引入优先不等式，研究了最小化预期旅行成本;Subramanyam等[4]开发了一种新的场景分解算法来解决该随机模型，适应连续和离散的可行时间窗口分配集;Spliet等[5]在与时间相关的时间窗指派车辆路径问题中，考虑了与时间相关的旅行时间，提出了旅行时间计算方法，其目标函数是使得预期的运输总成本包括弧上的旅行成本和驾驶员工资最小化。上述的研究均以最小化总预期成本的单目标进行的，并未考虑给客户指派时间窗后对配送时间的影响。

有关车辆配送的另一方面需要考虑的因素就是考虑车辆排放的问题，其被称为污染路径问题(Pollution Routing Problem, PRP)。Bektas等[6]首次提出的污染路径问题，其中确定了每条弧(i,j)的最优行进速度，以最小化包括燃料消耗、排放和驾驶员成本的综合目标函数;Xiao等[7]根据车辆空载与有效载荷燃料消耗率的关系，考虑载重与行驶距离因素，从而计算车辆的燃料消耗;Eshtehadi等[8]在需求和旅行时间不确定的情况下对PRP进行研究，提出了3种情况下的鲁棒优化技术。目前，有关研究同时考虑碳排放和配送时间的文献较少，因此本文主要集中于碳排放和配送时间两方面的研究。二氧化碳排放量与车辆的燃料消耗率成正比，而车辆的燃料消耗率又取决于车辆类型、车辆的速度、载荷、加速度、环境和交通拥堵等相关参数[6]。根据文献[9]的研究，每辆车都有一个最佳的速度，产生最低的燃料消耗，但一般这个速度低于车辆驾驶者偏好的速度，减少配送时间可以通过较高的行驶速度实现，但与减少碳排放产生了冲突，因此提出了多目标优化的解决方法，其中包含加权法、归一化权重法、ε-约束法和混合法(结合了自适应加权和ε-约束法);Kumar等[10]构建了总运营成本和总排放最小的多目标函数，提出一种混合自适应粒子群优化方法解决带时间窗PRP(Pollution Routing Problem with Time Window, PRP-TW);Suzuki[11]在多目标污染路径问题中考虑了实际的PRP，运用模拟退火和禁忌搜索的混合启发式算法进行求解，先使用模拟退火近似帕累托边界，再使用禁忌搜索改进每个元素的边界;李进等[12]利用一种基于划分的多起点禁忌搜索算法对多车型低碳车辆路径问题进行求解，增强了算法搜索能力的多样性;王君等[13]研究了模糊预约时间窗的车辆路径优化问题，先采用随机车辆配载的方式生成初始解，再使用可行邻域结构与并行禁忌搜索的禁忌搜索算法求解多目标模型，最后得到帕累托最优解;赵燕伟等[14]采用一种基于量子进化算法和粒子群分段优化的算法解决带有时间窗的随机需求车辆路径问题的多目标优化问题;陈玉光等[15]在车辆配送中研究了准时送货与最小油耗问题，运用改进的粒子群算法解决了配送时间和油耗最少的双目标模型。

为此，针对时间窗指派污染路径问题(Time Window Assignment Pollution Routing Problem, TWAPRP)，同时考虑成本(碳排放成本和旅行成本)与配送时间最小化的双目标优化，建立TWAPRP双目标模型；并设计了混合遗传—禁忌搜索算法对TWAPRP模型进行求解；最后根据需求场景模拟需求不确定性，进行数值实验，从而验证模型与算法的有效性和适用性。

1 问题描述

如图1所示为时间窗指派前后两种不同配送方案的示意图。图1a和图1b分别表示具有1个配送中心、8个常配客户的配送网络，图1b中客户集下的数字代表客户的时间窗。图1a为没有给客户指派时间窗前的配送方案，由于客户对货物的配送时间并没有很强的要求，只是以物流企业的配送到达时间为准，经过长期由同一物流企业配送后，客户与配送企业会根据业务运作经验约定配送的时间窗。为满足到达时间一致性，在不确定客户需求的情况下，物流企业根据历史数据确定时间窗宽度，以便给客户指派一个时间窗(如图1b)。当客户实际订单生成后，则重新优化新的配送方案，进而满足物流企业在配送过程中的碳排放成本和旅行成本。

2 模型建立

2.1 时间窗指派策略与碳排放成本的计算

(1)时间窗指派策略

在TWAPRP的第一阶段，对客户进行时间窗指派；第二阶段，针对每个需求场景，寻求遵守各约束的车辆配送路径方案，并使得成本最小化与配送时间最小化。第一阶段的时间窗指派是内生时间窗指派，由客户需求产生配送时间。因此，为模拟需求的不确定性，引入需求场景及场景发生概率。第二阶段简化为带有指定时间窗的污染路径问题，根据许诺给客户的时间窗，进行有目标的配送。

对客户进行时间窗指派的主要目的是对客户进行配送时能够使到达时间一致。首先确定客户的时间窗宽度wi，即基于每次给同一客户配送最早与最晚到达的时间差tdif的历史数据，限制时间窗宽度tdif≤wi；然后确定客户i服务开始时间yi，根据内生时间窗序列为客户指派一个时间窗；最后根据需求场景s发生的概率，对客户进行配送，并满足目标条件。如图2所示为历史配送数据中不同配送周期配送到客户的时间跨度tdf与时间窗宽度wi的关系，图2中深灰色代表最早和最晚服务的客户。tdif1表示客户1的最早与最晚的到达时间差，tdif2表示客户2的最早与最晚的到达时间差，w1表示客户1的指派时间窗宽度，w2表示客户2的指派时间窗宽度。显然，指定的时间窗宽度可以满足客户对配送的时效要求。

(2)碳排放成本的计算

PRP中有关燃料消耗的计算是Bektas等[6]基于Barth等[16]和Barth等[17]描述的综合排放模型，其给出的目标是基于燃油在给定的一个时刻估计燃料消耗的瞬时模型，Demir等[18]延伸应用了PRP的规划。根据瞬时模型，得到燃料消耗率，如式(1)所示：

FR=ζ(μBV+P/η)/κ。

(1)

式中μ和κ为常数，参数

P=Ptract/ηtf+Pa。

(2)

参数Ptract可由式(3)计算为：

Ptract=(Mτ+Mgsinθ+0.5CdρAv2+

MgCrcosθ)v/1 000。

(3)

式中：M=w+f；w为车辆自重；f为车辆负载。车辆在弧上(i,j)的油耗是与距离d、速度v和负载f有关的函数，表示为：

F(v)=λ(kNV+wγαv+βγv3+γαfv)d/v

=λ[kNVd/v+βγdv2+γα(w+f)d]。

(4)

其中λ,γ,α,β为常数。为了简化表示，令λ=ζ/(κψ)和γ=1/(1 000ntfη)为常数，α=δ+gsinθ+gCrcosθ和β=0.5CdρA分别为车辆弧特定常数和车辆特定常数。δ,θ,v,d,w和f分别表示车辆的加速度、道路坡度、速度、空车重量和有效载荷。如表1所示为碳排放计算相关参数的定义及经典值。

本文假设车辆在无坡度的道路行驶，燃料消耗和二氧化碳排放量的成本可以估算为TFco2=fcF，则在时间窗指派污染路径问题中，燃料和碳排放成本函数表示如下所示：

(5)

表1 碳排放计算相关参数定义

3.2 建立TWAPRP模型

模型中使用到的符号介绍如下：

s为需求场景，s∈S，其中S表示需求场景的集合;

ps为需求场景s中的发生概率;

[si,ei]为外生时间窗的限制，开始时间为si，结束时间为ei;

yi为客户i的时间窗的开始时间，yi∈[si,ei-wi];

wi为客户i的时间窗宽度;

tij为车辆在弧上(i,j)的行驶时间;

cij为车辆在弧上(i,j)的旅行成本;

目标函数由两部分构成:第一部分Z1为碳排放成本和在弧上的固定旅行成本；第二部分Z2为配送时间。其目的是使得这两部分最小化。

(6)

(7)

s.t.

(8)

(9)

(10)

(11)

(12)

(13)

∀i∈V0,j∈V0,s∈S;

(14)

(15)

(16)

(17)

yi∈[si,ei-wi],∀i∈V0;

(18)

(19)

∀(i,j)∈A,r∈R;

(20)

∀(i,j)∈A,s∈S;

(21)

(22)

4 设计求解算法

车辆路径问题是NP-难问题，当客户规模增加到50后，难以使用精确算法求解，从而转向启发式算法[19]。根据本文模型的特征，使用混合遗传—禁忌搜索算法进行求解，结合遗传算法具有良好的全局搜索能力和禁忌搜索算法具有优秀的局部搜索能力[20-21]，设计改进的混合遗传—禁忌搜索算法，对本文模型进行求解。

4.1 编码方式及初始种群的生成

本文采用遗传算法的自然数序列编码方式对配送中心和客户进行编码，由n个客户构成的配送网络需要m辆车进行配送，可以构成一条编码长度为n+m+1的染色体。其中n表示具有n个客户的自然数全排列，具有m+1个0，0表示配送中心。如R(0-3-6-1-5-8-0-4-2-7-0)表示r1(0-3-6-1-5-8-0)和r2(0-4-2-7-0)两条子路径。

遗传算法对初始种群的要求不太高，但是一个良好的初始种群有利于快速地找到较好的解，因此采用扫描算法[22]生成群规模为N的初始种群P1。

4.2 时间窗指派实现

在本文配送过程中，得知客户需求后，根据为客户指派的时间窗，满足约束条件进行配送，其中对客户的时间窗指派主要是基于长期合作得到的经验结果。在算法实现部分，客户编码完成后，对客户提前进行时间窗指派的设置，以一条染色体为例，假设有8个客户，主要操作过程如表2和表3所示。

表2 客户时间窗指派

表3 到达客户时刻表

4.3 混合遗传—禁忌搜索

得到初始种群P1后，对每条染色体进行相应的判断，具体操作步骤如下：

(1)适应度评价函数的选择。本文采用目标函数即两个目标组合优化值的倒数作为遗传算法的适应度函数，适应度值越大，被选择的概率就越大，遗传给下一代的几率也就越大，反之就越差。

(2)选择操作。为保留优秀个体，从初始种群中选择适应度大的前20%的个体直接进入下一代，采用最佳保留的轮盘赌选择的方法进行选择操作。

(3)交叉和变异操作。为增加种群的多样性，对种群进行交叉概率为pc的改进的顺序交叉操作和变异概率pm的变异操作，得到新的种群。

(4)遗传操作得到的新种群P2中的解作为禁忌搜索算法的初始解，进行局部邻域寻优操作。邻域算子如下所示：

邻域算子1随机选择一条路径r1，选中r1中的部分元素(数量多于两个元素)，进行顺时针逆转。

邻域算子2随机选择一条元素数目大于4的路径r1，选中4个连续的元素，前后两个元素分别进行顺时针逆转，如2 675逆转后为6 257。

邻域算子3随机选择一条路径r1，选中其中一个元素，将其插入到另一条路径中。

邻域算子4随机选择两条路径r1和r2，分别选中每条路径的一个元素，将选中的两点的后续元素进行路径间交换。

(5)禁忌表更新及特赦准则。为避免算法陷入局部最优，需判断邻域解bsf是否优于历史最优解Bsf。为此，特赦准则设有两种情况[23]：①若邻域解优于历史最优解，则更新历史最优解为bsf，并将最优解未变化次数更新为pp=0。此时判断禁忌表是否被充满，若禁忌表已满，则赦免禁忌表中第一个元素，将其他元素左移一位，将禁忌对象插入到禁忌表的尾部；否则，直接将禁忌对象插入到第一个不为0的位置。②若邻域解劣于历史最优解，则将最优解未变化次数pp=pp+1，继续判断下一个邻域解是否满足禁忌条件，当达到禁忌次数时最优解未变化，此时禁忌解Bsf更新为最优解。

(6)对P2进行禁忌搜索后的解，判断是否满足可行解池popsize的条件。若满足，则判断下一步，是否能够满足算法最大迭代次数的终止条件，若满足终止条件，则输出最优结果；否则继续进行遗传禁忌搜索操作。如图3所示为混合遗传—禁忌搜索算法的简要流程图。

5 数值实验

采用MATLAB(R2015b)编写混合遗传—禁忌搜索算法程序，在Intel(R)Core(TM)i7 CPU 2.0 GHz，内存8 GB的计算机上运行。算法参数：种群数量Pop=500，迭代次数G-max=300，交叉概率Pc=0.8，变异概率Pm=0.02，可行解池popsize=50，禁忌长度T-list=3，pp=200。

5.1 算例生成

5.2 算例结果分析

为验证模型的有效性，取50个客户点对模型进行求解，每个场景求解两次，每个客户的指派时间窗在不同的情景中是相同的，其时间窗指派如表4所示，求解得到的3种情景下的结果如表5所示。由表5可知每种场景的成本Fc、行驶距离dis、配送时间Tt、程序运行时间tt和车辆数量。

表4 时间窗指派表

续表4

表5 三种场景下的求解结果

从表5中观察相同场景下程序运行的结果Fc与Ts，得到的解为非劣解，为此可证明模型的可行性和算法的有效性。在不同场景下，使用的车辆数目也不一样，其中主要是因为各个场景下客户的需求发生了改变，需求越高，使用的车辆数越多；但在不同场景下的成本、行驶距离、配送时间和程序运行时间的指标差异不是很大，说明客户的需求改变对这4个指标影响不大，但在车辆使用数量方面有一定差别。

5.3 算法性能分析

为进一步证明算法的有效性，分别对不同数据集在基本的禁忌搜索算法(用于求解双目标的ε-约束法[15])和混合遗传—禁忌搜索算法进行求解，每个算例是对应算法运行后取9次较优解的平均值，得到的结果如表6所示。由表6可知，随着客户集增加，两种算法的各个指标量也逐渐增加。相对某一客户集而言，混合遗传—禁忌搜索算法在成本、行驶距离和配送时间3个指标都比禁忌搜索算法更优，以客户集20为例，本文算法比基本禁忌搜索算法在成本、行驶距离和配送时间方面分别改善了7.00%、44.78%和2.94%；30个客户集在相应方面分别改善了8.44%、50.78%和8.23%；50个客户集在相应方面分别改善了7.74%、50.40%和4.26%。但是在算法运行速度方面，禁忌搜索算法更胜一筹，说明混合遗传—禁忌搜索算法确实在寻优方面结合了禁忌搜索的局部搜索的优点和遗传算法全局搜索的长处，也证明了混合遗传—禁忌搜索算法对解决本文模型的有效性。

表6 禁忌搜索算法与混合遗传—禁忌搜索算法比较

5.4 考虑不同优化目标的比较结果

为了验证本文所提综合优化目标(FC)更符合物流配送运作需求，将其与VRP传统优化目标总行驶距离(TD)和总配送时间(TT)进行对比分析，其目标函数的表达方式如式(23)和式(24)所示：

(23)

(24)

为便于实验结果的分析，记录了碳排放成本和旅行成本(fc)、行驶距离(dis)和配送时间(ts)3个测量指标。主要分析两个方面：不同客户集下随机场景的测量指标和同一客户集下不同场景(以30个客户为例)的测量指标。所有实验数值以FC的实验结果为基准进行归一化处理，所有实验数据都是根据混合遗传—禁忌搜索算法运行后取9次较优解的平均值进行处理。

表7 不同客户集下随机场景的测量指标结果

从表7可看出，TD和TT都比FC都需要更多的成本(碳排放成本和旅行成本fc)，且TT需要的更多，TD在成本方面平均增加了4.95%，且同时可以得知，TD在配送时间方面也耗费更多，平均增加了1.41%，但在行驶距离方面却平均减少了6.95%，这说明在以距离为优化目标的情形下，TD虽然在成本有所增加，但是尽可能满足了优化目标。TT在比FC在成本方面和行驶距离都增加了，行驶距离的增加幅度比成本增加幅度小，在成本方面平均增加了7.76%，行驶距离平均增加了1.54%，然而在配送时间方面比FC减少了，配送时间平均减少了3.34%，这说明TT与FC的关系具有更加紧密的背反关系。由客户集方面可知，在TD中，随着客户集的增加，各指标基本维持相应的增加趋势，但30个客户的指标稍微不同；在TT中，随着客户集的改变，各指标的变化无明显的规律。这说明配送客户的大小也会对指标产生一定影响，但也不排除场景的影响因素。

表8 同一客户集下不同场景的测量指标结果

由表8可知，三种场景中成本方面均有所增加，行驶距离方面均有减少了。不管在场景1、2和3，TD和TT比FC耗费更多的成本，但是场景1需要更多的成本。TD比FC在成本和时间两个指标都需要更多，TD的成本平均增加6.37%，随着客户需求的减少，成本指标相应减少，TD的行驶距离平均减少了7.75%，且在场景1中减少了高达11.45%，TD的配送时间平均增加了2.49%。TT在成本方面平均增加了6.55%，但在行驶距离和配送时间方面都减少了，在行驶距离方面平均减少了0.55%，在场景1中减少最多，减少了4.37%，但在另外两个场景中的行驶距离均增加了，在配送时间方面平均减少了2.13%，而在场景1中减少的时间最多，平均减少了4.49%。根据场景由高到低观察，随着场景的需求增加，成本指标相应增加，且在需求最高的场景中，成本增长最大，但行驶距离和配送时间最小。这说明客户的高需求能够让企业集中配送，耗费更少的时间，但同时需要更多的配送车辆，因此在碳排放上，因客户需求增加而增加。

6 结束语

本文研究了基于指派时间窗情形下的污染路径问题，考虑到客户配送前的不确定需求和配送前需给客户指定配送时间窗的因素，引入了需求场景的概念，构建了基于TWAPRP的最小成本(碳排放成本和旅行成本)与最小配送时间的双目标优化模型，并根据模型的特征设计了混合遗传—禁忌搜索算法进行求解。求解结果表明了配送时间与成本之间有着制约关系，验证了模型的可行性和算法的有效性。将禁忌搜索算法与混合遗传—禁忌搜索算法的求解结果进行对比分析，进一步验证了本文算法的有效性。最后，以传统车辆路径的最短行驶距离和最小配送时间为目标与本文所提综合优化目标为基准进行对比分析，验证了所设计算法在减少成本和配送时间的有效性，同时也表明不同企业的配送方案会因选择的目标不同而存在差别。

然而，在实际配送过程中，充满着各种不确定因素，如交通拥堵、时变旅行等。未来可以将这两方面进行结合，并进行深入研究。