高 敏,邱晗光,徐廣業(yè)

(1.重慶工商大學(xué) 企業(yè)管理研究中心,重慶 400067;2.重慶工商大學(xué) 工商管理學(xué)院,重慶 400067;3.重慶工商大學(xué) 管理科學(xué)與工程學(xué)院,重慶 400067;4 南京郵電大學(xué) 管理學(xué)院,江蘇 南京 210023)

0 引言

隨著線上超市、外賣、生活服務(wù)等新零售業(yè)態(tài)蓬勃發(fā)展,提供差異化配送服務(wù)選項(xiàng),成為城市末端配送重要的發(fā)展趨勢(shì)之一[1-2]。送貨上門(Attended Home Delivery,AHD)、自提柜(Reception Boxes,RB)等差異化交付方式及不同的時(shí)間窗(time slots)逐漸成為顧客可選的服務(wù)選項(xiàng)[3]。顧客對(duì)服務(wù)選項(xiàng)的差異化要求,與城市配送服務(wù)供應(yīng)商相對(duì)有限的服務(wù)資源之間是矛盾的。在車輛、員工等資源有限約束下,供應(yīng)商無(wú)法滿足所有顧客的配送訂單。如何滿足顧客的差異化配送需求,成為供應(yīng)商在訂單接受決策、車輛調(diào)度與路徑規(guī)劃等運(yùn)作管理中面臨的新挑戰(zhàn)。

一方面,對(duì)于顧客選擇的服務(wù)選項(xiàng)組合,城市配送服務(wù)供應(yīng)商需要決定是否接受顧客訂單。無(wú)差別接受所有訂單,將耗盡供應(yīng)商有限的配送資源。配送訂單是否可行,不僅與可用的車輛、配送人員等資源相關(guān),在顧客序貫到達(dá)的動(dòng)態(tài)環(huán)境下還與已經(jīng)接受訂單相關(guān)。即便是當(dāng)前可行的交付方式及時(shí)間窗,由于服務(wù)高峰期內(nèi)顧客并發(fā)到達(dá),某些配送區(qū)域的服務(wù)能力也可能很快耗盡。因此,拒絕某些服務(wù)成本較高的配送需求,既能有效降低配送成本,還能確保配送方案可行性[4-5]。

另一方面,在顧客初次選擇的服務(wù)選項(xiàng)超出服務(wù)能力時(shí),提供有效的替代服務(wù)選項(xiàng)集合,是供應(yīng)商平衡服務(wù)選項(xiàng)差異化選擇與有限服務(wù)能力的有效措施,能降低配送訂單的流失數(shù)量,提升顧客滿意度。例如,英國(guó)ASDA超市為顧客提供自定義配送時(shí)間窗的送貨上門服務(wù);在評(píng)估顧客初次選擇的配送時(shí)間窗后,若供應(yīng)商發(fā)現(xiàn)現(xiàn)有配送資源難以滿足或者服務(wù)成本較高時(shí),往往會(huì)提供顧客替代選擇的其他備選配送時(shí)間窗,盡量滿足顧客差異化需求。

考慮顧客替代選擇的情形下,如何優(yōu)化設(shè)計(jì)備選服務(wù)選項(xiàng)集,是城市配送服務(wù)供應(yīng)商重要的決策問(wèn)題之一。供應(yīng)商要考慮當(dāng)前已接受訂單集合和可用資源約束,從成本角度最小化配送距離,但這會(huì)減少為顧客提供的備選服務(wù)選項(xiàng)數(shù)量,增加顧客流失的概率;同時(shí),為了提高顧客滿意度,提供的備選服務(wù)選項(xiàng)集需要盡量覆蓋顧客差異化需求,這又不可避免會(huì)增加車輛配送距離。因此,考慮顧客替代選擇的城市配送備選服務(wù)選項(xiàng)集設(shè)計(jì)是多目標(biāo)優(yōu)化問(wèn)題,需要在車輛配送距離與顧客備選服務(wù)選項(xiàng)數(shù)量之間平衡。

基于此,本文將使用嵌套Logit選擇模型描述顧客對(duì)配送服務(wù)選項(xiàng)的初次及替代選擇行為,構(gòu)建考慮期望距離最小化和顧客替代選擇累計(jì)轉(zhuǎn)移率最大化的城市配送備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型;基于Solomon插入算法及ε約束法、非支配排序遺傳算法等多目標(biāo)優(yōu)化方法,設(shè)計(jì)相應(yīng)的仿真過(guò)程,重點(diǎn)分析不同多目標(biāo)優(yōu)化方法的性能、時(shí)間窗偏差閾值和顧客替代選擇累計(jì)轉(zhuǎn)移率的影響。

1 國(guó)內(nèi)外研究現(xiàn)狀

顧客可選時(shí)間窗及末端交付方式的情境下,涉及車輛路徑?jīng)Q策的相關(guān)問(wèn)題具有需求動(dòng)態(tài)性特征。只有在顧客到達(dá)并完成服務(wù)選項(xiàng)選擇后,供應(yīng)商才能獲知顧客的位置及相關(guān)服務(wù)約束。供應(yīng)商無(wú)法提前獲取未來(lái)到達(dá)的配送需求信息。因此,備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化需要以動(dòng)態(tài)車輛路徑問(wèn)題(Dynamic Vehicle Routing Problems,DVRP)為基礎(chǔ)進(jìn)行討論。此外,該問(wèn)題還涉及時(shí)間窗管理、消費(fèi)者選擇行為等研究領(lǐng)域。

關(guān)于DVRP問(wèn)題的研究較早是由PSARAFTIS[6]于1988年提出的,現(xiàn)有研究大多關(guān)注需求帶來(lái)的動(dòng)態(tài)性,優(yōu)化目標(biāo)包括期望等待時(shí)間和服務(wù)時(shí)間最小、車輛數(shù)量最小、服務(wù)路徑最短、服務(wù)顧客最多等。DVRP問(wèn)題的求解方法分為周期性優(yōu)化和實(shí)時(shí)優(yōu)化兩類[7-8]。周期性優(yōu)化是通過(guò)決策點(diǎn)(decision epochs)或者時(shí)間片(time slices)的設(shè)置,待動(dòng)態(tài)不確定的需求轉(zhuǎn)換為確定需求后,將動(dòng)態(tài)問(wèn)題轉(zhuǎn)為靜態(tài)問(wèn)題進(jìn)行求解。實(shí)時(shí)優(yōu)化是由顧客到達(dá)或數(shù)據(jù)更新等事件驅(qū)動(dòng)的[8]。實(shí)時(shí)優(yōu)化可以為兩種:以算法為主和以規(guī)則為主。以算法為主的實(shí)時(shí)優(yōu)化在顧客到達(dá)或者數(shù)據(jù)更新后立刻通過(guò)局部?jī)?yōu)化或全局優(yōu)化更新現(xiàn)有路徑,以滿足接受訂單的配送需求[8]。以規(guī)則為主的研究側(cè)重于定義動(dòng)態(tài)出現(xiàn)的需求點(diǎn)如何形成配送路徑的規(guī)則,包括定義配送區(qū)域內(nèi)動(dòng)態(tài)產(chǎn)生訂單的遍歷機(jī)制及啟動(dòng)路徑優(yōu)化算法的觸發(fā)機(jī)制等。目前提出的規(guī)則包括:先到先服務(wù)策略(FCFS)、隨機(jī)中心排隊(duì)策略(SQM)、定量TSP策略(nTSP)、分區(qū)定量TSP策略(mod nTSP)、分格策略(PART)、就近策略(NN)和填充曲線策略(SFC)等[8-9]。相對(duì)來(lái)說(shuō),基于規(guī)則的實(shí)時(shí)優(yōu)化可以在求解時(shí)間和質(zhì)量之間實(shí)現(xiàn)平衡。時(shí)間窗的引入進(jìn)一步增加了DVRP問(wèn)題的求解難度,包括硬時(shí)間窗約束、軟時(shí)間窗約束和開(kāi)放式時(shí)間窗約束等情形[4]。帶時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題(Dynamic Vehicle Routing Problems withTimeWindows,DVRPTW),主要采取周期性優(yōu)化和以算法為主的實(shí)時(shí)優(yōu)化方法[4],以規(guī)則為主的實(shí)時(shí)優(yōu)化方法還比較少[4],聯(lián)合考慮末端交付方式和時(shí)間窗可選的規(guī)則設(shè)計(jì)也需要完善。

以往城市配送或路徑規(guī)劃研究中往往將時(shí)間窗設(shè)定為外界變量,時(shí)間窗管理研究(Time Slot Management,TSM)則將時(shí)間窗作為內(nèi)生變量,關(guān)注時(shí)間窗分配、時(shí)間窗寬度影響、時(shí)間窗定價(jià)等問(wèn)題。時(shí)間窗分配可以分為靜態(tài)和動(dòng)態(tài)兩類。靜態(tài)時(shí)間窗分配是指時(shí)間窗分配策略在整個(gè)訂單接收周期保持不變,例如AGATZ等[10](2011)研究了靜態(tài)情形下時(shí)間窗在地理位置維度上的分配問(wèn)題,在研究中使用連續(xù)預(yù)估方法來(lái)估計(jì)路徑成本,并假設(shè)每個(gè)區(qū)域的需求是預(yù)知的并且獨(dú)立于時(shí)間窗。DALMEIJER等[11](2018)構(gòu)建了時(shí)間窗分配的車輛路徑問(wèn)題模型用于解決不同顧客的時(shí)間窗分配決策,并設(shè)計(jì)分枝剪界算法進(jìn)行求解。相對(duì)的,動(dòng)態(tài)時(shí)間窗分配是指時(shí)間窗的分配策略會(huì)進(jìn)行調(diào)整,消費(fèi)者行為的刻畫是重要問(wèn)題之一,通常使用離散選擇模型進(jìn)行討論。BENT等[12](2004)通過(guò)優(yōu)化時(shí)間窗分配,實(shí)現(xiàn)利潤(rùn)最大化,但是沒(méi)有考慮拒絕服務(wù)成本較高的訂單;CAMPBELL等[13](2005)假設(shè)在訂單接受期內(nèi)配送需求隨機(jī)到達(dá),考慮拒絕某些服務(wù)成本較高的訂單,并提出了DSR、DIFF、PATH、REG四種路徑插入方法。CAMPBELL等[14](2006)考慮使用價(jià)格折扣,使消費(fèi)者選擇較寬的時(shí)間窗,進(jìn)而降低配送路徑的成本。EHMKE等[15](2014)在交通時(shí)間隨機(jī)的情況下討論了幾種城市配送訂單接受策略,在滿足線路可行性的基礎(chǔ)上接受盡可能多的配送訂單。KOHLER等[16](2020)考慮提供長(zhǎng)短兩種時(shí)間窗,在服務(wù)水平約束下以接受訂單數(shù)量最大化為目標(biāo),研究了面向動(dòng)態(tài)到達(dá)顧客的可選時(shí)間窗集合優(yōu)化設(shè)計(jì)。對(duì)于時(shí)間窗寬度的影響,PUNAKIVI等[17](2001)的研究表明:弱時(shí)間窗約束能夠提高收益,完全無(wú)時(shí)間窗約束能夠使總收益提升1/3左右;CAMPBELL等[13](2005)研究發(fā)現(xiàn)將一個(gè)小時(shí)的時(shí)間窗延長(zhǎng)為兩個(gè)小時(shí)可以提高總收益6%。對(duì)于時(shí)間窗定價(jià),YANG等[3](2016)基于多項(xiàng)式離散選擇和動(dòng)態(tài)規(guī)劃,建立了動(dòng)態(tài)定價(jià)模型,優(yōu)化提供給顧客的時(shí)間窗及相應(yīng)的價(jià)格折扣;使用插入算法估算接受配送訂單的服務(wù)成本,使用最近配送歷史數(shù)據(jù)近似考慮未來(lái)訂單的到達(dá)情況。延續(xù)上述研究,KOCH等[18](2020)使用強(qiáng)化學(xué)習(xí)的值函數(shù)近似(value function approximation)估算機(jī)會(huì)成本,STRAUSS等[19](2020)構(gòu)建了離線線性規(guī)劃模型用于計(jì)算接受訂單的機(jī)會(huì)成本總體上看,時(shí)間窗管理的研究是面向送貨上門交付,這與國(guó)外以獨(dú)立房屋居住為主的實(shí)際情況吻合。然而在中國(guó)城市化進(jìn)程中,城市居民以高層建筑集中居住為主,自提柜或自提點(diǎn)更符合中國(guó)國(guó)情。目前,對(duì)于多種末端交付模式下時(shí)間窗管理的研究還較少。

本文的研究還涉及離散選擇模型(discrete choice methods),該模型自提出以來(lái)逐漸成為定量化分析個(gè)體選擇行為的重要工具,并根據(jù)應(yīng)用需求從基本的多項(xiàng)式離散模型發(fā)展出了嵌套Logit模型、一般極值模型、混合Logit模型等[20]。在城市配送領(lǐng)域,早期主要使用多項(xiàng)Logit模型描述顧客對(duì)配送時(shí)間窗的選擇行為,如ASDEMIR等[21](2009)。后來(lái),由于多項(xiàng)式離散模型無(wú)法考慮“與其他選擇相關(guān)”,研究開(kāi)始使用嵌套Logit模型描述配送服務(wù)選項(xiàng)之間的相關(guān)性,例如邱晗光等使用嵌套Logit模型描述顧客在選擇末端交付方式和配送時(shí)間窗之間的差異[22]。其他選擇模型還包括通用吸引力模型(Generalized Attraction Model,GAM)[23]、一般非參數(shù)化排序選擇模型(general nonparametric rank-based choice model)[24]等。對(duì)于某些離散選項(xiàng)不可行帶來(lái)的選擇替代問(wèn)題,在實(shí)體產(chǎn)品分銷領(lǐng)域研究比較多,主要采用效用選擇模型(the utility-based models)、位置選擇模型(the locational choice model)和外部替代率模型(the exogenous substitution model)確定顧客面臨離散選項(xiàng)不可行的替代概率[13]。對(duì)于配送服務(wù)類產(chǎn)品的選擇替代問(wèn)題目前研究還比較少。

綜上所述,相對(duì)于已有研究,本文將使用基于效用的替代選擇模型,整合討論顧客對(duì)末端交付方式和時(shí)間窗的初次及替代選擇行為;構(gòu)建城市配送備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型,為顧客提供更多備選服務(wù)選項(xiàng)的同時(shí),最小化車輛配送距離。

2 問(wèn)題描述

城市配送服務(wù)供應(yīng)商在既定區(qū)域?yàn)轭櫩吞峁┓?wù)選項(xiàng)可選的配送服務(wù),包括送貨上門交付(記為AHD)、自提柜交付(記為RB)兩種末端交付方式(記為D={AHD,RB})和配送時(shí)間窗集合(記為S),形成完整的服務(wù)選項(xiàng)集(記為D×S)。記顧客或配送點(diǎn)集合為Nc、顧客i的位置(xi,yj)、相互之間的路徑距離dij是已知的(i,j∈Nc)。

隨著時(shí)間序貫到達(dá)的顧客i,基于自身效用最大化,選擇末端交付方式d(d∈D)和配送時(shí)間窗s(s∈S),確定接受服務(wù)的最早時(shí)間earlyi和最晚時(shí)間latei,產(chǎn)生配送需求。供應(yīng)商根據(jù)已接受訂單集合、現(xiàn)有車輛路徑可達(dá)性以及新產(chǎn)生配送需求位置等特征進(jìn)行配送可行性評(píng)估。若供應(yīng)商接受顧客選擇的服務(wù)選項(xiàng)(d,s),配送需求轉(zhuǎn)換為配送訂單;反之,供應(yīng)商拒絕顧客選擇的服務(wù)選項(xiàng),同時(shí)向顧客i提供替代的服務(wù)選項(xiàng)集D′×S′?D×S。顧客進(jìn)行替代選擇,若無(wú)合適的服務(wù)選項(xiàng),顧客撤回服務(wù)需求,供應(yīng)商將丟失該配送服務(wù)需求。

在此過(guò)程中,如何根據(jù)顧客i首次選擇的服務(wù)選項(xiàng)及概率、已接受訂單的服務(wù)約束,優(yōu)化設(shè)計(jì)替代的服務(wù)選項(xiàng)集合D′×S′,成為供應(yīng)商需要決策的重要問(wèn)題之一。為了提高顧客滿意度,提供的備選服務(wù)選項(xiàng)集應(yīng)該盡量覆蓋顧客差異化需求,這又不可避免會(huì)更改單個(gè)車輛的路徑甚至重構(gòu)整個(gè)配送方案,增加車輛行駛距離。供應(yīng)商需要在提供多樣化備選服務(wù)選項(xiàng)與控制配送距離之間取得平衡?？紤]替代選擇的配送服務(wù)供應(yīng)商與顧客交互決策過(guò)程如圖1所示。

根據(jù)問(wèn)題描述,進(jìn)行如下假設(shè):

假設(shè)1時(shí)段[0,T)內(nèi),配送需求rti是獨(dú)立到達(dá)的,滿足到達(dá)強(qiáng)度λ的齊次泊松過(guò)程,其中t∈[0,T)。

假設(shè)2根據(jù)泊松過(guò)程的性質(zhì),將時(shí)段[0,T)分成M個(gè)時(shí)段,每個(gè)時(shí)段[ti,ti+1](i=0,1,2,3,…,M,其中t0=0,tM=T)足夠短,使[ti,ti+1]內(nèi)至多只有一個(gè)配送需求到達(dá),產(chǎn)生的配送需求總量為M個(gè)。

假設(shè)4單個(gè)AHD交付和RB交付的價(jià)格分別為RAHD和RRB。根據(jù)Amazon及英國(guó)ASDA超市等案例,送貨上門交付比自提柜交付需要耗費(fèi)更多的時(shí)間和運(yùn)輸成本,送貨上門的服務(wù)價(jià)格通常會(huì)高于自提柜交付,據(jù)此設(shè)定RAHD≥RRB。

假設(shè)5在時(shí)間段[0,t)內(nèi),每個(gè)配送點(diǎn)i僅產(chǎn)生一次配送需求,i∈Nc;若某個(gè)地理位置多次產(chǎn)生配送需求,采用多個(gè)虛擬點(diǎn)進(jìn)行描述。

3 考慮顧客替代選擇的嵌套Logit模型

顧客在末端交付方式與配送時(shí)間窗之間的選擇行為存在緊密聯(lián)系[24-25]。在面對(duì)送貨上門與自提柜交付時(shí),不同末端交付方式帶來(lái)的感知效用是影響顧客選擇的重要因素。在面對(duì)不同配送時(shí)間窗時(shí),實(shí)際需求時(shí)間是決定顧客選擇的重要因素之一。根據(jù)朱惠琦等[25](2020)的研究,當(dāng)效用變量改變時(shí),配送服務(wù)發(fā)生在上午,顧客愿意首先變更配送時(shí)間窗;若配送發(fā)生在下午,顧客愿意首先變更配送方式。在送貨上門交付下,顧客等待時(shí)間、服務(wù)水平、經(jīng)濟(jì)損失都比自提柜交付更敏感。多項(xiàng)式離散選擇模型并不適合描述顧客對(duì)配送選項(xiàng)的選擇行為[25-26]。為了區(qū)分顧客在選擇末端交付方式和配送時(shí)間窗的相關(guān)性,使用嵌套Logit選擇模型描述顧客選擇城市配送服務(wù)選項(xiàng)的行為,如圖2所示。

3.1 顧客初次配送服務(wù)選項(xiàng)集合的概率

在初次選擇時(shí),顧客選擇第d種末端交付方式及配送時(shí)間窗s的概率pds:

(1)

3.2 顧客替代選擇的轉(zhuǎn)移率

在顧客初次選擇后,供應(yīng)商根據(jù)已接收訂單集合、現(xiàn)有車輛路徑可達(dá)性以及新配送需求位置等信息,決定是否接收新配送需求。若拒絕接收顧客選擇的服務(wù)選項(xiàng)(d,s),則需要提供備選服務(wù)選項(xiàng)集D′×S′。在嵌套Logit選擇模型中,顧客選擇不同服務(wù)選項(xiàng)的概率隨著服務(wù)選項(xiàng)集合的不同而變化。當(dāng)服務(wù)選項(xiàng)(d,s)不可行時(shí),顧客選擇第d′種末端交付方式下第s′個(gè)配送時(shí)間窗(記為(d′,s′))的轉(zhuǎn)移概率αds→d′s′如式(2)所示[27]:

(2)

4 備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型

在顧客i配送需求被拒絕的情形下,服務(wù)供應(yīng)商需要提供備選服務(wù)選項(xiàng)集合D′×S′供顧客i進(jìn)行替代選擇。設(shè)計(jì)的備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型拓展于帶時(shí)間窗車輛路徑問(wèn)題模型,以期望距離最小化和顧客替代選擇累計(jì)轉(zhuǎn)移率最大化為目標(biāo),考慮車輛路徑可達(dá)性、接收訂單集合服務(wù)約束等因素,在獲取最短車輛路徑的同時(shí),優(yōu)化構(gòu)建備選服務(wù)選項(xiàng)集D′×S′。

4.1 決策變量

備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型的決策變量包括備選服務(wù)選項(xiàng)集構(gòu)建向量和車輛路徑變量。

4.1.1 備選服務(wù)選項(xiàng)集構(gòu)建向量

備選服務(wù)選項(xiàng)集構(gòu)建向量ai=(ai11,...,aids,...,aiDS),是由0和1構(gòu)成的二進(jìn)制向量,用于表示供應(yīng)商為顧客i提供備選服務(wù)選項(xiàng)集D′×S′,若aids=1表示第d種末端交付方式的第s個(gè)時(shí)間窗包含在顧客i的備選服務(wù)選項(xiàng)集中,即d×s?D′×S′,反之,若aids=0,則d×s?D′×S′。

結(jié)合備選服務(wù)選項(xiàng)集構(gòu)建向量,顧客i選擇替代服務(wù)選項(xiàng)(d,s)的概率如式(3)所示:

(3)

4.1.2 車輛路徑變量

記顧客i配送需求到達(dá)時(shí)刻為t(t∈[0,T))、時(shí)間段[0,t)內(nèi)已經(jīng)接受的訂單集合為At,At={(i,d,s):i∈Na,d∈{AHD,RB},s∈S}。車輛路徑變量用于描述車輛服務(wù)已接受訂單集合At及顧客i潛在替代服務(wù)選項(xiàng)的順序。

網(wǎng)絡(luò)行駛方案:

(4)

網(wǎng)絡(luò)配送方案:

(5)

(6)

另外,使用完整有向圖G=(N,AC)表示整個(gè)配送網(wǎng)絡(luò),模型使用的其他符號(hào)定義如下:

N表示點(diǎn)集;

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

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

Nc表示配送點(diǎn)或顧客集合,Nc?N,N0∪Nd∪Nc=N;

Na表示已接受訂單的配送點(diǎn)集合,Na?Nc;

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

dij表示弧(i,j)的行駛距離;

tij表示弧(i,j)的行駛時(shí)間;

tsi表示配送點(diǎn)i的服務(wù)時(shí)間,i∈Nc;

tai表示配送點(diǎn)i的到達(dá)時(shí)間或配送時(shí)間,i∈Nc;

K={1,2,3,...,k}表示車輛集合;

C表示車輛載重能力。

4.2 目標(biāo)函數(shù)

使用函數(shù)vrptw(At)表示滿足訂單集合At服務(wù)約束的配送距離。在構(gòu)建的模型中,優(yōu)化目標(biāo)包括期望距離最小和顧客替代選擇累計(jì)轉(zhuǎn)移率最大兩個(gè)目標(biāo),分別如式(7)和式(8)所示:

優(yōu)化目標(biāo)I:期望距離最小化。

(7)

優(yōu)化目標(biāo)Ⅱ:顧客替代選擇累計(jì)轉(zhuǎn)移率最大化。

(8)

其中,αds→d′s′表示顧客在配送服務(wù)選項(xiàng)(d,s)不可選的情形下選擇(d′,s′)進(jìn)行替代的概率,{(i,d′,s′)}表示新產(chǎn)生的配送需求。

4.3 約束條件

為了便于表達(dá)約束條件,令Nr=N0∪Nd∪Na∪{i},包括配送中心、自提柜、已接受的顧客和顧客i,Nr?N。構(gòu)建模型的約束條件如式(9)～式(21)所示。

(9)

(10)

約束(10)表示網(wǎng)絡(luò)節(jié)點(diǎn)流量平衡。

(11)

約束(11)表示所有車輛的起點(diǎn)和終點(diǎn)都在配送中心,其中編號(hào)0的節(jié)點(diǎn)表示配送中心。

(12)

約束(12)表示送貨上門交付的節(jié)點(diǎn)必須有車輛訪問(wèn)。

(13)

約束(13)表示自提柜服務(wù)的節(jié)點(diǎn)無(wú)需車輛訪問(wèn)。根據(jù)約束(9),約束(13)與約束(12)是等價(jià)的。

(14)

約束(14)表示自提柜節(jié)點(diǎn)必須有車輛訪問(wèn)。

≤C,?k∈K

(15)

約束(15)表示車輛載重約束。其中,Na∪{i}|m表示自提柜m提供服務(wù)的配送點(diǎn)。

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

(16)

約束(16)表示車輛到達(dá)時(shí)間約束,其中tah、taj分別代表到達(dá)配送點(diǎn)h和j的時(shí)刻;thj表示從配送點(diǎn)h到配送點(diǎn)j的時(shí)間。

(17)

約束(17)避免車輛出現(xiàn)子回路。Vk表示車輛k訪問(wèn)的任一節(jié)點(diǎn)集合。

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

(18)

約束(18)是服務(wù)時(shí)間窗約束。

(19)

(20)

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

(21)

約束(19)～約束(21)表示決策變量的取值范圍。

5 仿真過(guò)程設(shè)計(jì)

仿真過(guò)程基于經(jīng)典的Solomon I1插入算法進(jìn)行設(shè)計(jì)[28],用于解決時(shí)間窗車輛路徑規(guī)劃、快速更新已有配送點(diǎn)的到達(dá)時(shí)間等問(wèn)題。選擇Solomon I1插入算法的原因在于該算法在其他時(shí)間窗車輛路徑類問(wèn)題的研究中體現(xiàn)了較高的求解效率和效果[15,29],尤其是在評(píng)估配送可行性時(shí)具有較高效率[13,30]。

算法大致可以分為3個(gè)核心模塊:訂單接受策略、基于SolomonI1插入算法的現(xiàn)有配送點(diǎn)到達(dá)時(shí)間更新和城市配送備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化,如圖3所示。其中,對(duì)于訂單的評(píng)估,采用基于輻射半徑的訂單接收策略,包括可接受時(shí)間窗分配初始化、可接受時(shí)間窗動(dòng)態(tài)調(diào)整、參照點(diǎn)動(dòng)態(tài)選擇及基于時(shí)間窗偏差閾值的配送需求評(píng)估等步驟[31]。

在圖3中,實(shí)線箭頭表示流程順序,虛線箭頭表示數(shù)據(jù)流。具體來(lái)說(shuō),更新后的服務(wù)選項(xiàng)分配結(jié)果在整個(gè)仿真過(guò)程中將長(zhǎng)期存貯,并為配送需求接受決策提供依據(jù)。詳細(xì)的仿真過(guò)程描述如下:

步驟1初始化時(shí)間窗寬度和配送中心坐標(biāo)等仿真基礎(chǔ)數(shù)據(jù);

步驟2按照基于輻射半徑的訂單接收策略[31],以配送中心為原點(diǎn)分配配送區(qū)域的交付方式和時(shí)間窗;

步驟3判斷是否停止接受本批次配送訂單,若停止接受,則仿真結(jié)束;若繼續(xù)接受新訂單,則轉(zhuǎn)入步驟4;

步驟4等待配送需求到達(dá);

步驟5配送需求到達(dá)后,根據(jù)基于輻射半徑的訂單接收策略[31],對(duì)配送需求選擇的配送方式和時(shí)間窗進(jìn)行評(píng)估;若拒絕此配送需求,則轉(zhuǎn)至步驟6;若接受此配送需求則轉(zhuǎn)至步驟8;

步驟6根據(jù)顧客初次選擇的服務(wù)選項(xiàng),優(yōu)化設(shè)計(jì)備選服務(wù)選項(xiàng)集;

步驟7顧客基于效用最大化目標(biāo),在備選服務(wù)選項(xiàng)集中挑選替代的服務(wù)選項(xiàng)組合;若顧客拒絕所有備選服務(wù)選項(xiàng),則跳轉(zhuǎn)至步驟3;若顧客從備選服務(wù)選項(xiàng)中完成挑選,則轉(zhuǎn)入步驟8;

步驟8將接受的配送需求納入已接受訂單集合;使用插入算法,調(diào)整現(xiàn)有配送路徑以滿足接受的配送需求,同時(shí)更新其他訂單的服務(wù)時(shí)間;

步驟9更新配送區(qū)域內(nèi)的配送方式和時(shí)間窗分配,跳轉(zhuǎn)至步驟3。

5.1 基于時(shí)間窗偏差閾值的配送需求評(píng)估

為了調(diào)整配送需求rti所選時(shí)間窗命中可接受時(shí)間窗集合SA的概率,設(shè)計(jì)基于時(shí)間窗偏差閾值的配送需求評(píng)估。其中,不同配送區(qū)域可接受時(shí)間窗集合SA采用基于輻射半徑的方法產(chǎn)生[31]。

時(shí)間窗偏差值用于衡量配送需求選擇的時(shí)間窗[earlyti,ateti]與可接受時(shí)間窗集合SA=[(Searlyi,Slatei):i∈|SA|]的重合程度,記為δ,其中|SA|表示t時(shí)刻配送需求rti所在區(qū)域預(yù)先分配的時(shí)間窗數(shù)量。時(shí)間窗偏差閾值是可接受配送需求的最大時(shí)間窗偏差值,記為δmax。在配送需求評(píng)估中,需要計(jì)算配送需求j的時(shí)間窗與集合SA中每個(gè)時(shí)間窗的偏差值δ,如式(22)所示:

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

(22)

其中timerange表示時(shí)間窗長(zhǎng)度,||表示取絕對(duì)值。

如圖4所示,時(shí)間窗長(zhǎng)度timerage是120分鐘,配送需求i的時(shí)間窗偏差值δi為0,配送需求j的時(shí)間窗偏差值δj為0.5,配送需求k的時(shí)間窗偏差值δk為1。配送需求評(píng)估的流程如圖5所示。

5.2 城市配送備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化

分別采用ε約束法(ε-constraint method)和帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅱ),求解構(gòu)建的優(yōu)化模型。

ε約束法是將某個(gè)目標(biāo)函數(shù)作為約束函數(shù),將多目標(biāo)問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解。通過(guò)調(diào)整目標(biāo)函數(shù)約束值的大小,進(jìn)而獲取多目標(biāo)問(wèn)題的帕累托解集。在構(gòu)建的模型中,將顧客替代選擇累計(jì)轉(zhuǎn)移率最大化目標(biāo)轉(zhuǎn)換為約束條件處理,如式(23)所示,其中ε代表顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值。

(23)

非支配排序遺傳算法是為了尋找多目標(biāo)帕累托解集,從基本遺傳算法拓展而來(lái),主要方法是通過(guò)定義的非支配排序,根據(jù)非劣解水平對(duì)種群進(jìn)行分層,通過(guò)不停進(jìn)化獲取問(wèn)題的帕累托解集[32]。

6 仿真實(shí)驗(yàn)

設(shè)定配送訂單的接受周期T為960分鐘,開(kāi)始接受下一批次配送訂單的時(shí)刻記為0時(shí)刻,960分鐘后停止接受本批次訂單并開(kāi)始配送。基于假設(shè)1和假設(shè)2,在[0,960)內(nèi),配送需求到達(dá)的時(shí)間間隔服從指數(shù)分布。算法采用MatlabR2017a版本,使用Matlab腳本語(yǔ)言實(shí)現(xiàn);仿真分析環(huán)境為IntelCore i7-6700 CPU、16G內(nèi)存和Windows10專業(yè)版。仿真涉及的參數(shù)如表1所示。其中,參數(shù)θd是尺度因子,表明備選項(xiàng)相關(guān)性大小。例如送貨上門交付尺度因子表示送貨上門交付下不同時(shí)間窗之間可替代性的大小。由于顧客在送貨上門交付下對(duì)等待時(shí)間更敏感,不同時(shí)間窗之間替代性更差,根據(jù)朱惠琦等(2020)[25],設(shè)置不同的送貨上門交付尺度因子和自提柜交付尺度因子。

表1 相關(guān)參數(shù)

在仿真分析過(guò)程中,圍繞構(gòu)造顧客備選服務(wù)選項(xiàng)集這一研究目的,首先討論不同優(yōu)化方法對(duì)于顧客替代選擇累計(jì)轉(zhuǎn)移率最大化的優(yōu)化結(jié)果以及服務(wù)選項(xiàng)更新的算法時(shí)間性能。然后分析時(shí)間窗偏差閾值的影響,最后重點(diǎn)分析顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值的影響。

6.1 仿真算例設(shè)計(jì)

仿真算例基于Solomon標(biāo)準(zhǔn)庫(kù)設(shè)計(jì),涵蓋了RC類和R類總計(jì)兩類4個(gè)算例,包括RC103,RC201,RC206和R207。RC類算例的配送點(diǎn)呈現(xiàn)分散和聚集結(jié)合的狀態(tài),與我國(guó)城市居民大多在多層建筑集中居住,以收件箱和自提點(diǎn)為主、送貨上門交付為輔的混合末端交付模式吻合。RC201算例和RC103總共有100個(gè)配送點(diǎn)。算例從6個(gè)配送點(diǎn)較密集的區(qū)域選擇6個(gè)配送點(diǎn)設(shè)立自提柜。其中,RC103算例中每條路徑上允許的最大顧客量更少。RC206算例總共有50個(gè)配送點(diǎn)。算例從5個(gè)配送點(diǎn)較密集的區(qū)域選擇5個(gè)配送點(diǎn)設(shè)立自提柜。此外,為了保證測(cè)試算例的多樣性,還采用了配送點(diǎn)完全分散的R類R207算例。根據(jù)假設(shè)3和假設(shè)5,配送需求從尚未產(chǎn)生配送需求的配送點(diǎn)集合中隨機(jī)產(chǎn)生。

6.2 仿真結(jié)果及多目標(biāo)優(yōu)化方法對(duì)比

采用ε約束法和NSGA-Ⅱ算法分別對(duì)RC103,RC201,RC206和R207四個(gè)算例進(jìn)行仿真求解100次,獲得各項(xiàng)指標(biāo)的平均值及相應(yīng)的單因素方差分析結(jié)果如表2～表5所示。

表2 RC201算例仿真結(jié)果

根據(jù)表2,在RC201算例中,ε約束法和NSGA-Ⅱ算法在RB收益、AHD收益及總收益不存在明顯差異,但是在行駛距離、車輛數(shù)量、服務(wù)選項(xiàng)更新耗時(shí)方面存在顯著差異。對(duì)于顧客替代選擇增加的訂單情況,ε約束法和NSGA-Ⅱ算法分別新增訂單數(shù)量為2.400和2.49個(gè),組間均方與組內(nèi)均方的比例F是0.119 5,小于相應(yīng)顯著水平下的F臨界值,可以認(rèn)為兩個(gè)算法對(duì)于優(yōu)化顧客替代選擇累計(jì)轉(zhuǎn)移率最大化目標(biāo)不存在明顯差異。在行駛距離方面,ε約束法耗費(fèi)的均值是1 536.168,高于NSGA-Ⅱ算法獲取的1 444.809,方差分析也顯示組間均方與組內(nèi)均方的比例F是7.356 5,大于相應(yīng)顯著水平下的F臨界值2.731 0(Fcrit),可以認(rèn)為在獲取相同收益的情形下,NSGA-Ⅱ算法能夠?qū)ふ业脚渌途嚯x更短的配送方案。因此,NSGA-Ⅱ算法獲得配送方案較ε約束法在收益距離比方面更占優(yōu)。

ε約束法需要的車輛數(shù)量均值是3.560,高于NSGA-Ⅱ算法(使用3.200),兩者使用的車輛數(shù)量存在明顯差異。ε約束法將通過(guò)外生變量ε將多目標(biāo)問(wèn)題轉(zhuǎn)為單目標(biāo)問(wèn)題求解。ε約束法的實(shí)質(zhì)是限定了顧客替代選擇累計(jì)轉(zhuǎn)移率的最小值。該方法為了滿足顧客差異化需求會(huì)增加配送距離和車輛數(shù)量。而NSGA-Ⅱ算法可以采用帕累托集合的形式自適應(yīng)平衡優(yōu)化多目標(biāo)。因此,ε約束法較NSGA-Ⅱ算法的配送距離更長(zhǎng),需要的車輛數(shù)量更多。

在服務(wù)選項(xiàng)更新耗時(shí)方面,NSGA-Ⅱ算法的平均耗時(shí)為12.216,遠(yuǎn)大于ε約束法,其方差分析的F值遠(yuǎn)大于臨界值Fcrit,且p<0.05,ε約束法和NSGA-Ⅱ的服務(wù)選項(xiàng)更新耗時(shí)存在明顯差異。這說(shuō)明,NSGA-Ⅱ算法可以通過(guò)更多的計(jì)算耗時(shí)獲取配送距離更小的方案。

根據(jù)表3,在RC206算例中,ε約束法和NSGA-Ⅱ算法除了在服務(wù)選項(xiàng)更新耗時(shí)方面存在顯著差異外,其余各項(xiàng)指標(biāo)方面不存在顯著差異。而在RC201算例中,兩種算法在行駛距離、車輛數(shù)量等指標(biāo)存在顯著差異,其原因在于:RC201算例的最大配送顧客數(shù)量是100個(gè)配送點(diǎn),遠(yuǎn)大于50個(gè)配送點(diǎn)的RC206算例;配送點(diǎn)數(shù)量更多,解空間也會(huì)增大,對(duì)算法的性能要求也就更高;雖然兩類算法在收益方面差異不顯著,但是對(duì)于配送點(diǎn)數(shù)量更多的RC201算例,NSGA-Ⅱ在車輛數(shù)量、行駛距離等方面優(yōu)于ε約束法。

表3 RC206算例仿真結(jié)果

根據(jù)表4,同樣具有100個(gè)配送點(diǎn)的RC103算例則與RC201算例結(jié)論比較一致,ε約束法和NSGA-Ⅱ算法在RB收益、AHD收益及總收益方面不存在明顯差異,但是在行駛距離、車輛數(shù)量、服務(wù)選項(xiàng)更新耗時(shí)方面存在顯著差異。

表4 RC103算例仿真結(jié)果

根據(jù)表5,不同于其他3個(gè)算例中配送點(diǎn)呈現(xiàn)分散和聚集結(jié)合的狀態(tài),R207算例中所有的配送點(diǎn)呈現(xiàn)分散的狀態(tài)。配送點(diǎn)的分布情況對(duì)兩種算法的性能存在明顯影響,無(wú)論是收益、配送距離還是配送時(shí)間,ε約束法和NSGA-Ⅱ算法均存在顯著差異。相對(duì)來(lái)說(shuō),NSGA-Ⅱ算法耗時(shí)更多,能夠獲取更高的收益,但配送距離也會(huì)顯著增加,收益距離比并不明顯占優(yōu)。

表5 R207算例仿真結(jié)果

總之,對(duì)于配送點(diǎn)分布呈現(xiàn)分散和聚集結(jié)合的情形,采用的ε約束法和NSGA-Ⅱ算法均能有效求解構(gòu)建的城市配送備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型;兩種方法獲取的各類收益不存在顯著差異,但是在車輛行駛距離、車輛數(shù)量方面,NSGA-Ⅱ算法更適用于配送點(diǎn)數(shù)量更多的情形。對(duì)于配送點(diǎn)分布完全分散的情形,NSGA-Ⅱ算法耗時(shí)更多,能夠獲取更高的收益,但配送距離也會(huì)顯著增加,收益距離比并不明顯占優(yōu)。

6.3 時(shí)間窗偏差閾值的影響

時(shí)間窗偏差閾值是指可接受配送需求的最大時(shí)間窗偏差值。時(shí)間窗偏差閾值越小,說(shuō)明可接受的配送需求選擇的時(shí)間窗與該區(qū)域預(yù)先分配的時(shí)間窗重合程度越高。根據(jù)NSGA-Ⅱ算法在求解配送點(diǎn)數(shù)量較多情形的優(yōu)勢(shì),采用NSGA-Ⅱ算法分析時(shí)間窗偏差閾值的影響。

4個(gè)算例的仿真結(jié)果隨著時(shí)間窗偏差閾值變化的情況分別如圖6～圖9所示。在圖中,時(shí)間窗偏差閾值的影響采用雙縱坐標(biāo)形式展現(xiàn),其中左縱坐標(biāo)標(biāo)識(shí)收益數(shù)值,右縱坐標(biāo)標(biāo)識(shí)距離,主要分析RB收益、AHD收益、總收益以及行駛距離隨時(shí)間窗偏差閾值從0到1增長(zhǎng)過(guò)程中的變化情況。

根據(jù)圖6～圖9所示,在RC201、RC203、RC103和R207算例中,隨著時(shí)間窗偏差閾值逐漸增加,總收益呈現(xiàn)逐漸下降趨勢(shì),其中AHD收益受到時(shí)間窗偏差閾值變化的影響明顯,RB收益則呈現(xiàn)震蕩上升的趨勢(shì);由于AHD收益下降太多,總收益呈現(xiàn)下降趨勢(shì)。其原因在于,隨著時(shí)間窗偏差閾值逐漸增加,可接受需求的時(shí)間窗需要與預(yù)先分配的時(shí)間窗重合度提高,AHD服務(wù)需求被拒絕的概率增加,其收益呈現(xiàn)下降趨勢(shì);RB服務(wù)僅需要在時(shí)間窗最晚服務(wù)時(shí)間之前提供,對(duì)服務(wù)時(shí)間窗的約束更小,時(shí)間窗偏差閾值的變化對(duì)其影響不大,同時(shí)隨著替代服務(wù)選擇的提供,顧客選擇RB服務(wù)的概率也會(huì)增加,因此RB收益呈現(xiàn)震蕩增長(zhǎng)趨勢(shì)。隨著AHD服務(wù)需求減少,行駛距離在配送點(diǎn)較多的RC201算例、RC103算例和R207算例中呈現(xiàn)震蕩下降趨勢(shì);由于RC206算例的配送點(diǎn)較小,行駛距離的變化趨勢(shì)不明顯。

6.4 顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值的影響

顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值是ε約束法中將顧客替代選擇累計(jì)轉(zhuǎn)移率最大化目標(biāo)轉(zhuǎn)換為約束條件所設(shè)置的可接受最小目標(biāo)值。最小約束值越大,意味著為拒絕顧客提供的備選服務(wù)選項(xiàng)數(shù)量越多。顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值的影響采用ε約束法分析。

4個(gè)算例的仿真結(jié)果隨著最小約束值變化的情況分別如圖10～圖13所示。在圖中,顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值的影響采用雙縱坐標(biāo)形式展現(xiàn),其中左縱坐標(biāo)標(biāo)識(shí)收益,右縱坐標(biāo)標(biāo)識(shí)距離,主要分析RB收益、AHD收益、總收益以及行駛距離隨最小約束值從0到100%增長(zhǎng)過(guò)程中的變化情況。

根據(jù)圖10～圖13所示,在RC201、RC203、RC103和R207算例中,AHD收益與總收益的變化趨勢(shì)比較一致,RB收益對(duì)于總收益的變化趨勢(shì)影響較小。這意味著為顧客提供的備選服務(wù)選項(xiàng)數(shù)量能夠影響AHD服務(wù)訂單數(shù)量,而對(duì)于RB訂單數(shù)量影響較少。AHD收益、RB收益及總收益隨著最小約束值的變化趨勢(shì)不明顯,顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值對(duì)收益的影響不存在線性關(guān)系。由于行駛距離與AHD服務(wù)數(shù)量密切相關(guān),相應(yīng)的行駛距離與顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值也不存在明確趨勢(shì)關(guān)系。

在RC201、RC203、RC103和R207算例中,時(shí)間窗偏差閾值及顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值對(duì)總收益的聯(lián)合影響如圖14～圖17所示,其中,總收益最大時(shí)兩參數(shù)的取值使用游標(biāo)標(biāo)明。

仿真結(jié)果顯示,收益最大值均不在時(shí)間窗偏差閾值及最小約束值的邊界處獲取;收益值在兩者的定義域內(nèi)呈現(xiàn)離散且局部極大值遍布的情形;總體上看,在時(shí)間窗偏差閾值較小、顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值較大的區(qū)域,往往能獲取更高的總收益。

7 結(jié)束語(yǔ)

在城市配送從通用無(wú)差異服務(wù)向個(gè)性定制化轉(zhuǎn)型升級(jí)的情境下,提高配送資源使用效率是城市配送運(yùn)營(yíng)商重要的核心競(jìng)爭(zhēng)力,是平衡服務(wù)成本和消費(fèi)者滿意度、實(shí)現(xiàn)定制化城市配送可持續(xù)發(fā)展的重要基礎(chǔ)。根據(jù)顧客對(duì)配送選項(xiàng)的偏好,為服務(wù)成本較高的服務(wù)需求提供成本可行的備選服務(wù)選項(xiàng)集合,實(shí)現(xiàn)配送需求與配送資源之間的匹配,成為城市配送運(yùn)營(yíng)商提高配送資源使用效率的重要措施之一。基于此,本文討論了顧客對(duì)服務(wù)選項(xiàng)的替代選擇行為,構(gòu)建了考慮期望距離最小和顧客替代選擇累計(jì)轉(zhuǎn)移率最大的城市配送備選服務(wù)選項(xiàng)集多目標(biāo)優(yōu)化模型。仿真結(jié)果顯示:對(duì)于配送點(diǎn)分布呈現(xiàn)分散和聚集結(jié)合的情形,ε約束法和NSGA-Ⅱ算法對(duì)優(yōu)化顧客替代選擇累計(jì)轉(zhuǎn)移率最大化目標(biāo)不存在明顯差異;NSGA-Ⅱ算法在配送點(diǎn)數(shù)量更多的情形可以有效降低車輛行駛距離、車輛數(shù)量等成本因素;對(duì)于配送點(diǎn)分布完全分散的情形,NSGA-Ⅱ算法耗時(shí)更多,能夠獲取更高的收益,但配送距離也會(huì)顯著增加,收益距離比并不明顯占優(yōu);允許顧客選擇的時(shí)間窗與分配的時(shí)間窗之間差異越大,損失的收益也就越大,尤其是對(duì)AHD收益的影響更明顯,可接受的時(shí)間窗偏差閾值是決策的重要指標(biāo);若供應(yīng)商縮小時(shí)間窗偏差閾值,應(yīng)適當(dāng)增加顧客替代選擇累計(jì)轉(zhuǎn)移率最小約束值,可以改善總收益。本文設(shè)計(jì)的模型和求解算法為服務(wù)水平約束下提供差異化城市配送服務(wù)提供了較好的解決思路和工具,在此基礎(chǔ)上考慮即時(shí)配送、需求管理等差異化運(yùn)營(yíng)場(chǎng)景將是下一步的研究方向。