多中心聯(lián)合配送模式下集貨需求隨機(jī)的VRPSDP問題

范厚明 劉鵬程 劉浩 侯登凱

車輛路徑問題(Vehicle routing problem,VRP)是物流配送企業(yè)的核心問題,自Dantzig 等[1]在1959 年首次提出之后,眾多學(xué)者對(duì)該問題展開了研究,并衍生出隨機(jī)需求車輛路徑問題(Vehicle routing problem with stochastic demand,VRPSD)、多中心車輛路徑問題(Multi-depot vehicle routing problem,MDVRP)以及同時(shí)配集貨車輛路徑問題(Vehicle routing problem with simultaneous delivery and pickup,VRPSDP)等眾多VRP 拓展問題.本文研究的多中心聯(lián)合配送模式下集貨需求隨機(jī)的同時(shí)配集貨車輛路徑問題(Multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution,MDVRPSDDSPJD)是綜合考慮了VRPSD、MDVRP、VRPSDP 及聯(lián)合配送特點(diǎn)的科學(xué)問題.

近年來,有關(guān)MDVRP、MDVRPJD(Multidepot vehicle routing problem based on joint distribution)、VRPSD 問題已成為VRP 拓展問題研究的熱點(diǎn).葛顯龍等[2]對(duì)基于聯(lián)合配送的多中心開放式動(dòng)態(tài)車輛路徑問題進(jìn)行研究,針對(duì)跨區(qū)域多中心聯(lián)合配送的情況,建立“多對(duì)多”的網(wǎng)絡(luò)配送機(jī)制,車輛配送完成后可就近返回任意配送中心,設(shè)計(jì)云遺傳算法對(duì)問題進(jìn)行求解.楊翔等[3]研究了帶有模糊時(shí)間窗的MDVRP 問題,假設(shè)虛擬配送中心對(duì)多配送中心問題進(jìn)行處理,設(shè)計(jì)了改進(jìn)的蟻群算法對(duì)問題進(jìn)行求解.Gruler 等[4]對(duì)帶有隨機(jī)需求的MDVRP 問題進(jìn)行研究,設(shè)計(jì)了結(jié)合迭代局部搜索算法的模擬優(yōu)化算法對(duì)問題進(jìn)行求解.Alinaghian等[5]研究了多車廂多類型產(chǎn)品的MDVRP 問題,車輛從配送中心出發(fā)最終返回原配送中心,在配送過程中,針對(duì)同一種產(chǎn)品不允許拆分服務(wù),設(shè)計(jì)了結(jié)合自適應(yīng)大鄰域搜索算法和變鄰域搜索算法的混合算法對(duì)問題進(jìn)行求解.葛顯龍等[6]研究了需求可拆分模式下的集配一體化MDVRP 問題,設(shè)計(jì)改進(jìn)遺傳算法進(jìn)行求解.陳呈頻等[7]對(duì)多車型MDVRP 問題進(jìn)行研究,車輛從配送中心出發(fā)對(duì)客戶進(jìn)行服務(wù)后,最終返回原配送中心,設(shè)計(jì)多染色體遺傳算法對(duì)問題進(jìn)行求解.Wang 等[8]研究了時(shí)變網(wǎng)絡(luò)下的多中心車輛路徑問題,提出了新的交通資源共享策略,結(jié)合節(jié)約算法、掃描算法和多目標(biāo)粒子群算法設(shè)計(jì)了混合元啟發(fā)式算法對(duì)問題進(jìn)行求解.Li 等[9]研究了帶時(shí)間窗限制的多目標(biāo)綠色MDVRP 問題,設(shè)計(jì)改進(jìn)蟻群算法對(duì)問題進(jìn)行求解.可見,眾多學(xué)者從時(shí)間窗、多車型、需求可拆分、隨機(jī)需求以及配集貨等方面進(jìn)一步深化了對(duì)MDVRP 問題的研究.

多中心同時(shí)配集貨車輛路徑問題(Multi-depot vehicle routing problem with simultaneous delivery and pickup,MDVRPSDP)是集成了MDVRP 和VRPSDP 問題而展開的研究.該問題涉及多個(gè)配送中心的物流配送企業(yè)對(duì)同時(shí)具有配貨需求和集貨需求的客戶點(diǎn)進(jìn)行配集貨服務(wù).Li 等[10]研究了閉環(huán)式MDVRPSDP 問題,車輛從配送中心出發(fā),服務(wù)完客戶后返回原配送中心,設(shè)計(jì)基于迭代局部搜索的元啟發(fā)式算法對(duì)問題進(jìn)行求解.Kachitvichyanukul 等[11]研究了多中心多種配集貨需求的車輛路徑問題,針對(duì)不同的客戶配集貨需求,車輛可從任一位置出發(fā),且無須返回原配送中心,設(shè)計(jì)基于粒子群的改進(jìn)算法對(duì)問題進(jìn)行求解.Soriano 等[12]對(duì)兩個(gè)區(qū)域多中心配集貨車輛路徑問題進(jìn)行研究,要求車輛服務(wù)完成后返回原配送中心,設(shè)計(jì)了自適應(yīng)大鄰域搜索算法對(duì)問題進(jìn)行求解.Ben Alaia 等[13]對(duì)閉環(huán)式多車輛多中心配集貨車輛路徑問題進(jìn)行研究,采用遺傳算法和粒子群算法對(duì)問題進(jìn)行求解.Bouanane 等[14]研究了帶有庫(kù)存限制的MDVRPSDP問題,并設(shè)計(jì)了一種結(jié)合最近倉(cāng)庫(kù)啟發(fā)式算法、掃描算法和最遠(yuǎn)插入啟發(fā)式算法的混合遺傳算法進(jìn)行求解.

綜上文獻(xiàn)梳理可見,在以下幾個(gè)方面有待更深入的研究.1)現(xiàn)有對(duì)于MDVRP 問題的研究通常采用先分組后路徑的方式,將客戶劃分到不同的區(qū)域,每個(gè)配送中心僅負(fù)責(zé)該區(qū)域內(nèi)的客戶,將MDVRP 問題轉(zhuǎn)化為多個(gè)獨(dú)立的單中心VRP 進(jìn)行求解.該方法未能考慮到多個(gè)配送中心聯(lián)合配送的優(yōu)勢(shì),客戶資源不能共享,難以對(duì)整個(gè)配送網(wǎng)絡(luò)進(jìn)行全局優(yōu)化.2)未考慮多個(gè)配送中心之間車輛資源共享并設(shè)計(jì)適合其特點(diǎn)的車輛返回規(guī)則.在對(duì)閉環(huán)式MDVRP 問題的研究中,僅考慮了各配送中心對(duì)于客戶資源共享,而對(duì)于車輛資源共享方面研究不足,導(dǎo)致車輛在完成配集貨服務(wù)后仍需返回原配送中心,造成路徑成本的增加.在對(duì)開放式MDVRP問題的研究中,車輛服務(wù)完客戶后,通常采用就近返回任意配送中心的規(guī)則.在配送中心車輛數(shù)量有限的情況下,雖然就近返回配送中心規(guī)則會(huì)降低本次車輛調(diào)度的成本,但未能根據(jù)配送中心的需求進(jìn)行合理的車輛分配,造成車輛的無序分配,使得下一次規(guī)劃車輛路徑受到限制.即需要先進(jìn)行配送中心間的車輛調(diào)度,增加了額外的路徑成本.3)針對(duì)MDVRPSDP 方面的研究,所涉及的客戶集貨量和配貨量多為確定型,然而在許多實(shí)際配送服務(wù)中,常存在客戶配貨量已知、集貨量不確定的情況.例如,在一個(gè)地區(qū)含有多個(gè)配送中心的玻璃制造公司對(duì)該地區(qū)客戶進(jìn)行服務(wù),其中配貨量可以通過客戶訂單來確定,而對(duì)于從客戶手中收集的玻璃原材料,客戶使用過程中損壞、剩余的廢舊玻璃以及玻璃殘次品的回收量無法得知,僅能根據(jù)以往的經(jīng)驗(yàn)得知其服從的某種概率分布.以往的研究缺乏對(duì)于不確定環(huán)境下的MDVRPSDP 的研究.

MDVRPSDDSPJD 問題是集成上述三個(gè)方面而展開的研究,已有方法無法適用于MDVRPSDDSPJD 問題的原因在于以下兩方面.1)已有文獻(xiàn)對(duì)于車輛返回規(guī)則的算法設(shè)計(jì)無法應(yīng)用于本文提出的適合車輛共享特點(diǎn)的車輛返回規(guī)則.2)在已有研究中,對(duì)于VRPSDP 問題的算法設(shè)計(jì)未考慮隨機(jī)需求對(duì)于車輛實(shí)時(shí)載重量的影響以及隨機(jī)需求引起的對(duì)于服務(wù)失敗點(diǎn)的二次配送.在VRPSD 問題的研究中,未考慮由于客戶雙重需求引起的車輛初始裝載量的設(shè)計(jì).即傳統(tǒng)對(duì)于VRPSD 問題的研究中,車輛從配送中心出發(fā)時(shí),車輛初始裝載量為滿載(配貨的情況)或者空載(集貨的情況).然而針對(duì)MDVRPSDDSPJD 問題的研究,由于集貨需求的隨機(jī)性,必須考慮車輛的初始裝載量情況,不能同傳統(tǒng)VRPSD 問題一般,滿載(或空載)出發(fā)對(duì)客戶進(jìn)行服務(wù).

本文針對(duì)MDVRPSDDSPJD 問題展開研究,闡述MDVRPSDDSPJD 的衍生進(jìn)程,并構(gòu)建了兩階段MDVRPSDDSPJD 模型.預(yù)優(yōu)化階段基于隨機(jī)機(jī)會(huì)約束機(jī)制以及車載量約束為客戶分配車輛,生成預(yù)優(yōu)化方案;重優(yōu)化階段針對(duì)服務(wù)失敗的客戶點(diǎn)采用重優(yōu)化策略生成重優(yōu)化路徑.根據(jù)問題特征設(shè)計(jì)自適應(yīng)變鄰域文化基因算法對(duì)問題進(jìn)行求解,并通過三組算例對(duì)本文的模型及算法進(jìn)行驗(yàn)證.MDVRPSDDSPJD 問題之所以能應(yīng)用到含有多個(gè)配送中心的物流企業(yè)實(shí)施多中心聯(lián)合配送問題中,是由于含有多個(gè)配送中心的物流企業(yè)中有著唯一的決策者或各決策者之間思想與行為高度協(xié)調(diào)一致,且各配送中心之間不存在利益沖突或建有利益分配機(jī)制.因此,本文對(duì)MDVRPSDDSPJD 進(jìn)行研究不僅進(jìn)一步拓展了VRP 問題的理論研究,也有利于提高物流配送活動(dòng)的效率,為制定科學(xué)合理的物流企業(yè)車輛調(diào)度計(jì)劃提供理論依據(jù),具有重要的理論和實(shí)踐價(jià)值.

1 問題描述及模型建立

1.1 問題提出

經(jīng)典的MDVRP 通常指在一個(gè)區(qū)域中含有多個(gè)配送中心的物流配送企業(yè),車輛從某一配送中心出發(fā),對(duì)客戶進(jìn)行服務(wù)后返回原配送中心.如圖1(a)所示,車輛K1從配送中心V1出發(fā),對(duì)客戶 1、2、6進(jìn)行服務(wù)后返回配送中心V1,車輛K2同理.

MDVRP 問題考慮的是客戶僅具有一種需求,然而,在實(shí)際中存在客戶同時(shí)具有配貨和集貨需求的情況,車輛在對(duì)客戶進(jìn)行服務(wù)時(shí),需要同時(shí)滿足客戶的配、集貨需求.僅具有配貨(或集貨)的單一需求的情況,可以看作是同時(shí)配集貨問題的特例,即集貨(或配貨)量為0 的情況.由此,原問題便拓展成了MDVRPSDP 問題.由于配、集貨量的加入,車輛的裝載量不再是單一的增加(集貨)或者減少(配貨),需要考慮在行駛過程中車輛裝載量的波動(dòng)情況,車輛的實(shí)時(shí)裝載量應(yīng)始終小于車輛容量,因此該問題較單一需求的問題更加復(fù)雜.如圖1(b)所示,車輛K1從配送中心V1出發(fā),對(duì)客戶1、2 進(jìn)行服務(wù)后,由于車輛剩余空間無法滿足客戶6 的集貨量需求,因此車輛K1返回配送中心V1;車輛K2從配送中心V2出發(fā),經(jīng)檢驗(yàn),發(fā)現(xiàn)車輛裝載量可以滿足客戶4、5、3 的配、集貨需求,車輛K2對(duì)客戶4、5、3 服務(wù)后,返回配送中心V2;派出車輛K3從配送中心V1出發(fā),對(duì)客戶6 服務(wù)完成后,返回配送中心V1.

圖1 MDVRPSDDSPJD 的衍生進(jìn)程Fig.1 Derivation of MDVRPSDDSPJD

在MDVRPSDP 問題的基礎(chǔ)上,考慮到客戶配貨量確定、集貨量為隨機(jī)變量以及多中心之間聯(lián)合配送的情況,便形成了MDVRPSDDSPJD 問題.多中心聯(lián)合配送機(jī)制打破了傳統(tǒng)的分區(qū)域配送模式,從全局的角度出發(fā)對(duì)客戶進(jìn)行聯(lián)合配送服務(wù).此外,由于隨機(jī)變量的引入,可能產(chǎn)生在某個(gè)客戶點(diǎn)不能滿足客戶的需求,導(dǎo)致服務(wù)失敗,車輛需返回配送中心后重新對(duì)服務(wù)失敗的客戶點(diǎn)進(jìn)行服務(wù).如圖1(c)所示,假設(shè)車輛的預(yù)優(yōu)化方案為V1-1-2-6-V1,V2-4-5-3-V2.車輛K1從配送中心V1出發(fā),按照預(yù)優(yōu)化方案,對(duì)客戶 1、2 服務(wù)后,在客戶6 處,由于客戶隨機(jī)集貨需求的影響,經(jīng)檢驗(yàn),車輛剩余空間無法滿足其集貨需求,車輛K1返回配送中心V1,客戶6 為失敗點(diǎn);車輛K2從配送中心V2出發(fā),按照預(yù)優(yōu)化方案,對(duì)客戶 4 服務(wù)完成后,經(jīng)過預(yù)判斷發(fā)現(xiàn)車輛剩余空間無法滿足客戶5 的需求,則車輛不再對(duì)客戶5 進(jìn)行服務(wù),車輛K2提前返回配送中心V2;對(duì)于未完成服務(wù)的客戶3、5、6 重新規(guī)劃路徑,由車輛K3從配送中心V2出發(fā),按照重優(yōu)化路徑V2-5-6-3-V2對(duì)未完成服務(wù)的客戶點(diǎn)進(jìn)行服務(wù),服務(wù)完成后返回配送中心V2.

本文綜合考慮多個(gè)配送中心聯(lián)合配送、客戶資源共享、車輛資源統(tǒng)一調(diào)度、客戶同時(shí)具有配集貨需求以及客戶集貨需求的隨機(jī)性,對(duì)MDVRPSDDSPJD 問題進(jìn)行研究,構(gòu)建兩階段求解方案.預(yù)優(yōu)化階段,車輛從配送中心出發(fā)按照預(yù)優(yōu)化路徑對(duì)客戶進(jìn)行服務(wù);重優(yōu)化階段,對(duì)于預(yù)優(yōu)化階段服務(wù)失敗的客戶點(diǎn)進(jìn)行重新優(yōu)化.車輛服務(wù)完成后,按照車輛返回規(guī)則返回配送中心.

1.2 問題描述

本文研究的MDVRPSDDSPJD 問題描述如下.配送網(wǎng)絡(luò)有完備的有向圖G(V,E) ;所有節(jié)點(diǎn)集合VV c ∪V d{0},客戶節(jié)點(diǎn)集合V c{1,2,···,n},配送中心集合Vd{n+1,n+2,···,n+m},節(jié)點(diǎn)0 為引入的虛擬配送中心編號(hào),虛擬配送中心同其他實(shí)際配送中心相連接且同各個(gè)實(shí)際配送中心間的距離為0;邊集合E{(i,j)|i,j ∈V},兩節(jié)點(diǎn)i,j之間的路徑成本為cij;k為可用配送車輛集合K{1,2,···,φ}的任一車輛,最大車輛數(shù)為φ,車輛容量為Q;客戶節(jié)點(diǎn)i(i ∈V c) 的配貨量為d i,選用泊松分布對(duì)客戶點(diǎn)的集貨需求信息進(jìn)行表征[15],客戶點(diǎn)i的集貨量為隨機(jī)變量ξi,相互獨(dú)立并且服從泊松分布,客戶點(diǎn)i的集貨量為q的概率為P iqPr(ξiq),q0,1,2,···;0≤q ≤Q,i ∈V c,期望值 E[ξi]和方差Var[ξi]均為λ;假設(shè)客戶無配送時(shí)間要求.決策變量xijk表示車輛k是否直接從點(diǎn)i到達(dá)點(diǎn)j,是為1,否為0;yik表示客戶點(diǎn)i(i ∈V c)是否由車輛k服務(wù),是為1,否為0.需要解決的問題是車輛從配送中心出發(fā),對(duì)客戶進(jìn)行配集貨服務(wù)后,返回配送中心,要求規(guī)劃車輛行駛路徑,使得總路徑成本最低.

1.3 預(yù)優(yōu)化階段

在預(yù)優(yōu)化階段,考慮到客戶點(diǎn)集貨需求的隨機(jī)性,本文引入隨機(jī)機(jī)會(huì)約束機(jī)制對(duì)是否為客戶點(diǎn)服務(wù)進(jìn)行預(yù)判斷.假設(shè)某一條預(yù)優(yōu)化路徑V k{s,t,e,w},V k ?V c,為車輛服務(wù)的客戶序列集合,車輛從某一配送中心出發(fā),按照預(yù)優(yōu)化路徑進(jìn)行配送服務(wù).當(dāng)車輛對(duì)客戶∑s,t,e服務(wù)完成后,其實(shí)時(shí)車載量可表達(dá)為Q ewk為車輛服務(wù)∑完客戶e后而在訪問客戶w之前的車輛裝載量,為車輛從配送中心出發(fā)時(shí)的初始裝載量.在車輛訪問客戶點(diǎn)w前,引入隨機(jī)機(jī)會(huì)約束機(jī)制對(duì)是否為客戶點(diǎn)w提供服務(wù)進(jìn)行檢驗(yàn),預(yù)先設(shè)置風(fēng)險(xiǎn)偏好值α,α ∈(0,1] .此時(shí)客戶點(diǎn)w集貨量與車輛服務(wù)完客戶e后實(shí)時(shí)車載量應(yīng)滿足ξw ≤Q ?Q ewk+d w,當(dāng)隨機(jī)約束以預(yù)設(shè)的偏好值水平α成立,則可以對(duì)客戶點(diǎn)w進(jìn)行配集貨服務(wù).即 Pr{ξw ≤Q ?Q ewk+d w}≥α,α的設(shè)定取決于決策者在隨機(jī)環(huán)境下基于風(fēng)險(xiǎn)偏好的喜好程度,α值越大,代表決策者的保守性越強(qiáng),更重視服務(wù)的成功率;α值越小,代表決策者的冒險(xiǎn)性越強(qiáng),更希望用一輛車配送更多的客戶.

在以往的閉環(huán)式MDVRP 問題的研究中,車輛服務(wù)完成后返回原配送中心,雖然保證了配送中心含有的車輛數(shù)平衡,考慮了配送中心之間的客戶資源可以共享,但忽略了車輛資源的共享,造成路徑成本的增加.在開放式MDVRP 問題的研究中,車輛服務(wù)完成后可就近返回任意配送中心,但就近返回規(guī)則存在著不合理性,因?yàn)樵趯?duì)配送中心進(jìn)行選址時(shí),其輻射范圍、客戶等均已考慮在內(nèi),并根據(jù)客戶需求為其配備適量的車輛,因此配送中心所應(yīng)含有的車輛數(shù)是受到限制的.然而車輛就近返回任意配送中心的規(guī)則會(huì)導(dǎo)致配送中心車輛數(shù)目的混亂,造成配送中心對(duì)車輛的需求數(shù)與所擁有的車輛數(shù)的不平衡,即車輛返回哪一個(gè)配送中心會(huì)影響到下一次路徑優(yōu)化時(shí)各配送中心含有的初始車輛數(shù).若仍然按照以往的車輛就近返回規(guī)則,可能會(huì)產(chǎn)生額外的配送中心之間車輛調(diào)度的成本,隨著規(guī)劃次數(shù)的增加,各配送中心的車輛數(shù)將產(chǎn)生更大的無序性,甚至可能出現(xiàn)某配送中心無車輛可用的情況.綜合考慮兩種車輛返回規(guī)則的優(yōu)缺點(diǎn),并基于多中心聯(lián)合配送的特點(diǎn),本文提出新的車輛返回規(guī)則:車輛從配送中心出發(fā),可返回任意配送中心,但應(yīng)滿足每個(gè)配送中心車輛的進(jìn)出平衡,即配送中心駛離的車輛數(shù)應(yīng)等于返回該配送中心的車輛數(shù),保證每一次路徑優(yōu)化完畢后,各配送中心的車輛數(shù)不變.

1.3.1 模型建立

相應(yīng)的MDVRPSDDSPJD 模型如下:

目標(biāo)函數(shù)式(1)為最小化運(yùn)輸總成本;式(2)為隨機(jī)容量機(jī)會(huì)約束,保證為客戶j服務(wù)成功的概率大于等于預(yù)設(shè)的風(fēng)險(xiǎn)偏好值α;式(3)表示車輛k訪問客戶p前后的車輛負(fù)載平衡約束;式(4)表示車輛在訪問客戶i之后的車載量約束;式(5)為車輛初始裝載量;式(6)表示每個(gè)客戶只被一輛車服務(wù);式(7)表示相同節(jié)點(diǎn)之間沒有路徑;式(8)為車輛進(jìn)出平衡約束;式(9)和式(10)保證客戶點(diǎn)被車輛服務(wù)時(shí)一定有路徑與其連接;式(11)表示車輛被使用時(shí)只有一條服務(wù)路徑且從虛擬配送中心出發(fā),并最終回到虛擬配送中心;式(12)保證了從虛擬配送中心出發(fā)的車輛數(shù)不超過總車輛數(shù);式(13)為從任意一個(gè)配送中心出發(fā)的車輛數(shù)等于返回該配送中心的車輛數(shù);式(14)為決策變量取值約束.

1.3.2 隨機(jī)機(jī)會(huì)約束確定型等價(jià)處理

式(2)為對(duì)單個(gè)客戶點(diǎn)的隨機(jī)機(jī)會(huì)約束,由單點(diǎn)隨機(jī)機(jī)會(huì)約束式可以得到每條配集貨路徑的隨機(jī)機(jī)會(huì)約束式,如式(15):

即在預(yù)優(yōu)化方案中,對(duì)于任意的車輛k(k ∈K),每條路徑中客戶點(diǎn)的集貨量之和不超過車輛裝載量的概率大于等于預(yù)設(shè)的風(fēng)險(xiǎn)偏好值α.將隨機(jī)機(jī)會(huì)約束式(15)轉(zhuǎn)化為確定型的等價(jià)形式,進(jìn)行預(yù)優(yōu)化路徑客戶點(diǎn)的選取,可以在保證得到理論上的最優(yōu)解時(shí)降低計(jì)算量.

存在常數(shù)τ滿足τΦ?1(α) 時(shí),(τ為α分位點(diǎn)),式(16)等價(jià)于:

進(jìn)而有:

將期望值和方差代入式(18):

由于集貨量服從泊松分布,期望值和方差相等且為λ,因而存在一個(gè)常數(shù),使得式(15)轉(zhuǎn)化如下:

1.4 重優(yōu)化階段

由于客戶點(diǎn)集貨量為隨機(jī)變量,可能會(huì)導(dǎo)致車輛在到達(dá)某一個(gè)客戶點(diǎn)時(shí),車輛實(shí)時(shí)剩余空間無法滿足客戶的集貨需求從而造成路徑失敗,對(duì)于服務(wù)失敗的客戶點(diǎn)稱為失敗點(diǎn).由于預(yù)優(yōu)化方案并不一定能完全實(shí)施,因此需要采取重優(yōu)化策略對(duì)失敗點(diǎn)進(jìn)行合理規(guī)劃.

在以往對(duì)隨機(jī)需求問題的研究中,對(duì)于失敗點(diǎn)的處理方法多為失敗點(diǎn)返回策略、失敗點(diǎn)前序點(diǎn)返回策略以及分離配集貨策略三種[16?19].圖2 給出了一個(gè)簡(jiǎn)單的示例,對(duì)不同的失敗點(diǎn)重優(yōu)化策略進(jìn)行分析,實(shí)線代表預(yù)優(yōu)化方案路徑,虛線代表由重優(yōu)化策略得出的路徑.假設(shè)有兩條預(yù)優(yōu)化路徑V1-1-2-6-V1、V2-4-5-3-V2(如圖2(a)),V1、V2為配送中心,節(jié)點(diǎn)i和j之間的路徑成本為cij,客戶2 和客戶5 為路徑失敗點(diǎn).

1)失敗點(diǎn)返回策略(如圖2(b)).當(dāng)車輛在客戶2 處發(fā)生服務(wù)失敗時(shí),車輛返回配送中心后,再按照預(yù)優(yōu)化方案繼續(xù)對(duì)客戶2 及其后續(xù)客戶進(jìn)行服務(wù);客戶5 同理.

2)失敗點(diǎn)前序點(diǎn)返回策略(如圖2(c)).在對(duì)客戶2 進(jìn)行服務(wù)前,對(duì)車輛剩余空間能否滿足客戶2 需求的期望值(或通過計(jì)算預(yù)選返回點(diǎn)得到路徑方案的總體期望成本等方法)進(jìn)行預(yù)判斷,當(dāng)車輛剩余空間大于等于該客戶的需求期望時(shí)對(duì)其進(jìn)行服務(wù),否則車輛返回配送中心后再按照預(yù)優(yōu)化方案對(duì)客戶2 及其后續(xù)客戶點(diǎn)進(jìn)行服務(wù);客戶5 同理.

3)分離配集貨策略(如圖2(d)).若到達(dá)客戶2時(shí),車輛剩余空間無法滿足客戶2 的全部集貨需求,則僅滿足部分集貨需求后,繼續(xù)對(duì)其后續(xù)客戶點(diǎn)進(jìn)行服務(wù);客戶5 同理.最后將未完成服務(wù)的客戶2和客戶5 看作經(jīng)典的VRP 問題進(jìn)行求解.

上述三種策略中,失敗點(diǎn)返回策略會(huì)造成路徑的往返,導(dǎo)致路徑成本的大量增加,而且失敗點(diǎn)返回策略一定劣于失敗點(diǎn)前序點(diǎn)返回策略,原因在于由三角形三邊原理可知c12+c20>c10(客戶5 同理);失敗點(diǎn)前序點(diǎn)返回策略對(duì)點(diǎn)選擇的要求嚴(yán)格,選取合適的返回點(diǎn)較為困難,對(duì)客戶點(diǎn)不當(dāng)?shù)念A(yù)判斷易導(dǎo)致多余的返回,引起路徑成本的增加;分離配集貨策略缺乏對(duì)是否服務(wù)客戶的預(yù)判斷,可能產(chǎn)生多次服務(wù)客戶的情況,降低客戶的滿意度并造成路徑的往返,增加路徑成本.鑒于以上三種方案存在的不足,本文采取文獻(xiàn)[20]中所提出的路徑失敗點(diǎn)重優(yōu)化策略并作出改進(jìn)(如圖2(e)).當(dāng)車輛未能滿足客戶需求造成路徑失敗(客戶2 處的失敗原因)或通過預(yù)判斷不對(duì)客戶進(jìn)行服務(wù)(客戶5 處的失敗原因)時(shí),車輛返回配送中心,統(tǒng)計(jì)所有路徑的失敗點(diǎn)及失敗點(diǎn)后續(xù)客戶(客戶點(diǎn)2、3、5、6),根據(jù)最近鄰法求解原理,重新設(shè)計(jì)配集貨路徑,生成第二階段重優(yōu)化路徑.在重優(yōu)化路徑中,客戶點(diǎn)的集貨量仍然是隨機(jī)變量,因此重優(yōu)化路徑仍可能出現(xiàn)路徑失敗,對(duì)該情況執(zhí)行失敗點(diǎn)返回策略.由于在重優(yōu)化階段,失敗點(diǎn)及其后續(xù)客戶點(diǎn)的規(guī)模相對(duì)較小,而車輛的載重量較大,因此重優(yōu)化路徑中再次出現(xiàn)失敗點(diǎn)的概率極小.

圖2 不同失敗點(diǎn)重優(yōu)化策略對(duì)比圖Fig.2 Different failure points re-optimized strategies

2 自適應(yīng)變鄰域文化基因算法

MDVRPSDDSPJD 是一類NP-hard(Non-deterministic polynomial-hard)問題,在以往對(duì)于VRP 及其拓展問題的求解算法中,元啟發(fā)式算法具備較強(qiáng)的尋優(yōu)能力,能在合理的時(shí)間內(nèi)給出問題的近似最優(yōu)解,廣泛應(yīng)用于各種VRP 拓展問題中,表現(xiàn)出了較強(qiáng)的競(jìng)爭(zhēng)優(yōu)勢(shì).其中,文化基因算法是基于文化進(jìn)化理論中的隱喻機(jī)制而提出的,具有較強(qiáng)的全局搜索性能和局部搜索性能.變鄰域搜索算法采用多個(gè)不同的鄰域結(jié)構(gòu)進(jìn)行系統(tǒng)搜索,具有較強(qiáng)的局部搜索能力.因此,本文結(jié)合文化基因算法和變鄰域搜索算法設(shè)計(jì)了自適應(yīng)變鄰域文化基因算法(Adaptive memetic algorithm and variable neighborhood search,AMAVNS),將變鄰域搜索算法應(yīng)用到文化基因算法的局部搜索策略中,加強(qiáng)種群的尋優(yōu)能力;引入順序交叉算子,加強(qiáng)種群個(gè)體間的交流;設(shè)計(jì)自適應(yīng)鄰域搜索次數(shù)策略和自適應(yīng)劣解接受機(jī)制平衡進(jìn)化所需的廣度和深度,加快算法的收斂以及加強(qiáng)算法跳出局部最優(yōu)的能力.本文的算法框架如圖3 所示.

圖3 自適應(yīng)變鄰域文化基因算法框架圖Fig.3 The basic flow of adaptive memetic algorithm and variable neighborhood search

2.1 編解碼方式及初始種群的生成

本文算法采用整數(shù)編碼的方式,將客戶的全排列存儲(chǔ)到矩陣pop_route中,記錄客戶的服務(wù)順序.解碼方式分為兩個(gè)階段,第一階段通過隨機(jī)機(jī)會(huì)約束機(jī)制以及車輛載重約束檢驗(yàn),將客戶按照初始排列順序劃分給車輛,當(dāng)對(duì)下一個(gè)客戶進(jìn)行檢驗(yàn)發(fā)現(xiàn)當(dāng)前車輛不能滿足要求時(shí),派出新車對(duì)該客戶進(jìn)行服務(wù);第二階段根據(jù)每輛車首尾客戶到配送中心的距離以及配送中心車輛進(jìn)出平衡約束確定車輛的始末配送中心.本文給出一個(gè)簡(jiǎn)單例子來進(jìn)行說明,如圖4 所示,假設(shè)客戶矩陣pop_route中客戶排列為135674829,派出第一輛車按照客戶排列順序?qū)Φ谝粋€(gè)客戶進(jìn)行服務(wù),在車輛派遣矩陣V eh_K中記錄V eh_K(1)1,即第一輛車的初始服務(wù)客戶為pop_route矩陣中的第一個(gè)客戶;按照pop_route中客戶排列順序?qū)ο乱粋€(gè)客戶進(jìn)行隨機(jī)機(jī)會(huì)約束機(jī)制以及車輛載重約束檢驗(yàn),假設(shè)當(dāng)對(duì)第四個(gè)客戶6 進(jìn)行檢驗(yàn)時(shí),不能滿足檢驗(yàn)要求,則派出第二輛車對(duì)客戶6 進(jìn)行服務(wù),記錄V eh_K(2)4 ;以此類推,直到最后一個(gè)客戶檢驗(yàn)完成.最后根據(jù)每輛車首尾客戶到配送中心的最小距離確定始末配送中心,根據(jù)車輛進(jìn)出平衡原則進(jìn)行檢查,對(duì)于不符合車輛進(jìn)出平衡約束的配送中心進(jìn)行調(diào)整,確定最終的始末配送中心.即車輛始發(fā)的配送中心矩陣V eh_K_sta以及車輛返回的配送中心矩陣V eh_K_end.客戶排列最終解碼路徑如圖5 所示.

圖4 編碼方式示意圖Fig.4 Encoding mode diagram

圖5 解碼路徑圖Fig.5 Decoding routing diagram

可以看出,僅需記錄每輛車服務(wù)的首個(gè)客戶的位置,就可以結(jié)合pop_route矩陣求得該車輛服務(wù)的客戶順序,在后續(xù)的進(jìn)化操作以及局部搜索策略中也僅對(duì)編碼長(zhǎng)度固定的pop_route矩陣進(jìn)行操作.采用客戶排列順序、車輛服務(wù)的客戶以及車輛往返的配送中心分離編碼的方式,可以使得在后續(xù)的迭代擾動(dòng)時(shí),總能生成可行解,避免了編碼長(zhǎng)度不固定以及對(duì)不可行解的修復(fù)困難等問題.

在生成初始種群方面,采用隨機(jī)生成和最近鄰法相結(jié)合的方式,既能夠保證種群的多樣性,又能通過最近鄰解提高初始種群的質(zhì)量,加快種群的收斂速度.

2.2 適應(yīng)度函數(shù)

染色體的適應(yīng)度函數(shù)根據(jù)目標(biāo)函數(shù)式(1)進(jìn)行構(gòu)建.顯然,目標(biāo)函數(shù)值越大,染色體的適應(yīng)度值越小,染色體S的適應(yīng)度函數(shù)f S可以表示如下:

其中,ZS為染色體S的目標(biāo)函數(shù)值.

2.3 選擇操作

選擇操作采用輪盤賭和精英保留相結(jié)合的策略.采用輪盤賭的方式,每個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值的大小成正比,即適應(yīng)度函數(shù)值越大的個(gè)體被選中的概率就越高;反之,被選中的概率越低.采用精英保留策略,將每一代的最優(yōu)個(gè)體進(jìn)行保留,即用父代適應(yīng)度值最優(yōu)的個(gè)體替換掉子代適應(yīng)度值最差的個(gè)體.采用輪盤賭和精英保留相結(jié)合的策略,可以在進(jìn)化的過程中形成穩(wěn)定的下一代,使得算法快速收斂.

2.4 進(jìn)化操作

本文的進(jìn)化操作選用順序交叉算子.如圖6 所示,對(duì)個(gè)體pop1 進(jìn)行順序交叉時(shí),從種群中隨機(jī)選取個(gè)體pop2,分別隨機(jī)產(chǎn)生點(diǎn)位i11、i12,i21、i22.pop1隨機(jī)點(diǎn)位i11、i12之間的部分作為新個(gè)體new_pop1的第一段;new_pop1的后續(xù)點(diǎn)位與pop2有關(guān),即先消除pop2中包含pop1隨機(jī)點(diǎn)位i11、i12之間的客戶點(diǎn),在消除過程中,pop2 中客戶點(diǎn)的位置順序不改變,再將消除后的客戶點(diǎn)排列作為new_pop1的第二段,此時(shí)new_pop1 個(gè)體生成完畢.new_pop2同理.

圖6 順序交叉算子示意圖Fig.6 The diagram of ordered crossover operator

2.5 局部搜索策略

文化基因算法的局部搜索策略是算法的核心功能之一,決定著算法的局部搜索能力,本文將變鄰域搜索算法算法應(yīng)用到局部搜索策略中,加強(qiáng)對(duì)種群的深度搜索.設(shè)定l個(gè)鄰域結(jié)構(gòu)集合N k{N1,N2,···,N l},對(duì)種群中個(gè)體x從第一個(gè)鄰域結(jié)構(gòu)N1開始擾動(dòng).若在預(yù)設(shè)的鄰域搜索次數(shù)S n內(nèi)未找到改進(jìn)解,則執(zhí)行下一個(gè)鄰域結(jié)構(gòu).若在某一鄰域結(jié)構(gòu)內(nèi)獲得改進(jìn)解x′,則令xx′,并返回第一個(gè)鄰域結(jié)構(gòu)重新開始迭代,直到循環(huán)到最后一個(gè)鄰域結(jié)構(gòu)仍未找到改進(jìn)解時(shí),搜索終止;或當(dāng)變鄰域搜索循環(huán)次數(shù)達(dá)到預(yù)設(shè)值M ax_S n時(shí),搜索終止,算法進(jìn)入下一階段.本文采用如下4 種鄰域結(jié)構(gòu),增強(qiáng)算法的局部搜索能力.

1)插入:隨機(jī)選擇一個(gè)客戶點(diǎn)i,將其從原方案中移除,隨機(jī)插入到某個(gè)客戶點(diǎn)j的后面.如圖7(a)所示,客戶3 插入到客戶6 的后面.

2)交換:隨機(jī)選中兩個(gè)客戶點(diǎn)i和j,交換兩客戶點(diǎn)的位置.如圖7(b)所示,客戶3 和客戶6 交換位置.

3)2-插入:在原方案中隨機(jī)選擇連續(xù)的兩個(gè)客戶點(diǎn),將其插入到隨機(jī)選擇的客戶點(diǎn)j的后面.如圖7(c)所示,客戶3、4 插入到客戶6 后面.

4)2-opt:隨機(jī)選擇兩客戶點(diǎn)i和j,并將客戶點(diǎn)間的順序進(jìn)行交換.如圖7(d)所示,保持客戶3的位置不變,客戶4、5、7、6 逆序.

圖7 鄰域結(jié)構(gòu)示意圖Fig.7 Neighborhood structures

2.6 自適應(yīng)機(jī)制

本文設(shè)計(jì)自適應(yīng)鄰域搜索次數(shù)策略和自適應(yīng)劣解接受機(jī)制平衡進(jìn)化所需的廣度和深度,使算法跳出局部最優(yōu).

1)在算法迭代的不同時(shí)期,種群所需的擾動(dòng)強(qiáng)度不同.在迭代初期,采用較低的鄰域搜索次數(shù),加快種群的收斂;隨著最優(yōu)解連續(xù)未改變次數(shù)的增大,增加鄰域搜索次數(shù),加強(qiáng)算法的搜索能力,并結(jié)合自適應(yīng)劣解接受機(jī)制使算法跳出局部最優(yōu).本文的自適應(yīng)鄰域搜索次數(shù)策略所下.

a)設(shè)置初始鄰域搜索次數(shù)為Sn1,最優(yōu)解連續(xù)未改變的次數(shù)為Con_num;

b)若本次迭代后的種群最優(yōu)解未改進(jìn),則令Con_numCon_num+1,SnSn+1;若迭代后的最優(yōu)解存在改進(jìn),則令Con_num0,Sn1;

c)當(dāng)最優(yōu)解連續(xù)未改變的次數(shù)Con_num達(dá)到預(yù)設(shè)值Stop_num時(shí),算法終止,輸出最優(yōu)解.

2)設(shè)計(jì)自適應(yīng)劣解接受機(jī)制對(duì)是否接受擾動(dòng)后的解進(jìn)行判斷,本文的自適應(yīng)劣解接受機(jī)制如下.

a)設(shè)置閾值參數(shù)t,t1+Con_num/gen,gen為迭代的代數(shù);

b)當(dāng)擾動(dòng)產(chǎn)生的新解x′滿足f(x′)≤tf˙(x),則令xx′.

設(shè)置最小可接受劣解的代數(shù)M in_gen,即算法的前M in_gen代擾動(dòng)操作禁止接受劣解,當(dāng)算法迭代到中后期時(shí),算法逐步陷入局部最優(yōu),劣解接受機(jī)制被激活.隨著最優(yōu)解連續(xù)未改變的次數(shù)Con_num的增加,t值逐漸增大,可接受劣解的范圍也逐漸增大,增大種群的多樣性,使得算法跳出局部最優(yōu).

3 算例驗(yàn)證及結(jié)果分析

本文選取了三類算例驗(yàn)證本文算法的有效性,包括MDVRP 算例、VRPSDP 算例和MDVRPSDDSPJD 算例,由于MDVRP 和VRPSDP 是本文研究的基礎(chǔ)問題,因此首先選取MDVRP 算例和VRPSDP 算例對(duì)本文算法進(jìn)行驗(yàn)證.本文算法編程工具采用MATLAB R2017b,操作系統(tǒng)為Windows10,電腦內(nèi)存為8 GB,CPU 為Intel i7-7700,主頻3.60 GHz.經(jīng)過反復(fù)測(cè)試,本文算法參數(shù)設(shè)置如下:最大迭代次數(shù)M ax_gen800 ,種群規(guī)模Pop_size30 ～150,初始變鄰域搜索次數(shù)Sn1,最大鄰域循環(huán)次數(shù)M ax_Sn1 000,最優(yōu)解連續(xù)未改變的最大次數(shù)Stop_num20 ～50,最小可接受劣解的代數(shù)M in_gen30 ～100 .參數(shù)的設(shè)置值同對(duì)應(yīng)算例中客戶點(diǎn)規(guī)模n相關(guān),當(dāng)n ≤30 時(shí),Pop_size設(shè)置為30,Stop_num設(shè)置為20,最小可接受劣解的代數(shù)M in_gen30;當(dāng) 30

3.1 MDVRP 算例分析

實(shí)驗(yàn)1.選取文獻(xiàn)[21]中提出的MDVRP 算例,客戶規(guī)模為30,含有3 個(gè)配送中心(A、B、C)且每個(gè)配送中心含有4 輛車,目前已有文獻(xiàn)對(duì)該算例求得的最優(yōu)解為116.01.表1 給出聚類分層法[22],狼群算法[23],文獻(xiàn)[24]中提出的禁忌搜索算法、量子遺傳算法、云量子遺傳算法以及本文的自適應(yīng)變鄰域文化基因算法求解10 次的計(jì)算結(jié)果.其中文獻(xiàn)[22]中聚類分層法采用分區(qū)域配送的方式,文獻(xiàn)[23?24]以及本文算法均采用聯(lián)合配送的方式進(jìn)行配送.BK S為目前已有文獻(xiàn)求得的最優(yōu)解,Best、Worst、Avg分別為算法運(yùn)行10 次所求得的最優(yōu)解、最劣解和平均解,%Dev為算法求得的解同目前已知最優(yōu)解的偏差,CPU為算法運(yùn)行時(shí)間.

由表1 可以看出,在求解質(zhì)量方面,文獻(xiàn)[22]通過分區(qū)域配送方式將多中心問題轉(zhuǎn)化為單中心問題進(jìn)行求解,這種求解思想從本質(zhì)上來看是局部?jī)?yōu)化的思想,求解效果最差.本文算法對(duì)現(xiàn)有最優(yōu)解進(jìn)行了改進(jìn),求得最優(yōu)解為113.62,較原有文獻(xiàn)求得的最優(yōu)解改進(jìn)了2.06%;在求解最劣解以及平均解方面,也均優(yōu)于其他算法.在計(jì)算時(shí)間方面,本文算法運(yùn)行時(shí)間僅為4.78 s,相較于其他算法,具有較強(qiáng)的競(jìng)爭(zhēng)優(yōu)勢(shì).表2 給出本文求解的車輛行駛路徑.圖8 給出了最短路徑變化趨勢(shì)圖,可以看出本文算法可以在較少的迭代次數(shù)內(nèi)快速收斂,當(dāng)算法陷入局部最優(yōu)解時(shí),可快速跳出局部最優(yōu),具有較好的尋優(yōu)性能.

圖8 最短路徑變化趨勢(shì)圖Fig.8 The iterative trend of optimal solution

表1 算法性能比較Table 1 Performance comparison of different types of metaheuristics

表2 本文算法求解路徑Table 2 The algorithm solution path of this paper

實(shí)驗(yàn)2.選擇由標(biāo)準(zhǔn)算例庫(kù)提供的MDVRP 算例集對(duì)本文算法進(jìn)行驗(yàn)證(算例集來源:http://neo.lcc.uma.es/vrp/vrp-instances/multiple-depotvrp-instances/).表3 給出了貪婪隨機(jī)自適應(yīng)搜索算法(GRASP/VND)[25]、遺傳算法(GA)[26]、迭代局部搜索算法(ILS)[27]以及本文的AMAVNS 算法運(yùn)行10 次的最優(yōu)解.BK S為算例庫(kù)中給出的已知最優(yōu)解,Best為算法運(yùn)行10 次所求得的最優(yōu)解,%Dev為算法求得的最優(yōu)解同已知最優(yōu)解的偏差,CPU為算法平均運(yùn)行時(shí)間.

由表3 可以看出,在對(duì)7 個(gè)標(biāo)準(zhǔn)算例的求解中,GRASP/VND 算法、GA 算法以及ILS 算法均未找到最優(yōu)解.GRASP/VND 算法求解質(zhì)量最差,求解最大偏差為11.85%,平均偏差4.81%;GA 算法求解質(zhì)量一般,最大偏差9.05%,平均偏差3.12%;ILS 算法求解最大偏差6.09%,平均偏差4.51%.本文AMAVNS 算法求解速度略差于其他三種算法,但求解質(zhì)量最優(yōu),求得其中兩個(gè)最優(yōu)解,最大偏差3.80%,平均偏差1.76%.驗(yàn)證了本文算法的有效性.

表3 MDVRP 算例結(jié)果比較Table 3 The results comparison of MDVRP instances

3.2 VRPSDP 算例分析

實(shí)驗(yàn)3.選擇由Dethloff[28]提出的客戶規(guī)模為50 的測(cè)試算例,算例根據(jù)兩種不同的地理情況分為SCA(Scattered)和CON(Concentrated)兩大類.表4 給出了禁忌搜索算法(TS)[29]、并行節(jié)約算法(EPSA3)[30]、節(jié)約蟻群算法(SavAnt)[31]、分散搜索算法(SS)[32]以及本文的AMAVNS 算法在SCA8和CON8 的20 個(gè)算例中運(yùn)行10 次的最優(yōu)解.Best表示算法求解該算例得到的最優(yōu)值,%Dev表示每個(gè)算例中各算法的最優(yōu)解同5 個(gè)算法中最優(yōu)解的偏差,CPU為運(yùn)行時(shí)間.圖9 給出了本文算法在算例SCA8-0、SCA8-1 的求解路徑圖.

圖9 實(shí)驗(yàn)3 部分算例的求解路徑圖Fig.9 The specific path diagrams of some cases of experiment 3

由表4 可以看出,在SCA8、CON8 共20 個(gè)算例中,TS 算法求得了其中6 個(gè)最優(yōu)解,最大偏差2.65%,平均偏差0.83%,算法耗時(shí)較短;EPSA3算法求解運(yùn)行時(shí)間最短,但求解質(zhì)量最差,僅求得其中1 個(gè)最優(yōu)解,最大偏差5.57%,平均偏差2.52%;Sav Ant 算法求解時(shí)間最長(zhǎng),求得4 個(gè)最優(yōu)解,最大偏差2.69%,平均偏差0.61%;SS 算法求得其中6 個(gè)最優(yōu)解,最大偏差2.65%,平均偏差0.83%;本文AMAVNS 算法求解速度良好,求解質(zhì)量?jī)?yōu)于其他4 種算法,求得其中13 個(gè)最優(yōu)解,最大偏差0.83%,平均偏差0.12%,在未取得最優(yōu)解的算例中,偏差均保持在1%以內(nèi).再次驗(yàn)證了本文算法的有效性及算法的穩(wěn)定性能.

表4 VRPSDP 算例結(jié)果比較Table 4 The results comparison of VRPSDP instances

3.3 MDVRPSDDSPJD 算例分析

實(shí)驗(yàn)4.由于現(xiàn)有研究沒有關(guān)于MDVRPSDDSPJD 問題的標(biāo)準(zhǔn)算例,通過對(duì)標(biāo)準(zhǔn)MDVRP 算例p01 進(jìn)行修改以適應(yīng)本文的模型.p01 算例含有4 個(gè)配送中心(配送中心編號(hào)51～54),每個(gè)配送中心含有4 輛同質(zhì)車輛,車輛容量為80,客戶規(guī)模為50(客戶編號(hào)1～50).客戶的配、集貨量由Salhi 等[33]提出的需求分離規(guī)則產(chǎn)生:x i和y i是客戶的坐標(biāo),q i為客戶i的原始需求,計(jì)算每個(gè)客戶的比率r imin(x i/y i;y i/x i),由dir i q i和ξiq i d i計(jì)算得出該客戶的配、集貨量.在對(duì)客戶進(jìn)行配送路徑優(yōu)化時(shí),客戶的集貨量是未知的,僅能知道客戶需求服從λ6.34 的泊松分布.車輛從配送中心出發(fā),服務(wù)完客戶后返回配送中心.目標(biāo)是規(guī)劃車輛行駛路徑,使得總路徑成本最低.表5 給出傳統(tǒng)的車輛返回原配送中心規(guī)則(規(guī)則1)和本文提出的車輛返回規(guī)則(規(guī)則2)在不同風(fēng)險(xiǎn)偏好值決策下分別求解20 次的計(jì)算結(jié)果.Best為該規(guī)則下求解的最優(yōu)解,Avg為算法運(yùn)行20 次的平均解,%Dev為規(guī)則2 在最優(yōu)解和平均解方面相較于規(guī)則1 的偏差,CPU為算法運(yùn)行時(shí)間.表6 給出算法所求最優(yōu)解對(duì)應(yīng)的車輛行駛路徑.

由表5 可以看出,在不同風(fēng)險(xiǎn)偏好值決策下,求解結(jié)果具有明顯的區(qū)別,規(guī)則1 在α0.7 時(shí)求得最優(yōu)解533.85,平均值為624.97;規(guī)則2 在α0.7時(shí)求得最優(yōu)解499.96,平均值為610.54.當(dāng)風(fēng)險(xiǎn)偏好值α增大時(shí),決策者偏向于保守型,希望以較大的概率成功服務(wù)客戶.對(duì)于服務(wù)成功概率較小的客戶點(diǎn),選擇不去配送,提前返回配送中心,導(dǎo)致在重優(yōu)化階段需要為其重新規(guī)劃路徑,造成了路徑成本的增加.當(dāng)風(fēng)險(xiǎn)偏好值α減小時(shí),決策者偏向于冒險(xiǎn)型,希望一輛車能夠服務(wù)更多的客戶.然而由于隨機(jī)因素的影響,導(dǎo)致車輛剩余空間無法滿足客戶的集貨需求,造成服務(wù)客戶失敗,需要折返配送中心后,重新為其服務(wù).因此,冒險(xiǎn)型決策的路徑失敗造成的額外路徑成本要大于保守型決策的額外路徑成本.基于此,本文建議決策者風(fēng)險(xiǎn)偏好值α取0.7 左右,既能防止由于α值偏大,一輛車服務(wù)客戶數(shù)較少的弊端,又能避免由于α值過小,頻繁折返配送中心,造成額外成本的增加.

此外,通過規(guī)則1 和規(guī)則2 的對(duì)比,可以看出,本文提出的車輛返回規(guī)則較傳統(tǒng)的車輛返回原配送中心規(guī)則在最優(yōu)解方面改進(jìn)了6.35%,使用車輛數(shù)減少了一輛,在總的求解平均值方面改進(jìn)了4.45%.這是由于傳統(tǒng)的車輛返回原配送中心規(guī)則僅考慮了配送中心之間客戶資源的共享,缺乏對(duì)于車輛資源的統(tǒng)一調(diào)配,導(dǎo)致車輛返回配送中心受到限制,造成路徑成本的增加.實(shí)驗(yàn)結(jié)果表明,本文提出的車輛返回規(guī)則能夠有效地降低路徑成本,為多個(gè)配送中心之間車輛聯(lián)合調(diào)度提供參考.

4 結(jié)論

本文針對(duì)多中心聯(lián)合配送模式下集貨需求隨機(jī)的同時(shí)配集貨車輛路徑問題進(jìn)行了研究,主要結(jié)論如下.

1)本文提出的MDVRPSDDSPJD 問題不僅考慮了多中心聯(lián)合配送、客戶及車輛資源共享,而且考慮到客戶同時(shí)具有配集貨需求且集貨需求為隨機(jī)變量的情況,是對(duì)MDVRP、VRPSDP 等研究的進(jìn)一步深化和拓展.

2)基于多中心聯(lián)合配送的特點(diǎn),提出車輛返回規(guī)則.即車輛從配送中心出發(fā),可返回任意配送中心,但需保持每個(gè)配送中心車輛進(jìn)出平衡.經(jīng)驗(yàn)證表明,該規(guī)則較傳統(tǒng)的車輛返回規(guī)則有明顯的改進(jìn),能夠有效降低企業(yè)的路徑成本.

3)設(shè)計(jì)的自適應(yīng)變鄰域文化基因算法,將變鄰域搜索算法引入文化基因算法的局部搜索策略中,提高了算法的尋優(yōu)性能;設(shè)計(jì)的自適應(yīng)鄰域搜索次數(shù)策略和自適應(yīng)劣解接受機(jī)制能夠平衡算法進(jìn)化所需的廣度和深度,提高了算法跳出局部最優(yōu)的能力.

4)通過多組算例對(duì)本文的模型及算法進(jìn)行驗(yàn)證,結(jié)果表明,所建的模型及設(shè)計(jì)的算法能有效解決MDVRPSDDSPJD 問題,同其他類型的算法進(jìn)行比較,本文算法尋優(yōu)能力較強(qiáng)、搜索穩(wěn)定,具有較強(qiáng)的優(yōu)勢(shì).

本文的研究能為具有多個(gè)配送中心的物流企業(yè)實(shí)施多中心聯(lián)合配送提供較好的解決方案.但需要指出的是,物流企業(yè)可能面臨多重不確定環(huán)境且車輛調(diào)度會(huì)受到客戶時(shí)間窗因素的影響,如何在時(shí)間窗約束下刻畫和解決多重不確定環(huán)境下的車輛調(diào)度問題是未來需要繼續(xù)研究的方向.