考虑顾客替代选择的城市配送备选服务选项集多目标优化研究

高 敏,邱晗光,徐广业

(1.重庆工商大学 企业管理研究中心,重庆 400067;2.重庆工商大学 工商管理学院,重庆 400067;3.重庆工商大学 管理科学与工程学院,重庆 400067;4 南京邮电大学 管理学院,江苏 南京 210023)

0 引言

随着线上超市、外卖、生活服务等新零售业态蓬勃发展,提供差异化配送服务选项,成为城市末端配送重要的发展趋势之一[1-2]。送货上门(Attended Home Delivery,AHD)、自提柜(Reception Boxes,RB)等差异化交付方式及不同的时间窗(time slots)逐渐成为顾客可选的服务选项[3]。顾客对服务选项的差异化要求,与城市配送服务供应商相对有限的服务资源之间是矛盾的。在车辆、员工等资源有限约束下,供应商无法满足所有顾客的配送订单。如何满足顾客的差异化配送需求,成为供应商在订单接受决策、车辆调度与路径规划等运作管理中面临的新挑战。

一方面,对于顾客选择的服务选项组合,城市配送服务供应商需要决定是否接受顾客订单。无差别接受所有订单,将耗尽供应商有限的配送资源。配送订单是否可行,不仅与可用的车辆、配送人员等资源相关,在顾客序贯到达的动态环境下还与已经接受订单相关。即便是当前可行的交付方式及时间窗,由于服务高峰期内顾客并发到达,某些配送区域的服务能力也可能很快耗尽。因此,拒绝某些服务成本较高的配送需求,既能有效降低配送成本,还能确保配送方案可行性[4-5]。

另一方面,在顾客初次选择的服务选项超出服务能力时,提供有效的替代服务选项集合,是供应商平衡服务选项差异化选择与有限服务能力的有效措施,能降低配送订单的流失数量,提升顾客满意度。例如,英国ASDA超市为顾客提供自定义配送时间窗的送货上门服务;在评估顾客初次选择的配送时间窗后,若供应商发现现有配送资源难以满足或者服务成本较高时,往往会提供顾客替代选择的其他备选配送时间窗,尽量满足顾客差异化需求。

考虑顾客替代选择的情形下,如何优化设计备选服务选项集,是城市配送服务供应商重要的决策问题之一。供应商要考虑当前已接受订单集合和可用资源约束,从成本角度最小化配送距离,但这会减少为顾客提供的备选服务选项数量,增加顾客流失的概率;同时,为了提高顾客满意度,提供的备选服务选项集需要尽量覆盖顾客差异化需求,这又不可避免会增加车辆配送距离。因此,考虑顾客替代选择的城市配送备选服务选项集设计是多目标优化问题,需要在车辆配送距离与顾客备选服务选项数量之间平衡。

基于此,本文将使用嵌套Logit选择模型描述顾客对配送服务选项的初次及替代选择行为,构建考虑期望距离最小化和顾客替代选择累计转移率最大化的城市配送备选服务选项集多目标优化模型;基于Solomon插入算法及ε约束法、非支配排序遗传算法等多目标优化方法,设计相应的仿真过程,重点分析不同多目标优化方法的性能、时间窗偏差阈值和顾客替代选择累计转移率的影响。

1 国内外研究现状

顾客可选时间窗及末端交付方式的情境下,涉及车辆路径决策的相关问题具有需求动态性特征。只有在顾客到达并完成服务选项选择后,供应商才能获知顾客的位置及相关服务约束。供应商无法提前获取未来到达的配送需求信息。因此,备选服务选项集多目标优化需要以动态车辆路径问题(Dynamic Vehicle Routing Problems,DVRP)为基础进行讨论。此外,该问题还涉及时间窗管理、消费者选择行为等研究领域。

关于DVRP问题的研究较早是由PSARAFTIS[6]于1988年提出的,现有研究大多关注需求带来的动态性,优化目标包括期望等待时间和服务时间最小、车辆数量最小、服务路径最短、服务顾客最多等。DVRP问题的求解方法分为周期性优化和实时优化两类[7-8]。周期性优化是通过决策点(decision epochs)或者时间片(time slices)的设置,待动态不确定的需求转换为确定需求后,将动态问题转为静态问题进行求解。实时优化是由顾客到达或数据更新等事件驱动的[8]。实时优化可以为两种:以算法为主和以规则为主。以算法为主的实时优化在顾客到达或者数据更新后立刻通过局部优化或全局优化更新现有路径,以满足接受订单的配送需求[8]。以规则为主的研究侧重于定义动态出现的需求点如何形成配送路径的规则,包括定义配送区域内动态产生订单的遍历机制及启动路径优化算法的触发机制等。目前提出的规则包括:先到先服务策略(FCFS)、随机中心排队策略(SQM)、定量TSP策略(nTSP)、分区定量TSP策略(mod nTSP)、分格策略(PART)、就近策略(NN)和填充曲线策略(SFC)等[8-9]。相对来说,基于规则的实时优化可以在求解时间和质量之间实现平衡。时间窗的引入进一步增加了DVRP问题的求解难度,包括硬时间窗约束、软时间窗约束和开放式时间窗约束等情形[4]。带时间窗的动态车辆路径问题(Dynamic Vehicle Routing Problems withTimeWindows,DVRPTW),主要采取周期性优化和以算法为主的实时优化方法[4],以规则为主的实时优化方法还比较少[4],联合考虑末端交付方式和时间窗可选的规则设计也需要完善。

以往城市配送或路径规划研究中往往将时间窗设定为外界变量,时间窗管理研究(Time Slot Management,TSM)则将时间窗作为内生变量,关注时间窗分配、时间窗宽度影响、时间窗定价等问题。时间窗分配可以分为静态和动态两类。静态时间窗分配是指时间窗分配策略在整个订单接收周期保持不变,例如AGATZ等[10](2011)研究了静态情形下时间窗在地理位置维度上的分配问题,在研究中使用连续预估方法来估计路径成本,并假设每个区域的需求是预知的并且独立于时间窗。DALMEIJER等[11](2018)构建了时间窗分配的车辆路径问题模型用于解决不同顾客的时间窗分配决策,并设计分枝剪界算法进行求解。相对的,动态时间窗分配是指时间窗的分配策略会进行调整,消费者行为的刻画是重要问题之一,通常使用离散选择模型进行讨论。BENT等[12](2004)通过优化时间窗分配,实现利润最大化,但是没有考虑拒绝服务成本较高的订单;CAMPBELL等[13](2005)假设在订单接受期内配送需求随机到达,考虑拒绝某些服务成本较高的订单,并提出了DSR、DIFF、PATH、REG四种路径插入方法。CAMPBELL等[14](2006)考虑使用价格折扣,使消费者选择较宽的时间窗,进而降低配送路径的成本。EHMKE等[15](2014)在交通时间随机的情况下讨论了几种城市配送订单接受策略,在满足线路可行性的基础上接受尽可能多的配送订单。KOHLER等[16](2020)考虑提供长短两种时间窗,在服务水平约束下以接受订单数量最大化为目标,研究了面向动态到达顾客的可选时间窗集合优化设计。对于时间窗宽度的影响,PUNAKIVI等[17](2001)的研究表明:弱时间窗约束能够提高收益,完全无时间窗约束能够使总收益提升1/3左右;CAMPBELL等[13](2005)研究发现将一个小时的时间窗延长为两个小时可以提高总收益6%。对于时间窗定价,YANG等[3](2016)基于多项式离散选择和动态规划,建立了动态定价模型,优化提供给顾客的时间窗及相应的价格折扣;使用插入算法估算接受配送订单的服务成本,使用最近配送历史数据近似考虑未来订单的到达情况。延续上述研究,KOCH等[18](2020)使用强化学习的值函数近似(value function approximation)估算机会成本,STRAUSS等[19](2020)构建了离线线性规划模型用于计算接受订单的机会成本总体上看,时间窗管理的研究是面向送货上门交付,这与国外以独立房屋居住为主的实际情况吻合。然而在中国城市化进程中,城市居民以高层建筑集中居住为主,自提柜或自提点更符合中国国情。目前,对于多种末端交付模式下时间窗管理的研究还较少。

本文的研究还涉及离散选择模型(discrete choice methods),该模型自提出以来逐渐成为定量化分析个体选择行为的重要工具,并根据应用需求从基本的多项式离散模型发展出了嵌套Logit模型、一般极值模型、混合Logit模型等[20]。在城市配送领域,早期主要使用多项Logit模型描述顾客对配送时间窗的选择行为,如ASDEMIR等[21](2009)。后来,由于多项式离散模型无法考虑“与其他选择相关”,研究开始使用嵌套Logit模型描述配送服务选项之间的相关性,例如邱晗光等使用嵌套Logit模型描述顾客在选择末端交付方式和配送时间窗之间的差异[22]。其他选择模型还包括通用吸引力模型(Generalized Attraction Model,GAM)[23]、一般非参数化排序选择模型(general nonparametric rank-based choice model)[24]等。对于某些离散选项不可行带来的选择替代问题,在实体产品分销领域研究比较多,主要采用效用选择模型(the utility-based models)、位置选择模型(the locational choice model)和外部替代率模型(the exogenous substitution model)确定顾客面临离散选项不可行的替代概率[13]。对于配送服务类产品的选择替代问题目前研究还比较少。

综上所述,相对于已有研究,本文将使用基于效用的替代选择模型,整合讨论顾客对末端交付方式和时间窗的初次及替代选择行为;构建城市配送备选服务选项集多目标优化模型,为顾客提供更多备选服务选项的同时,最小化车辆配送距离。

2 问题描述

城市配送服务供应商在既定区域为顾客提供服务选项可选的配送服务,包括送货上门交付(记为AHD)、自提柜交付(记为RB)两种末端交付方式(记为D={AHD,RB})和配送时间窗集合(记为S),形成完整的服务选项集(记为D×S)。记顾客或配送点集合为Nc、顾客i的位置(xi,yj)、相互之间的路径距离dij是已知的(i,j∈Nc)。

随着时间序贯到达的顾客i,基于自身效用最大化,选择末端交付方式d(d∈D)和配送时间窗s(s∈S),确定接受服务的最早时间earlyi和最晚时间latei,产生配送需求。供应商根据已接受订单集合、现有车辆路径可达性以及新产生配送需求位置等特征进行配送可行性评估。若供应商接受顾客选择的服务选项(d,s),配送需求转换为配送订单;反之,供应商拒绝顾客选择的服务选项,同时向顾客i提供替代的服务选项集D′×S′⊂D×S。顾客进行替代选择,若无合适的服务选项,顾客撤回服务需求,供应商将丢失该配送服务需求。

在此过程中,如何根据顾客i首次选择的服务选项及概率、已接受订单的服务约束,优化设计替代的服务选项集合D′×S′,成为供应商需要决策的重要问题之一。为了提高顾客满意度,提供的备选服务选项集应该尽量覆盖顾客差异化需求,这又不可避免会更改单个车辆的路径甚至重构整个配送方案,增加车辆行驶距离。供应商需要在提供多样化备选服务选项与控制配送距离之间取得平衡。考虑替代选择的配送服务供应商与顾客交互决策过程如图1所示。

根据问题描述,进行如下假设:

假设1时段[0,T)内,配送需求rti是独立到达的,满足到达强度λ的齐次泊松过程,其中t∈[0,T)。

假设2根据泊松过程的性质,将时段[0,T)分成M个时段,每个时段[ti,ti+1](i=0,1,2,3,…,M,其中t0=0,tM=T)足够短,使[ti,ti+1]内至多只有一个配送需求到达,产生的配送需求总量为M个。

假设4单个AHD交付和RB交付的价格分别为RAHD和RRB。根据Amazon及英国ASDA超市等案例,送货上门交付比自提柜交付需要耗费更多的时间和运输成本,送货上门的服务价格通常会高于自提柜交付,据此设定RAHD≥RRB。

假设5在时间段[0,t)内,每个配送点i仅产生一次配送需求,i∈Nc;若某个地理位置多次产生配送需求,采用多个虚拟点进行描述。

3 考虑顾客替代选择的嵌套Logit模型

顾客在末端交付方式与配送时间窗之间的选择行为存在紧密联系[24-25]。在面对送货上门与自提柜交付时,不同末端交付方式带来的感知效用是影响顾客选择的重要因素。在面对不同配送时间窗时,实际需求时间是决定顾客选择的重要因素之一。根据朱惠琦等[25](2020)的研究,当效用变量改变时,配送服务发生在上午,顾客愿意首先变更配送时间窗;若配送发生在下午,顾客愿意首先变更配送方式。在送货上门交付下,顾客等待时间、服务水平、经济损失都比自提柜交付更敏感。多项式离散选择模型并不适合描述顾客对配送选项的选择行为[25-26]。为了区分顾客在选择末端交付方式和配送时间窗的相关性,使用嵌套Logit选择模型描述顾客选择城市配送服务选项的行为,如图2所示。

3.1 顾客初次配送服务选项集合的概率

在初次选择时,顾客选择第d种末端交付方式及配送时间窗s的概率pds:

(1)

3.2 顾客替代选择的转移率

在顾客初次选择后,供应商根据已接收订单集合、现有车辆路径可达性以及新配送需求位置等信息,决定是否接收新配送需求。若拒绝接收顾客选择的服务选项(d,s),则需要提供备选服务选项集D′×S′。在嵌套Logit选择模型中,顾客选择不同服务选项的概率随着服务选项集合的不同而变化。当服务选项(d,s)不可行时,顾客选择第d′种末端交付方式下第s′个配送时间窗(记为(d′,s′))的转移概率αds→d′s′如式(2)所示[27]:

(2)

4 备选服务选项集多目标优化模型

在顾客i配送需求被拒绝的情形下,服务供应商需要提供备选服务选项集合D′×S′供顾客i进行替代选择。设计的备选服务选项集多目标优化模型拓展于带时间窗车辆路径问题模型,以期望距离最小化和顾客替代选择累计转移率最大化为目标,考虑车辆路径可达性、接收订单集合服务约束等因素,在获取最短车辆路径的同时,优化构建备选服务选项集D′×S′。

4.1 决策变量

备选服务选项集多目标优化模型的决策变量包括备选服务选项集构建向量和车辆路径变量。

4.1.1 备选服务选项集构建向量

备选服务选项集构建向量ai=(ai11,...,aids,...,aiDS),是由0和1构成的二进制向量,用于表示供应商为顾客i提供备选服务选项集D′×S′,若aids=1表示第d种末端交付方式的第s个时间窗包含在顾客i的备选服务选项集中,即d×s⊂D′×S′,反之,若aids=0,则d×s⊄D′×S′。

结合备选服务选项集构建向量,顾客i选择替代服务选项(d,s)的概率如式(3)所示:

(3)

4.1.2 车辆路径变量

记顾客i配送需求到达时刻为t(t∈[0,T))、时间段[0,t)内已经接受的订单集合为At,At={(i,d,s):i∈Na,d∈{AHD,RB},s∈S}。车辆路径变量用于描述车辆服务已接受订单集合At及顾客i潜在替代服务选项的顺序。

网络行驶方案:

(4)

网络配送方案:

(5)

(6)

另外,使用完整有向图G=(N,AC)表示整个配送网络,模型使用的其他符号定义如下:

N表示点集;

N0表示配送中心,N0⊂N;

Nd表示自提柜集合,Nd⊂N;

Nc表示配送点或顾客集合,Nc⊂N,N0∪Nd∪Nc=N;

Na表示已接受订单的配送点集合,Na⊆Nc;

AC表示弧集,AC={(i,j):i,j∈N,i≠j};

dij表示弧(i,j)的行驶距离;

tij表示弧(i,j)的行驶时间;

tsi表示配送点i的服务时间,i∈Nc;

tai表示配送点i的到达时间或配送时间,i∈Nc;

K={1,2,3,...,k}表示车辆集合;

C表示车辆载重能力。

4.2 目标函数

使用函数vrptw(At)表示满足订单集合At服务约束的配送距离。在构建的模型中,优化目标包括期望距离最小和顾客替代选择累计转移率最大两个目标,分别如式(7)和式(8)所示:

优化目标I:期望距离最小化。

(7)

优化目标Ⅱ:顾客替代选择累计转移率最大化。

(8)

其中,αds→d′s′表示顾客在配送服务选项(d,s)不可选的情形下选择(d′,s′)进行替代的概率,{(i,d′,s′)}表示新产生的配送需求。

4.3 约束条件

为了便于表达约束条件,令Nr=N0∪Nd∪Na∪{i},包括配送中心、自提柜、已接受的顾客和顾客i,Nr⊆N。构建模型的约束条件如式(9)～式(21)所示。

(9)

(10)

约束(10)表示网络节点流量平衡。

(11)

约束(11)表示所有车辆的起点和终点都在配送中心,其中编号0的节点表示配送中心。

(12)

约束(12)表示送货上门交付的节点必须有车辆访问。

(13)

约束(13)表示自提柜服务的节点无需车辆访问。根据约束(9),约束(13)与约束(12)是等价的。

(14)

约束(14)表示自提柜节点必须有车辆访问。

≤C,∀k∈K

(15)

约束(15)表示车辆载重约束。其中,Na∪{i}|m表示自提柜m提供服务的配送点。

∀k∈K,∀(h,j)∈A,

(16)

约束(16)表示车辆到达时间约束,其中tah、taj分别代表到达配送点h和j的时刻;thj表示从配送点h到配送点j的时间。

(17)

约束(17)避免车辆出现子回路。Vk表示车辆k访问的任一节点集合。

earlyj≤taj≤lastj,∀j∈Na∪{i},

(18)

约束(18)是服务时间窗约束。

(19)

(20)

zmj∈{0,1},∀m∈Nd,j∈N,

(21)

约束(19)～约束(21)表示决策变量的取值范围。

5 仿真过程设计

仿真过程基于经典的Solomon I1插入算法进行设计[28],用于解决时间窗车辆路径规划、快速更新已有配送点的到达时间等问题。选择Solomon I1插入算法的原因在于该算法在其他时间窗车辆路径类问题的研究中体现了较高的求解效率和效果[15,29],尤其是在评估配送可行性时具有较高效率[13,30]。

算法大致可以分为3个核心模块:订单接受策略、基于SolomonI1插入算法的现有配送点到达时间更新和城市配送备选服务选项集多目标优化,如图3所示。其中,对于订单的评估,采用基于辐射半径的订单接收策略,包括可接受时间窗分配初始化、可接受时间窗动态调整、参照点动态选择及基于时间窗偏差阈值的配送需求评估等步骤[31]。

在图3中,实线箭头表示流程顺序,虚线箭头表示数据流。具体来说,更新后的服务选项分配结果在整个仿真过程中将长期存贮,并为配送需求接受决策提供依据。详细的仿真过程描述如下:

步骤1初始化时间窗宽度和配送中心坐标等仿真基础数据;

步骤2按照基于辐射半径的订单接收策略[31],以配送中心为原点分配配送区域的交付方式和时间窗;

步骤3判断是否停止接受本批次配送订单,若停止接受,则仿真结束;若继续接受新订单,则转入步骤4;

步骤4等待配送需求到达;

步骤5配送需求到达后,根据基于辐射半径的订单接收策略[31],对配送需求选择的配送方式和时间窗进行评估;若拒绝此配送需求,则转至步骤6;若接受此配送需求则转至步骤8;

步骤6根据顾客初次选择的服务选项,优化设计备选服务选项集;

步骤7顾客基于效用最大化目标,在备选服务选项集中挑选替代的服务选项组合;若顾客拒绝所有备选服务选项,则跳转至步骤3;若顾客从备选服务选项中完成挑选,则转入步骤8;

步骤8将接受的配送需求纳入已接受订单集合;使用插入算法,调整现有配送路径以满足接受的配送需求,同时更新其他订单的服务时间;

步骤9更新配送区域内的配送方式和时间窗分配,跳转至步骤3。

5.1 基于时间窗偏差阈值的配送需求评估

为了调整配送需求rti所选时间窗命中可接受时间窗集合SA的概率,设计基于时间窗偏差阈值的配送需求评估。其中,不同配送区域可接受时间窗集合SA采用基于辐射半径的方法产生[31]。

时间窗偏差值用于衡量配送需求选择的时间窗[earlyti,ateti]与可接受时间窗集合SA=[(Searlyi,Slatei):i∈|SA|]的重合程度,记为δ,其中|SA|表示t时刻配送需求rti所在区域预先分配的时间窗数量。时间窗偏差阈值是可接受配送需求的最大时间窗偏差值,记为δmax。在配送需求评估中,需要计算配送需求j的时间窗与集合SA中每个时间窗的偏差值δ,如式(22)所示:

δ=|latej-Slatei|/timerange,i∈|SA|。

(22)

其中timerange表示时间窗长度,||表示取绝对值。

如图4所示,时间窗长度timerage是120分钟,配送需求i的时间窗偏差值δi为0,配送需求j的时间窗偏差值δj为0.5,配送需求k的时间窗偏差值δk为1。配送需求评估的流程如图5所示。

5.2 城市配送备选服务选项集多目标优化

分别采用ε约束法(ε-constraint method)和带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅱ),求解构建的优化模型。

ε约束法是将某个目标函数作为约束函数,将多目标问题转换为单目标优化问题进行求解。通过调整目标函数约束值的大小,进而获取多目标问题的帕累托解集。在构建的模型中,将顾客替代选择累计转移率最大化目标转换为约束条件处理,如式(23)所示,其中ε代表顾客替代选择累计转移率最小约束值。

(23)

非支配排序遗传算法是为了寻找多目标帕累托解集,从基本遗传算法拓展而来,主要方法是通过定义的非支配排序,根据非劣解水平对种群进行分层,通过不停进化获取问题的帕累托解集[32]。

6 仿真实验

设定配送订单的接受周期T为960分钟,开始接受下一批次配送订单的时刻记为0时刻,960分钟后停止接受本批次订单并开始配送。基于假设1和假设2,在[0,960)内,配送需求到达的时间间隔服从指数分布。算法采用MatlabR2017a版本,使用Matlab脚本语言实现;仿真分析环境为IntelCore i7-6700 CPU、16G内存和Windows10专业版。仿真涉及的参数如表1所示。其中,参数θd是尺度因子,表明备选项相关性大小。例如送货上门交付尺度因子表示送货上门交付下不同时间窗之间可替代性的大小。由于顾客在送货上门交付下对等待时间更敏感,不同时间窗之间替代性更差,根据朱惠琦等(2020)[25],设置不同的送货上门交付尺度因子和自提柜交付尺度因子。

表1 相关参数

在仿真分析过程中,围绕构造顾客备选服务选项集这一研究目的,首先讨论不同优化方法对于顾客替代选择累计转移率最大化的优化结果以及服务选项更新的算法时间性能。然后分析时间窗偏差阈值的影响,最后重点分析顾客替代选择累计转移率最小约束值的影响。

6.1 仿真算例设计

仿真算例基于Solomon标准库设计,涵盖了RC类和R类总计两类4个算例,包括RC103,RC201,RC206和R207。RC类算例的配送点呈现分散和聚集结合的状态,与我国城市居民大多在多层建筑集中居住,以收件箱和自提点为主、送货上门交付为辅的混合末端交付模式吻合。RC201算例和RC103总共有100个配送点。算例从6个配送点较密集的区域选择6个配送点设立自提柜。其中,RC103算例中每条路径上允许的最大顾客量更少。RC206算例总共有50个配送点。算例从5个配送点较密集的区域选择5个配送点设立自提柜。此外,为了保证测试算例的多样性,还采用了配送点完全分散的R类R207算例。根据假设3和假设5,配送需求从尚未产生配送需求的配送点集合中随机产生。

6.2 仿真结果及多目标优化方法对比

采用ε约束法和NSGA-Ⅱ算法分别对RC103,RC201,RC206和R207四个算例进行仿真求解100次,获得各项指标的平均值及相应的单因素方差分析结果如表2～表5所示。

表2 RC201算例仿真结果

根据表2,在RC201算例中,ε约束法和NSGA-Ⅱ算法在RB收益、AHD收益及总收益不存在明显差异,但是在行驶距离、车辆数量、服务选项更新耗时方面存在显著差异。对于顾客替代选择增加的订单情况,ε约束法和NSGA-Ⅱ算法分别新增订单数量为2.400和2.49个,组间均方与组内均方的比例F是0.119 5,小于相应显著水平下的F临界值,可以认为两个算法对于优化顾客替代选择累计转移率最大化目标不存在明显差异。在行驶距离方面,ε约束法耗费的均值是1 536.168,高于NSGA-Ⅱ算法获取的1 444.809,方差分析也显示组间均方与组内均方的比例F是7.356 5,大于相应显著水平下的F临界值2.731 0(Fcrit),可以认为在获取相同收益的情形下,NSGA-Ⅱ算法能够寻找到配送距离更短的配送方案。因此,NSGA-Ⅱ算法获得配送方案较ε约束法在收益距离比方面更占优。

ε约束法需要的车辆数量均值是3.560,高于NSGA-Ⅱ算法(使用3.200),两者使用的车辆数量存在明显差异。ε约束法将通过外生变量ε将多目标问题转为单目标问题求解。ε约束法的实质是限定了顾客替代选择累计转移率的最小值。该方法为了满足顾客差异化需求会增加配送距离和车辆数量。而NSGA-Ⅱ算法可以采用帕累托集合的形式自适应平衡优化多目标。因此,ε约束法较NSGA-Ⅱ算法的配送距离更长,需要的车辆数量更多。

在服务选项更新耗时方面,NSGA-Ⅱ算法的平均耗时为12.216,远大于ε约束法,其方差分析的F值远大于临界值Fcrit,且p<0.05,ε约束法和NSGA-Ⅱ的服务选项更新耗时存在明显差异。这说明,NSGA-Ⅱ算法可以通过更多的计算耗时获取配送距离更小的方案。

根据表3,在RC206算例中,ε约束法和NSGA-Ⅱ算法除了在服务选项更新耗时方面存在显著差异外,其余各项指标方面不存在显著差异。而在RC201算例中,两种算法在行驶距离、车辆数量等指标存在显著差异,其原因在于:RC201算例的最大配送顾客数量是100个配送点,远大于50个配送点的RC206算例;配送点数量更多,解空间也会增大,对算法的性能要求也就更高;虽然两类算法在收益方面差异不显著,但是对于配送点数量更多的RC201算例,NSGA-Ⅱ在车辆数量、行驶距离等方面优于ε约束法。

表3 RC206算例仿真结果

根据表4,同样具有100个配送点的RC103算例则与RC201算例结论比较一致,ε约束法和NSGA-Ⅱ算法在RB收益、AHD收益及总收益方面不存在明显差异,但是在行驶距离、车辆数量、服务选项更新耗时方面存在显著差异。

表4 RC103算例仿真结果

根据表5,不同于其他3个算例中配送点呈现分散和聚集结合的状态,R207算例中所有的配送点呈现分散的状态。配送点的分布情况对两种算法的性能存在明显影响,无论是收益、配送距离还是配送时间,ε约束法和NSGA-Ⅱ算法均存在显著差异。相对来说,NSGA-Ⅱ算法耗时更多,能够获取更高的收益,但配送距离也会显著增加,收益距离比并不明显占优。

表5 R207算例仿真结果

总之,对于配送点分布呈现分散和聚集结合的情形,采用的ε约束法和NSGA-Ⅱ算法均能有效求解构建的城市配送备选服务选项集多目标优化模型;两种方法获取的各类收益不存在显著差异,但是在车辆行驶距离、车辆数量方面,NSGA-Ⅱ算法更适用于配送点数量更多的情形。对于配送点分布完全分散的情形,NSGA-Ⅱ算法耗时更多,能够获取更高的收益,但配送距离也会显著增加,收益距离比并不明显占优。

6.3 时间窗偏差阈值的影响

时间窗偏差阈值是指可接受配送需求的最大时间窗偏差值。时间窗偏差阈值越小,说明可接受的配送需求选择的时间窗与该区域预先分配的时间窗重合程度越高。根据NSGA-Ⅱ算法在求解配送点数量较多情形的优势,采用NSGA-Ⅱ算法分析时间窗偏差阈值的影响。

4个算例的仿真结果随着时间窗偏差阈值变化的情况分别如图6～图9所示。在图中,时间窗偏差阈值的影响采用双纵坐标形式展现,其中左纵坐标标识收益数值,右纵坐标标识距离,主要分析RB收益、AHD收益、总收益以及行驶距离随时间窗偏差阈值从0到1增长过程中的变化情况。

根据图6～图9所示,在RC201、RC203、RC103和R207算例中,随着时间窗偏差阈值逐渐增加,总收益呈现逐渐下降趋势,其中AHD收益受到时间窗偏差阈值变化的影响明显,RB收益则呈现震荡上升的趋势;由于AHD收益下降太多,总收益呈现下降趋势。其原因在于,随着时间窗偏差阈值逐渐增加,可接受需求的时间窗需要与预先分配的时间窗重合度提高,AHD服务需求被拒绝的概率增加,其收益呈现下降趋势;RB服务仅需要在时间窗最晚服务时间之前提供,对服务时间窗的约束更小,时间窗偏差阈值的变化对其影响不大,同时随着替代服务选择的提供,顾客选择RB服务的概率也会增加,因此RB收益呈现震荡增长趋势。随着AHD服务需求减少,行驶距离在配送点较多的RC201算例、RC103算例和R207算例中呈现震荡下降趋势;由于RC206算例的配送点较小,行驶距离的变化趋势不明显。

6.4 顾客替代选择累计转移率最小约束值的影响

顾客替代选择累计转移率最小约束值是ε约束法中将顾客替代选择累计转移率最大化目标转换为约束条件所设置的可接受最小目标值。最小约束值越大,意味着为拒绝顾客提供的备选服务选项数量越多。顾客替代选择累计转移率最小约束值的影响采用ε约束法分析。

4个算例的仿真结果随着最小约束值变化的情况分别如图10～图13所示。在图中,顾客替代选择累计转移率最小约束值的影响采用双纵坐标形式展现,其中左纵坐标标识收益,右纵坐标标识距离,主要分析RB收益、AHD收益、总收益以及行驶距离随最小约束值从0到100%增长过程中的变化情况。

根据图10～图13所示,在RC201、RC203、RC103和R207算例中,AHD收益与总收益的变化趋势比较一致,RB收益对于总收益的变化趋势影响较小。这意味着为顾客提供的备选服务选项数量能够影响AHD服务订单数量,而对于RB订单数量影响较少。AHD收益、RB收益及总收益随着最小约束值的变化趋势不明显,顾客替代选择累计转移率最小约束值对收益的影响不存在线性关系。由于行驶距离与AHD服务数量密切相关,相应的行驶距离与顾客替代选择累计转移率最小约束值也不存在明确趋势关系。

在RC201、RC203、RC103和R207算例中,时间窗偏差阈值及顾客替代选择累计转移率最小约束值对总收益的联合影响如图14～图17所示,其中,总收益最大时两参数的取值使用游标标明。

仿真结果显示,收益最大值均不在时间窗偏差阈值及最小约束值的边界处获取;收益值在两者的定义域内呈现离散且局部极大值遍布的情形;总体上看,在时间窗偏差阈值较小、顾客替代选择累计转移率最小约束值较大的区域,往往能获取更高的总收益。

7 结束语

在城市配送从通用无差异服务向个性定制化转型升级的情境下,提高配送资源使用效率是城市配送运营商重要的核心竞争力,是平衡服务成本和消费者满意度、实现定制化城市配送可持续发展的重要基础。根据顾客对配送选项的偏好,为服务成本较高的服务需求提供成本可行的备选服务选项集合,实现配送需求与配送资源之间的匹配,成为城市配送运营商提高配送资源使用效率的重要措施之一。基于此,本文讨论了顾客对服务选项的替代选择行为,构建了考虑期望距离最小和顾客替代选择累计转移率最大的城市配送备选服务选项集多目标优化模型。仿真结果显示:对于配送点分布呈现分散和聚集结合的情形,ε约束法和NSGA-Ⅱ算法对优化顾客替代选择累计转移率最大化目标不存在明显差异;NSGA-Ⅱ算法在配送点数量更多的情形可以有效降低车辆行驶距离、车辆数量等成本因素;对于配送点分布完全分散的情形,NSGA-Ⅱ算法耗时更多,能够获取更高的收益,但配送距离也会显著增加,收益距离比并不明显占优;允许顾客选择的时间窗与分配的时间窗之间差异越大,损失的收益也就越大,尤其是对AHD收益的影响更明显,可接受的时间窗偏差阈值是决策的重要指标;若供应商缩小时间窗偏差阈值,应适当增加顾客替代选择累计转移率最小约束值,可以改善总收益。本文设计的模型和求解算法为服务水平约束下提供差异化城市配送服务提供了较好的解决思路和工具,在此基础上考虑即时配送、需求管理等差异化运营场景将是下一步的研究方向。