基于顾客时间满意度的车辆路径问题

李常敏,陶 颖,彭 显,姚连杰

(上海大学管理学院,上海200444)

1 提出问题

车辆路径问题(vehicle routing problem,VRP)是物流配送研究中的核心部分,配送路线的选定对企业的配送成本起决定性作用.经典VRP模型关注的是所有配送车辆的配送路径最短、耗费时间最少的配送方案[1],带时间窗VRP(vehicle routing problem with time windows,VRPTW)是在经典的VRP基础上增加时间窗约束衍生而来的.VRPTW模型在日常生活中有着广泛的应用:银行的运钞车调度、邮政配送、工厂废弃物回收、校车路线和准时化(just in time,JIT)生产调度问题等.

针对VRPTW的严格时间约束,Balakrishnan[2]提出了带软时间窗的VRP(VRP with soft time windows,VRPSTW)进行改进,即在超出顾客规定的时段外,运用该模型可以通过支付合理的惩罚来补偿.武佳佳等[3]认为,VRPSTW是在经典的VRP基础上增加了时间窗约束条件的一种变化形式:①客户配送中心希望在服务时间内服务时,客户配送中心接受货物且满意度高,在客户配送中心可接受服务时间内服务时,对物流公司予以惩罚,并将此惩罚成本作为对客户配送中心经济上的补偿,从而给客户配送中心一定的心理安慰并提高客户满意度;②在客户配送中心拒绝接收时间内提供服务时,客户配送中心拒绝接受货物.Manisri等[4]基于VRPSTW问题提出了多目标优化模型,其第一优化目标是在配送任务中使用的配送车辆数量最少,第二优化目标是全程配送时间最短,并使用混合算法对模型进行求解.一般的软时间窗口利用其灵活性,为广泛的应用程序定义各种交付成本函数.然而,这个问题是高度复杂的.Beheshti等[5]提出了一个数学模型和一个高效的混合列生成元启发式方法来解决这个复杂的问题.Tas等[6]进一步将VRPSTW模型中的整个时段划分为等待区、早到惩罚区、正常服务区、迟到惩罚区、不接受服务区5个区间,对早于早到惩罚区的等待区和晚于迟到惩罚区的不接受服务区都不接受配送.Tas等[7]又进一步提出了求解VRPSTW模型的禁忌搜索和邻域搜索算法,并用实际数据对算法进行验算和分析.李进等[8]研究了考虑碳排放和速度优化的带时间窗VRP,引入了基于速度的碳排放计算方法,以油耗、碳排放和旅行时间费用最小化为目标,将速度作为决策变量,建立了混合整数规划模型并提出了2阶段启发式算法:①第一阶段采用改进的禁忌搜索算法优化配送网络中的速度;②第二阶段设计了弧段速度优化算法用于优化路径弧段上的速度以寻求对最优解的进一步改进.李珍萍等[9]研究了多时间窗VRP,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型;根据智能水滴算法,设计了求解多时间窗VRP的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示智能水滴算法能够以较高的概率得到全局最优解.穆东等[10]为提高传统串行模拟退火(simulated annealing,SA)算法求解时间依赖型VRP的效率,提出了一种并行模拟退火算法,该算法首先使用前向插入启发式算法生成初始解,在主从式并行模拟退火算法框架下使用4种邻域搜索法对初始解进行优化.采用Figliozzi测试数据库对算法性能进行测试,得到不同时间依赖型行驶函数情形,当使用6个线程时并行模拟退火算法相对于传统串行模拟退火算法可以得到近似于5倍的加速比,且均能在较快时间内得到比Figliozzi算法更优的解.

李想等[11]指出,SA算法是一种通用性很强的优化算法,求解效果比其他启发式算法好,并具有对初始参数设置不敏感的优点.李江伟等[12]指出,模拟退火算法具有较强的全局搜索能力,且不要求目标函数为凸函数,能够以一定概率接受次最优解,使得算法在迭代过程中不会像Hopfield神经网络一样陷入局部最优.理论上只要初始的系统温度够高,温度下降够慢,迭代次数够多,算法收敛于全局最优解的概率就为100%.

任力[13]从最小化总成本和最大时间满意度出发,假设配送的时间服从不确定分布,利用不确定变量的期望、方差和熵提出了配送中心选址问题的新模型;基于Hamiki的结论给出了该模型的等价形式;通过数值例子验证了该模型的有效性.齐艳等[14]给出了顾客对产品或者服务的满意度与顾客等待时间的线性和非线性函数关系式.韩瑜睿等[15]对研究选址问题的基本覆盖模型进行了详细的分析和叙述,重点讨论集覆盖模型和最大覆盖模型;对模型中用到的重要函数(时间满意度函数)进行分析,并将其转换为通过距离衡量满意度的函数.Li等[16]研究了考虑客户满意度的积极配送网络的可靠性评估;建立了配送网络的运行优化模型,旨在利用需求响应来最大化配送网络的运营效益.

传统的物流配送问题大多从物流配送企业的角度去同等看待所有顾客配送时间的要求,而忽略了顾客对特殊时段不同的满意度水平.如何以顾客体验为导向,提升顾客满意度,成为现代物流配送企业提升自身竞争优势的一个关键问题.然而在模型方面,大多数VRP研究都是基于出行成本的最小化为目的,而对于VRPTW和VRPSTW的研究大多假设各需求点的配送时间必须在一定范围之内,早于或者晚于该范围的都不能配送,这无疑与实际不符.另外在计算方面,在传统的VRP问题中假设目标函数是最小化配送路径,所有需求点构成一个完全图,所有需求点满足基本的几何公理:2点之间线段最短,即配送路径最短.但如果综合考虑包括所有需求点的时间满意度和配送路程的配送效益,对于所有需求点组成的网络来说,其可行的最优配送效益并不一定满足2点之间的直接配送效益优于经过其余需求点的配送效益.鉴于以上分析,本工作将顾客满意度水平定义为顾客对物流企业为其提供配送服务时间的满意程度,物流企业通过尽量满足所有顾客对配送时间段的要求获得优于竞争对手的优势;通过建立配送服务时间与顾客满意度之间的函数关系式(称作顾客时间满意度函数),继而将顾客对时间窗的限制转化为顾客时间满意度,将各需求点经过且仅可经过一次的约束放松为车辆可多次经过需求点,建立顾客时间满意度配送模型(VRP with satisfaction,VRPWS),旨在配送过程中综合考虑顾客满意度和运输成本在内的配送效益.该模型克服了传统时间窗模型中对时间窗和需求点的限制缺陷,更有利于物流企业找到实际配送效益高的配送路径方案.

2 VRPWS模型的建立

VRPWS模型是在经典的VRP模型上,结合顾客时间满意度函数衍生而来的.VRPWS问题的优化目标是使综合考虑配送成本和顾客满意度的配送效益最大,即在满足约束条件的情况下,选择适当的路径使在运输成本较低的同时顾客满意度最大.

2.1 假设条件

2.1.1 顾客时间满意度函数

在实际配送过程中,根据顾客对产品配送时段的要求,将顾客分为2类:对配送时间无特殊要求的顾客(类型1)和要求在特定时间段完成配送活动的顾客(类型2).2种类型的顾客的时间满意度函数曲线如图1所示.

图1 顾客类型1与顾客类型2的时间满意度函数Fig.1 Time satisfaction functions of customer type 1 and customer type 2

对于顾客类型1,有耐心等待期[0,ai]和焦躁等待期[ai,bi].如果顾客在耐心等待期[0,ai]内收到产品,则时间满意度为100%;顾客在焦躁等待期[ai,bi]内收到产品,顾客时间满意度会随着收到时间与耐心等待时间之差增大而降低;而收到产品时间长于焦躁等待期,顾客的时间满意度为0.对于顾客类型2,有期望时间段[ui,vi]和可接受配送时间段[ti,wi].如果顾客在期望时间段[ui,vi]内收到产品,则满意度为100%;顾客在[ti,ui]以及[vi,wi]内收到产品,顾客时间满意度会随着收到时间与期望时间之差增大而降低;而在时间段[ti,wi]外收到产品,顾客时间满意度为0.每个顾客对服务时间感知度不同,并且每次订货需求只有一种产品类型.显然,从数学模型上来讲,类型1是类型2的特殊情况.

2.1.2 车辆配送服务

配送车辆从一个配送中心出发服务多位顾客,当完成该条线路上的顾客需求任务后仍返回配送中心,且已知车辆平均行驶速度,单位距离的运输成本固定,车辆禁止超载,车辆数目足够.每个顾客对服务时间感知度不同,并且每次订货需求只有一种产品类型,且各需求点的需求量不超过配送车辆的最大载运量.允许车辆经过而不服务需求点,但每个顾客只能被一辆车服务且仅服务一次,这与传统的VRP模型及其衍生模型有较大区别.

2.2 符号定义

基于以上假设,还需引入如下符号:

有向图G=(V,E)为配送网络,其中V={0,1,···,n}为节点集,节点0为配送中心;V/{0}表示顾客节点;

E={(i,j)|i,j邻接,j∈V,i̸=j}表示为配送路段集合,共有M 辆配送车,分别记为1,2,···,M;

Qmax为每辆配送车的最大载运量;

vij为节点i到节点j的平均车速;

dij为节点i到节点j的配送路段距离;

tij为车辆从顾客节点i到达顾客节点j所需要的时间;

Ne为接受产品类型e的顾客节点集合;

µ为顾客的时间满意度权重系数,反映了企业对顾客满意度的重视程度;

c为配送车的单位距离行驶时的运输成本(包括油费、车辆维修保养费)；

x¨ym和yim为决策变量(当x¨ym=1时,表示车辆m访问弧(i,j),否则x¨ym=0;当yim=1时,车辆m为顾客i配送产品,即为需求点i服务,否则yim=0).

2.3 VRPWS模型构建

本工作建立的VRPWS模型从顾客满意度视角出发,对VRP进行深入研究.在制定配送路径的过程中,考虑到顾客对配送时段的要求,本工作放宽了传统的VRP模型中关于车辆经过即被服务的限制,允许车辆多次经过需求点但不一定服务该需求点,具体模型如下:

约束条件：

式(1)为目标函数:满意度权重系数乘以顾客满意度减去运输成本;式(2)为配送车辆的载装能力约束;式(3)和(4)表示车辆m可以多次经过顾客节点i和顾客节点j,但不一定被服务,放宽了传统VRP模型中关于需求点经过即被服务的限制;式(5)保证了每个顾客i只能被服务一次;式(6)表示从配送中心0处出发的配送车有M辆;式(7)表示行驶路径的一致性;式(8)表示车辆服务顺序,先到顾客节点i再到顾客节点j.

2.4 求解VRPWS模型的改进模拟退火算法

模拟退火算法[13]是源于固体退火原理,相对于其他智能算法,模拟退火算法在求解传统VRP问题时具有收敛速度快且能迅速找到全局最优解的优点.一般算法容易局限于局部最优解而停滞不前,而模拟退火算法是以一种概率的方式进行搜索,增加了搜索过程的灵活性.考虑到VRPWS模型中目标函数的非凸性,基于模拟退火算法的以上优点,修正模拟退火算法求解传统VRP构造的邻域解中,默认同一辆车最多经过需求点一次的局限性,通过模拟退火算法给出各车辆的服务顾客顺序点集合,按一定概率选取其中相邻的2个服务点,寻找最佳配送效益的配送路径.模拟退火算法的内循环中通过路径间调整和路径内优化构造邻域解,采用双终止准则来提升模拟退火算法的记忆功能和优度.简记将模型目标函数记为配送效益Z.该问题在k步对应的一个解zk以及配送效益Zk分别与固体的一个降温时间Tk及其能量Ek等价.具体算法如下.

步骤1 设定初始温度T0以及终止温度Tz,令k=0,计算初始可行解zk.

步骤3使用2-opt法和插入法构造VRPWS模型的邻域解˜zk.

步骤3.5 ePkn+N对应的路径路径上各途径点的到达时间由如下公式可得t˜转步骤4.

步骤4根据式(1)计算˜zk下的配送效益值˜Zk,如果˜Zk>Zk,则令Zk=˜Zk,转步骤6;否则转步骤5.

步骤7 zk为可接受的最优解,Zk为相应的最优值.算法终止.

3 算例

本工作通过一个算例来比较VRPSTW模型、VRPTW模型和本工作提出的VRPWS模型,并对满意度权重系数进行敏感性分析.假定某快销品公司的一个配送中心要向其服务范围内的10个需求点进行货物配送,配送中心与需求点信息如表1所示.配送中心共有10辆规格相同的配送车辆,载重量均为15 t,在配送过程中平均行驶速度为100 km/h,每辆车油耗及维护成本为1元/km,配送车在每个需求点的服务时间长度为6 min.由于产品类型1是产品类型2的特殊情况,故本工作假设VRPSTW模型中客户要求配送的时间窗以及VRPWS模型中顾客的时间满意度函数如图2所示.

表1 配送中心与需求点信息Table 1 Distribution center and demand point informatim

图2 VRPSTW中的时间窗与VRPWS中的顾客满意度函数Fig.2 Time window in VRPSTW and customer’s satisfaction functions in VRPWS

VRPSTW时间窗与VRPWS顾客满意度函数中的参数ti,ui,vi,wi分别为2,4,6,8 h.当然在VRPSTW模型中,不接受配送超出最早配送时间和最晚配送时间范围的客户.

为研究满意度权重系数的变化对配送效益的影响,选取不同的满意度权重系数µ(其他条件均保持不变),求得的运输成本和顾客满意值(见图3).图3中,运输成本数值=运输成本×103,权重系数数值=权重系数×102.

可见,当权重系数取值从0到2 000变化时,运输成本、顾客满意值以及配送效益都随之发生了相应的改变(见图3).随着权重系数的增大,顾客满意度数值(顾客满意值=满意度权重系数×顾客满意度)和运输成本也在增大.当权重系数由0增大至500时,顾客满意度增加显著;但当权重系数超过500之后,运输成本和顾客满意值基本稳定.可见,权重系数反映了企业对顾客满意度的重视程度.上述结果表明,企业对顾客满意度的重视程度对物流配送成本和顾客满意度影响较大;但当重视程度达到一定程度后,就不能通过提高重视程度来提升顾客满意度了.因此,本工作将VRPWS模型中顾客时间满意度权重系数µ设置为稳定值500,并将VRPSTW模型中的惩罚系数也设置为500.

3.1 模拟退火算法参数选取

模拟退火算法中初始温度(T0)、降温系数(p)、终止温度(Tz)参数分别取值为

图3 权重系数变化对运输成本和顾客满意值的影响Fig.3 Influence of variation of weight coefficient on transportation cost and customer satisfaction

3.2 实验结果及分析

基于以上参数的设置和选取,利用Matlab 7.0.1进行求解,结果如表2所示.

表2 3类模型结果比较Table 2 Comparison results of the three models

通过比较3种模型可以发现,在VRPSTW模型中,当超出最早配送时间2和最晚配送时间8范围的配送时间,不接受配送会导致其配送效益要远远低于VRPWS模型和VRPWS模型的配送效益;VRPTW模型和VRPWS模型相比较,二者的最优配送路径都需要4辆车来进行,第3辆车和第4辆车的配送路径完全一样,由于VRPWS模型放宽了车辆经过即被配送的限制,需求点10有2辆车经过,但只有1辆车为其配送,尽管第2辆车多行驶了距离,但对于整个配送需求来说增强了顾客配送效益.与VRPSTW模型和经过即被服务的VRPTW模型相比较,VRPWS模型将配送效益从VRPSTW模型的248.9和VRPTW模型的651.30提高到672.12,分别提高了170.0%和3.2%.可见,VRPWS模型以顾客时间满意度的形式代替时间窗,通过放宽路径假设范围,使模型的配送效益更高,适用性更强.

4 结束语

随着电子商务的发展和时效性强的商业模式的出现,在物流配送过程中考虑顾客的时间满意度变得尤为重要.考虑在配送过程中顾客对于时间有较高的敏感性,本工作在车辆路径优化模型的基础上,结合顾客时间满意度,放宽对需求点和配送路径关系的限制,建立了VRPWS模型;通过算例说明本工作所提出的VRPWS模型是可行且有效的,并且在一定程度上为物流企业保障顾客满意度、降低运输成本提供方案.