考虑交通拥堵及工作量平衡性的一致性车辆路径问题

（北京交通大学经济管理学院，北京100044）

（北京交通大学经济管理学院，北京100044）

为研究快递公司在提供一致性配送服务时，交通拥堵以及快递人员工作量平衡性因素对配送路径的影响，在传统车辆路径问题研究的基础上，提出了考虑拥堵和工作量的一致性车辆路径问题，并构建了混合整数规划模型.针对该模型的NP难性质，提出了基于模板路径的两阶段模拟退火算法（template-based simulated annealing heuristic，TSA）.该算法通过构建模板路径求解初始路径方案，再利用模拟退火算法优化路径方案，降低车辆总行驶时间.将该模型和算法应用于3组基准数据（benchmark data set）的数值实验，结果表明：本文模型和算法能有效解决此类问题，交通拥堵使最优配送路径的总行驶时间平均增加18.38%，使快递人员在任意两天到达同一顾客的最早与最晚时刻之差平均增加12.92%；当快递人员配件量的不平衡性平均下降35.82%后，二者仅分别平均增加2.29%和1.68%.

一致性车辆路径问题；快递业；交通拥堵；工作量平衡性

自文献［1］提出车辆路径问题（vehicle routing problem，VRP）以来，VRP问题引起了学者们的广泛关注.文献［2-4］对VRP问题进行了各类扩展，文献［5］对VRP问题做了详尽的综述.近年来，电商的迅速崛起促进了快递市场高速发展，2013年中国网络购物交易规模达到1.85万亿，其中70%产生了快递量［6］.顾客对快递服务质量也提出了越来越高的要求，文献［7］指出，顾客对高质量快递服务的重要衡量指标是服务一致性，文献［8］基于服务一致性要求提出了一致性车辆路径问题.众多位学者从应用、模型改进和算法优化等方面进行了进一步的研究［7，9-13］.

文献［14］考虑了司机工作量的平衡性，但是忽略了交通拥堵因素.这两个因素在快递公司提供一致性服务的过程中都很重要.

（1）交通拥堵

传统一致性车辆路径问题中，两点之间的行驶时间是固定的，即车辆以匀速行驶，此假设在交通拥堵情况日益严重的现状下并不成立，以北京二环为例，部分主干路早晚高峰时段运行速度低于15 km/h，全路网工作日日均拥堵时间超过4 h［15］，因此，按照此假设规划得到的配送路径将产生巨大偏差.文献［16］提出，由于交通拥堵造成的行驶时间不确定性影响了物流运作效率，并导致一致性服务受到重大影响.需要指出的是，越来越多的消费者在电商平台上购买的大型电器，只能通过大中型车辆进行配送，不具备小型机动车辆的灵活性，因此受交通拥堵影响巨大.

（2）工作量平衡性

越来越多的学者开始关注公平性问题，例如，文献［17］指出，对快递人员来说，一方面其收入构成很大一部分取决于计件工资，快递人员之间的派件数量差别过大会直接导致明显的收入差异；另一方面，因为一致性车辆路径问题的特殊性，要求快递人员在一个时间段内对同一个顾客进行配送服务，若对快递人员所服务片区中的顾客分配不当，会加剧工作量的不平衡性.

综上分析，本文提出了考虑交通拥堵和快递人员工作量平衡性的一致性车辆路径问题，建立了基于该问题的混合整数规划模型.该模型保证了服务一致性要求，并利用3组基准数据集的数值实验，检验了交通拥堵和工作量平衡因素对快递公司运营成本和服务质量的影响.

1 模型建立

1.1 相关假设及参数定义

一致性车辆路径问题定义为有向图G=｛N，A｝，其中N=｛0，1，2，…，n｝表示点集合，点0代表快递站，NC=N∉｛0｝对应各需求点顾客；A=｛（i，j）∶i，j∈N，i≠j｝表示弧集合.

本文将每位顾客视为运输网络中的一个需求点.每位顾客在D天中的某一天或某几天有需求，且提前已知所需服务时间与需求量.K辆完全相同的车（即K名司机）为顾客服务，每位顾客每天最多只能被服务一次.车的最大容量为Q，每天都在同一时刻从快递站出发，且在T个时间单位内返回.为保证服务一致性，司机在顾客有需求的几天中，任意两天到达该顾客的最早与最晚时刻之差不超过L个时间单位.令在第d天为顾客i的服务时间为tid，需求量为qid，任意两个顾客之间的行驶时间对应着对称矩阵（未考虑拥堵因素）T=（tij），即tij=tji.

本问题为混合整数规划问题，引入以下参数：车辆在第d天到达顾客i处的时刻为taid.若在第d天顾客i有需求，则令0-1变量wid=1，否则wid=0；引入决策变量xijkd，如果车辆k在第d天服务完顾客i后紧接着服务顾客j，则xijkd=1，否则xijkd=0；引入决策变量yikd，如果在第d天由车辆k为顾客i提供服务，则yikd=1，否则yikd=0.本问题目标函数是路径规划后D天中车辆的总运行时间最短.

1.2 交通拥堵

文献［18］根据不同的时间段，将车辆行驶速度分为4个等级.根据文献［19］，70%～87%的拥堵时间在早晚高峰.本文中假设每天上午8：00～9：00、晚上18：00～20：00分别为早晚高峰时间段，车辆若在这两个时间段中行驶会处于低速状态，否则处于常速状态.假设所有车辆均每天上午8：00从快递站出发，且必须在24：00之前返回快递站.如果某位司机在第d天为顾客i服务完毕的离开时刻taid+tid处于早晚高峰时间窗中，那么该车辆在前往下一顾客处的行驶路程中，行驶时间会增加μ倍（拥堵因子μ≥0）.引入0-1变量σid，

车辆在两个顾客之间的实际行驶时间为tij（1+μσid）.

1.3 工作量平衡性

将司机k在D天中的工作量定义为

即在D天中由司机k服务的所有顾客的总需求量，根据文献［20］提出的用均方差形式刻画工作量不平衡性，定义快递人员工作量的不平衡量为

为体现快递公司对此问题的不同重视程度，引入常量M，可以得到以下约束条件：

fWl≤M.

1.4 混合整数规划模型

混合整数规划方程如下：

式中：wid为0-1变量，若顾客i在第d天有需求，则令wid=1，否则为0；

widα为0-1变量，若顾客i在第（d-α）天有需求，则令wid-α=1，否则为0；

wid，β为0-1变量，若顾客i在第（d-β）天有需求，则令wid-β=1，否则为0；

taid为车辆第d天到达顾客i处的时刻.

约束式（1）和（2）要求每辆车每天在时刻0从快递站出发（实际应用中可将时刻0设置其他时刻）；约束式（3）保证了每位顾客每天最多被服务一次；约束式（4）限制了车的容量为Q；约束式（5）为各顾客处流量守恒约束；快递人员的一致性要求通过约束式（6）保证；约束式（7）和（8）为考虑了交通拥堵后车辆到达各顾客的时刻，约束式（7）还可以防止产生子回路；约束式（9）同样为了防止子回路的产生；约束式（10）保证了各快递人员必须在T个时间单位内返回；约束式（11）保证了快递人员在任意两天dα和dβ到达顾客i的最大时间差不超过L个时间单位；约束式（12）保证了整体工作量的不平衡量不超过M个需求单位；约束式（13）定义了决策变量和相关参数.

2 用TSA算法求解模型

一致性车辆路径问题是典型NP难问题，根据服务一致性的特征，文献［8，11］提出了模板路径思想，本文在此基础上提出了基于模板路径的模拟退火法（template-based simulated annealing method，TSA）求解路径方案，算法分析和编码过程可参考文献［11-21］的研究成果.

2.1 TSA算法基本思想

用TSA算法先后求解主、从两个子问题，其中主子问题针对多天需求顾客利用贪婪算法构建模板路径，确定为多天需求顾客提供服务的快递人员及访问先后顺序；从子问题则根据所有顾客的实际需求，首先逐天删除当天没有需求的多天需求顾客，再通过贪婪算法插入仅当天有需求的单天需求顾客，得到每天路径方案.SA（simulated annealing）算法分别应用到两个子问题中优化初始模板路径和初始路径方案［21］.

2.2 模板路径获得

利用TSA算法，先将顾客分为两个子集：多天需求顾客集合Nf和单天需求顾客集合Nnf.因为模板路径中只包含多天需求顾客，作为最终路径方案的参考，可以保证多天需求顾客每天都由同一快递人员提供服务.模板路径的求解过程如下：

（1）对多天需求顾客集合Nf进行初始化，求得各多天需求顾客在整个服务时间范围中的平均需求量qi和服务时间tsi，

式中：qid为顾客i在第d天的需求量；

tid为顾客i在d天需要被服务的时间.

（2）再为每位多天需求顾客安排一辆车进行服务，然后利用贪婪算法获得模板路径，优先选择可使合并后总行驶时间减少量最多的两条路径进行合并，当路径数目等于K时停止.每次合并后，立即对新产生路径对车容量限制和司机最长工作时间约束进行可行性检查，只接受可行的新路径.

2.3 最终路径方案获取

基于模板路径获得最终路径方案.首先，根据各天实际需求情况，删除模板路径中当天没有需求的多天需求顾客；然后，插入仅当天有需求的单天需求顾客.单天需求顾客插入位置的选择遵循贪婪算法：选择插入后使总行驶时间增量最少的位置进行插入.在每次插入顾客后，立即对新路径进行可行性检查，除车容量限制和司机最长工作时间约束外，还需要检查多天需求顾客的时间一致性要求，只接受可行的新路径.

2.4 SA法

SA算法主要涉及6个参数：Iiter、Nnon-impr、W0、Wf、B和θ，其中，Iiter表示在特定温度进行邻域搜索的次数；Nnon-impr表示能接受的通过连续降温当前最优解仍未被优化的最大次数；W0和Wf分别表示起止温度；B为Boltzmann常数；θ（0＜θ＜1）用于控制温度下降速度.在SA算法开始时将初始温度W设定为W0，初始最优解Sbest和当前解S均设为初始模板路径或初始路径方案，定义δobj（S）为路径方案S对应的总行驶时间，tbestT为最优解Sbest对应的总行驶时间.在某个温度下的每次迭代产生邻域解Sneigh，令Δ=δobj（Sneigh）-δobj（S）.若Δ＜0，则接受Sneigh为新的当前解；若Δ≥0，则随机产生一个0到1的数v2～R（0，1）.如果

v2＜exp（-Δ/（BW）），则接受Sneigh为当前解.一旦找到更优解，更新Sbest和tbestT.在每个温度进行Iiter次迭代后，温度下降到θW.SA法终止的条件有两个，满足其一即可：

（1）经过连续Nnon-impr次降温后，当前的最优解仍未被优化；

（2）当前的温度已经下降到终止温度Wf或以下.

当算法停止时，即可从Sbest读取近似最优方案.

3 数值实验

3.1 参数设定及数据说明

在实验开始前，先选取一组数据反复测试不同参数组合来确定实验的最终参数设置.对每组参数组合，本文进行了5次测试，测试参数可选值如下：

Iiter=｛1 000N，3 000N，5 000N，7 000N，9 000N｝， N为顾客数；

Nnon-impr=｛100，200，300｝；

W0=｛10，20，30，40｝；

Wf=｛0.01，0.10｝；

B=｛1/10，1/8，1/6，1/4，1/2，1｝；

θ=｛0.96，0.97，0.98，0.99｝.

在权衡算法的收敛速度和解的质量后，本文选定如下参数：

Iiter=9 000N， Nnon-impr=100，

W0=20， Wf=0.01，

B=1/6， θ=0.98.

本文选择文献［8］给定的基准数据集中的3组中等规模数据进行实验：Christofides_3_5_ 0.7，Christofides_6_5_0.7和Christofides_12_5_ 0.7，用数据集1、2、3分别代表3组数据.3组数据的服务时间范围为5 d，顾客数从50人到199人不等，各天具体的需求量和服务时间均提前已知.

3.2 交通拥堵检验

为刻画不同的交通拥堵程度，拥堵因子μ在（0，1）中取11组值.针对每组实验数据，均给出了总行驶时间ttotal和时间一致性指标lmax.用和分别表示交通拥堵比不存在交通拥堵情况下ttotal和lmax增加量的百分比，实验结果如表1所示.

从表1可知，相较于μ=0的第1列数据，在考虑交通拥堵因素后，各组数据的ttotal和lmax均有所增加.3组数据的总行驶时间ttotal分别平均增加了20.65%、8.56%和25.94%，整体平均增加18.38%，可以直观地理解为由于交通拥堵造成低速行驶导致总行驶时间增加.对于时间一致性指标lmax，3组数据中有2组数据的lmax大幅增加，其中，第1组数据的lmax值平均增加了18.87%，第3组数据的lmax值平均增加了18.14%，而第2组数据小幅增加1.74%，整体平均增加12.92%.造成lmax增加的原因是交通拥堵导致行驶时间的不确定性增加，最终扰乱了原有路径规划，如图1所示.

图1中，ts为服务时间，tt为行驶时间，灰色部分表示常速行驶，黑色部分表示低速行驶，服务时间共2 d，A和B为多天需求顾客，C为单天需求顾客.

假设A在2 d中均先于B接受服务，C只在第2天有需求，且在A和B之间接受服务，从图1（b）可以看出，快递人员在服务完C后的时刻恰好处于晚高峰期间，因此，快递人员前往顾客B处的行驶时间增加，最终导致第2天顾客B的服务时间增加了1 h.综上分析，交通拥堵对快递公司的运营成本ttotal和服务质量lmax均会造成较大负面影响，若在路径规划中忽略这些因素，规划方案会严重偏离实际情形.

表1 不同交通拥堵情况下数据结果Tab.1 Results for data sets of different degrees of traffic congestion

图1 交通拥堵图例Fig.1 Example of traffic congestion

3.3 工作量平衡性检验

区别于传统的一致性车辆路径问题，本文研究一致性车辆路径问题时增加了新约束条件式（12）.

为刻画快递公司对工作量平衡性问题的不同重视程度，令

M=γM′，

式中：M′为司机平均工作量水平，

γ为重视程度因子，其值越小表示快递公司越重视此问题.

在本实验中，γ在（1，2）中取11个值，检验了工作量平衡性对快递公司运营成本和服务质量的影响.针对每组实验数据，除指标ttotal、lmax、和外，本文还给出了不同重视程度下快递人员的平均工作不平衡量bwl，以及随着重视程度提高导致快递人员平均工作量比γ=2时平均工作量减少的百分比，结果如表2所示.

由表2可知，随着重视程度的提高，ttotal和lmax都呈现增长趋势，以数据集3为例，相较于重视程度最低γ=2时，ttotal和lmax分别平均增加了3.13%和1.60%.ttotal和lmax增加是因为新约束条件导致解空间缩小.

从表2可以发现，小幅度增加ttotal和lmax可以使bwl大幅度提高，以数据集2为例尤其明显，当ttotal和lmax分别平均增加1.00%和3.38%时，bwl平均下降了50.01%.

从整体上看，当快递人员的工作量平衡性平均提高35.82%时，仅使总行驶时间和快递人员在任意两天到达同一顾客的最早与最晚时刻之差分别平均增加2.29%和1.68%.由此可见，快递公司在进行路径规划时，提高对快递人员工作量平衡性的重视程度，不会以大幅度提高运营成本或降低服务质量作为代价.

表2 对工作量平衡性不同重视程度下数据结果Tab.2 Results for data sets of different degrees of emphasis on workload balance

4 结束语

本文提出了考虑交通拥堵和工作量平衡性的一致性车辆路径问题，此问题从两方面体现出了重要现实意义：

（1）交通拥堵逐渐成为不可避免的日常问题，对快递公司的一致性服务提出了新挑战，若在路径规划中忽略此因素，将得到不切实际的路径方案；

（2）快递人员通常以计件工资的形式获取收入，若不能合理安排各个快递人员的派件量，将会加剧快递人员之间的收入差距.针对新问题，本文设计了两阶段TSA算法，并通过对3个数据集的数值实验，验证了交通拥堵和工作量平衡性因素对快递公司运营成本和服务质量的影响.

实验结果表明：交通拥堵会大幅度提高运营成本，服务质量也会有所下降；当小幅度提高运营成本且服务质量下降不多的情况下，快递人员的工作量平衡性将得到显著提高.

［1］ DANTZIG G B，RAMSER J H.The truck dispatching problem［J］.Management Science，1959，6：80-91.

［2］ NAGY G，WASSAN N A，SPERANZA M G，et al.The vehicle routing problem with divisible deliveries and pickups［J］.Transportation Science，2015，49（2）：271-294.

［3］ 邹书蓉，黄晓滨，张宏伟.有容量约束车辆路径问题的多目标遗传算法［J］.西南交通大学学报，2009，44（5）：782-786.

［4］ SCHNEIDER M，STENGERA，GOEKED.The electric vehicle routing problem with time windows and recharging stations［J］.Transportation Science，2014，48（4）：500-520.

［5］ LAPORTE G. Fiftyyearsofvehiclerouting［J］. Transportation Science，2009，43（4）：408-416.

［6］ 王雅琪，杨雪梅.电子商务与快递业融合发展的动力机制研究［J］.物流工程与管理，2015，37（1）：150-151.

［7］ KOVACS A A，PARRAGH S N，HARTL R F.A template-based adaptive large neighborhood search for the consistent vehicle routing problem［J］.Networks，2014，63（1）：60-81.

［8］ GROER C，Golden B，WASIL E.The consistent vehicle routing problem［J］.Manufacturing Service and Operations Management，2009，11（4）：630-643.

［9］ WOODWARD C A，ABELSON J，TEDFORD S，et al. Whatis important to continuity in home care？perspectives of key stakeholders［J］.Social Science and Medicine，2004，58（1）：177-192.

［10］ FEILLET D，GARAIX T，LEHUEDE F，et al.A new consistent vehicle routing problem for the transportation ofpeople with disabilities［J］. Networks，2014，63（3）：211-224.

［11］ TARANTILIS C D，STAVROPOULOU F，REPOUSSIS P P.A template-based tabu search algorithm for the consistent vehicle routing problem［J］.Expert Systems with Applications，2012，39（4）：4233-4239.

［12］ GOLDEN B L，KOVACS A A，HARTL R F，et al. The generalized consistent vehicle routing problem［J］. Transportation Science，2015，49（4）：796-816.

［13］ LUO Z X，QIN H，CHE C H，et al.On service consistency in multi-period vehicle routing［J］. European Journal of Operational Research，2015，243（3）：731-744.

［14］ JANSSENS J，DEN BERGH J V，SORENSEN K，et al.Multi-objective microzone-based vehicle routing for courier companies： From tactical to operational planning［J］. European Journal of Operational Research，2015，242：222-231.

［15］ 北京交通发展研究中心.北京市2010年交通运行报告［R］.北京：北京交通发展研究中心，2011.

［16］ FIGLIOZZI M A.The impacts of congestionon commercial vehicle tour characteristics and costs［J］. Transportation Research Part E，2010，46：496-506.

［17］ TAN T F，NETSSINE S.When does the devil make work？an empirical study of the impact of workload on worker productivity［J］.Management Science，2014，60（6）：1574-1593.

［18］ SOYSAL M，BLOEMHOF-RUWAARD J M，BEKTAS T.The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations［J］. International Journal of Production Economics，2015，164：366-378.

［19］ KOK A L，HANS E W，SCHUTTEN J M J.Vehicle routing under time-dependent travel times：the impact of congestion avoidance［J］.Computers and Operations Research，2012，39：910-918.

［20］ JANSSENS J，DEN BERGH J V，SORENSEN K，et al.Multi-objective microzone-based vehicle routing for courier companies： from tactical to operational planning［J］. European Journal of Operational Research，2015，242：222-231.

［21］ YU V F，LIN S Y.A simulated annealing heuristic for the open location-routing problem［J］.Computers and Operations Research，2015，62：184-196.

考虑交通拥堵及工作量平衡性的一致性车辆路径问题

刘恒宇， 汝宜红

Consistent Vehicle Routing Problem Considering Traffic Congestion and Workload Balance

LIU Hengyu， RU Yihong
（School of Economics and Management，Beijing Jiaotong University，Beijing 100044，China）

In order to investigate the effects of transportation congestion and workload balance on the delivery routing of express delivery companies which wish to provide consistent services，a consistent vehicle routing problem considering traffic congestion and workload balance was proposed and a mixed integer programming model for this problem was constructed.In view of the model's NP-hard property，a two-phase template-based simulated annealing method（TSA）was applied to solve this problem.The TSA attains an initial route plan by constructing template routes first，and then optimizes them using the simulated annealing method to decrease the total travel time.To verify the validity of the proposed model and algorithm，numerical experiments were conducted using three benchmark data sets.Results show that the model and TSA can solve this problem effectively.The traffic congestion will significantly increase the total travel time by an average of 18.38%and increase the difference between the earliest and latest arrival time at the same customer within any two days by an average of 12.92%.Besides，when the average difference of the delivery men＇s shipment quantity decreases by 35.82%，the total travel time and the difference between the earliest and latest arrival time at the same customer are only increased by 2.29%and 1.68%，respectively.

book=932,ebook=121

consistent vehicle routing problem；express delivery industry；traffic congestion；workload balance

0258-2724（2016）05-0931-07

10.3969/j.issn.0258-2724.2016.05.016

U116.2

A

2015-09-07

云南省教育厅课题（SYSX201412）；北京市科委课题（Z141100003614059）

刘恒宇（1990—），男，博士研究生，研究方向为城市物流，E-mail：14113138@bjtu.edu.cn

汝宜红（1953—），女，教授，博士生导师，研究方向为逆向物流，E-mail：yhru@bjtu.edu.cn

刘恒宇，汝宜红.考虑交通拥堵及工作量平衡性的一致性车辆路径问题［J］.西南交通大学学报，2016，51（5）：931-937.

（中文编辑：秦萍玲 英文编辑：兰俊思）