楊屹夫，孫 冰，馬艷芳，程 聰，馮翠英

1.河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401

2.浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，杭州 310014

在電子商務(wù)時(shí)代，市民既希望所購(gòu)物品能夠快速交付，又能夠減少市區(qū)的交通擁堵。但隨著網(wǎng)購(gòu)需求的日益增長(zhǎng)和客戶需求的多樣化，給物流公司在以較低成本的條件下保證高效率的物流服務(wù)帶來(lái)了難題。為了實(shí)現(xiàn)及時(shí)交付并緩解交通擁堵，已經(jīng)提出了解決“最后一公里”物流問(wèn)題的方法——設(shè)立二級(jí)物流設(shè)施，以配送點(diǎn)為例，貨車先將部分客戶的包裹送至配送點(diǎn)，而配送點(diǎn)則通過(guò)配送車來(lái)為這些客戶提供配送服務(wù)。而另一種逐漸盛行的方法是設(shè)立自助點(diǎn)，特別是在防疫背景下提出的“無(wú)接觸取送貨”，更是促進(jìn)自助點(diǎn)在物流領(lǐng)域的發(fā)展。自助點(diǎn)在物流活動(dòng)中起到臨時(shí)倉(cāng)儲(chǔ)的作用，同樣是一種二級(jí)設(shè)施，其一般設(shè)立在小區(qū)、社區(qū)等居住人口密度大的區(qū)域，便于客戶前往自助點(diǎn)取貨，或?qū)⑽锲匪椭磷灾c(diǎn)臨時(shí)存放，等待物流公司取走?？蛻舾鶕?jù)自身情況，結(jié)合周圍物流設(shè)施，提前在網(wǎng)上選擇其所需服務(wù)類型，而物流公司以此為依據(jù)選擇開放二級(jí)物流設(shè)施、規(guī)劃配送路徑，滿足客戶不同的服務(wù)需求。自助點(diǎn)服務(wù)可以直接減少配送距離和所需訪問(wèn)的客戶，進(jìn)而有效減低運(yùn)輸、人工、車輛等物流成本。

本文依據(jù)客戶選擇接受的服務(wù)類型將客戶分為“自取需求型客戶”和“配送需求型客戶”兩類，前一類客戶自行前往附近的自助點(diǎn)完成取送貨，后一類客戶由配送車到達(dá)客戶點(diǎn)完成取送貨。在如此分類下，不僅使得用戶不同的服務(wù)需求得以滿足，還有利于上述問(wèn)題的解決。本文考慮了設(shè)立二級(jí)物流設(shè)施，并在典型的配送點(diǎn)的基礎(chǔ)上進(jìn)一步引入自助點(diǎn)，構(gòu)建包含兩類二級(jí)設(shè)施的物流網(wǎng)絡(luò)，分別服務(wù)于不同類型的客戶，以物流總成本最小為目標(biāo)，為物流公司在客戶服務(wù)差異環(huán)境下的服務(wù)策略提供支持。

本文研究的是自取需求型客戶和配送需求型客戶同時(shí)存在時(shí)的二級(jí)配送網(wǎng)絡(luò)優(yōu)化問(wèn)題，目前也有一些文獻(xiàn)在客戶分類方面進(jìn)行了研究。郭曉宇等[1]通過(guò)建立用戶評(píng)價(jià)體系，用k-means算法將客戶按重要度進(jìn)行分類，對(duì)不同類型客戶在配送貨物提取或延遲中采用不同的策略。夏揚(yáng)坤等[2]研究了進(jìn)行客戶分級(jí)并增加重要客戶的時(shí)間窗偏離懲罰程度，引導(dǎo)算法求解時(shí)優(yōu)先滿足重要客戶的時(shí)間窗。劉秋萍[3]在配送資源受限的情況下，考慮了客戶價(jià)值和時(shí)間敏感度對(duì)客戶的服務(wù)優(yōu)先級(jí)進(jìn)行劃分，并為不同類型客戶設(shè)計(jì)不同的時(shí)間窗約束。黃秋彬[4]同樣考慮客戶重要度的影響對(duì)客戶進(jìn)行分類，建立了物流總成本最小和客戶滿意度最大的雙目標(biāo)模型，通過(guò)M-NSGA-Ⅱ（非支配排序遺傳算法）求解，證明了對(duì)客戶進(jìn)行分級(jí)配送管理的合理性。以上文獻(xiàn)通過(guò)評(píng)估客戶價(jià)值或重要度來(lái)進(jìn)行客戶分類，希望提高物流服務(wù)的客戶滿意度，然而由于評(píng)價(jià)的過(guò)程往往缺乏客觀且客戶信息不易獲取，大多情況下不能達(dá)到預(yù)期效果，本文按照客戶希望接受的物流服務(wù)對(duì)客戶進(jìn)行分類，直接獲取客戶需求，更直觀地為客戶提供所需物流服務(wù)。

兩級(jí)選址-路徑問(wèn)題在近幾年也吸引許多學(xué)者研究，這類問(wèn)題一般指的是具有兩級(jí)物流設(shè)施的問(wèn)題。第一級(jí)設(shè)施通常指車輛在運(yùn)輸過(guò)程中的起點(diǎn)，例如中央配送中心等，第二級(jí)設(shè)施指在運(yùn)輸過(guò)程中的中轉(zhuǎn)站，比如區(qū)域配送網(wǎng)點(diǎn)[5]和配送點(diǎn)等。Nguyen等[6]研究2E-LRP的問(wèn)題，第一層和第二層設(shè)施均有容量約束和開放成本，建立了三下標(biāo)模型，然后通過(guò)MS-ILS-PR算法求解。Contardo等[7]針對(duì)同樣的問(wèn)題，使用分支-切割法（B&C）和適應(yīng)性大規(guī)模鄰域搜索方法（ALNS）求解，并將兩種方法進(jìn)行比較。Schwengerer等[8]為求解該問(wèn)題，將求解LRP問(wèn)題的VNS算法進(jìn)行改進(jìn)，該算法有7種基本的鄰域結(jié)構(gòu)，并結(jié)合兩種局域搜索算法進(jìn)行解的改進(jìn)。Enthoven等[9]對(duì)于設(shè)置配送點(diǎn)和客戶自取點(diǎn)為中轉(zhuǎn)站的2E-VRP-CO問(wèn)題進(jìn)行研究，采用改進(jìn)后的ALNS算法進(jìn)行求解。關(guān)于同時(shí)取送貨的車輛路徑問(wèn)題（VRPSPD）的研究，最早由Min[10]提出，Dethloff[11]進(jìn)一步將模型進(jìn)行完善。李博威等[12]考慮了帶軟時(shí)間窗的同時(shí)取送貨問(wèn)題，建立MINLP模型，并采用LINGO對(duì)模型進(jìn)行求解。而更多學(xué)者采用啟發(fā)式算法進(jìn)行求解，如張烜熒等[13]提出一種超啟發(fā)式分布估計(jì)算法，張慶華等[14]采用模因算法求解，王超等[15]提出一種改進(jìn)的布谷鳥算法（DCS），并驗(yàn)證了算法的有效性。郭放等[16]考慮設(shè)置前置倉(cāng)進(jìn)行補(bǔ)存貨操作的VRPSPD問(wèn)題，并設(shè)計(jì)了一種基于節(jié)約算法與自適應(yīng)大鄰域搜索的混合啟發(fā)式算法CWIGALNS求解問(wèn)題。目前有關(guān)二級(jí)選址-路徑的文獻(xiàn)中缺乏取送貨的研究，且已有文獻(xiàn)大多只考慮配送成本最低，暫未有文獻(xiàn)結(jié)合客戶服務(wù)需求差異進(jìn)行研究，本文采用在2E-LRP求解上被Enthoven等[9]證明效果較好的ALNS算法求解模型，并對(duì)其進(jìn)行了改進(jìn)和有效性檢驗(yàn)。

綜合以上分析，可知已有文獻(xiàn)中同時(shí)考慮2E-LRP和VRPSPD問(wèn)題的論文較少，且有關(guān)車輛路徑問(wèn)題的客戶分類大多從客戶重要度的角度出發(fā)，暫無(wú)按客戶服務(wù)需求對(duì)客戶進(jìn)行分類的車輛路徑問(wèn)題的研究?，F(xiàn)有研究主要從VRPSPD的基礎(chǔ)問(wèn)題上增加限制條件或者從提升算法性能方面進(jìn)行，而缺乏在設(shè)置前置配送點(diǎn)、自助點(diǎn)策略以及構(gòu)建兩級(jí)配送網(wǎng)絡(luò)方面的研究。本文考慮了不同配送點(diǎn)的可用配送車數(shù)量以及多車型，更加貼合實(shí)際情況?？偟膩?lái)說(shuō)，本文旨在考慮客戶不同服務(wù)需求的情況下，構(gòu)建并優(yōu)化兩級(jí)同時(shí)取送貨配送網(wǎng)絡(luò)來(lái)研究城市物流配送服務(wù)的問(wèn)題，并結(jié)合了二級(jí)設(shè)施選址，多類型配送車輛等因素，在已知二級(jí)設(shè)施擁有的配送車輛情況的條件下，使得配送總成本最小化?？偝杀景ㄜ囕v固定成本、運(yùn)輸成本、自助點(diǎn)與客戶點(diǎn)的連接成本、二級(jí)設(shè)施開放成本。

1 問(wèn)題描述及數(shù)學(xué)模型

1.1 問(wèn)題描述

該問(wèn)題可以描述為一個(gè)多級(jí)網(wǎng)絡(luò)，節(jié)點(diǎn)由三層構(gòu)成，第一層是配送中心，第二層是配送點(diǎn)、自助點(diǎn)，第三層是客戶點(diǎn)。第一、二層的節(jié)點(diǎn)通過(guò)車輛路徑進(jìn)行連接，第二、三層節(jié)點(diǎn)通過(guò)車輛路徑或者自助點(diǎn)服務(wù)進(jìn)行連接，配送中心整理整個(gè)區(qū)域的訂單并通過(guò)卡車進(jìn)行物品轉(zhuǎn)運(yùn)，將貨物運(yùn)輸至各配送點(diǎn)和自助點(diǎn)同時(shí)進(jìn)行回收，這是在一級(jí)路徑上進(jìn)行的。商品到達(dá)配送點(diǎn)后，物品通過(guò)配送車送至客戶點(diǎn)，到達(dá)自助點(diǎn)后，由客戶自取，同時(shí)進(jìn)行回收，這則是通過(guò)二級(jí)路徑和自助點(diǎn)服務(wù)來(lái)實(shí)現(xiàn)。圖1為二級(jí)選址路徑示意圖。

圖1 服務(wù)差異下二級(jí)選址-路徑示意圖Fig.1 Solution for 2E-LRP under different service mode

本文考慮了兩類客戶所需的不同物流服務(wù)，分別是通過(guò)配送點(diǎn)和自助點(diǎn)來(lái)實(shí)現(xiàn)的，配送需求型客戶的服務(wù)過(guò)程是配送員到達(dá)客戶點(diǎn)后進(jìn)行取送貨，而自取型客戶的服務(wù)過(guò)程是客戶自行到達(dá)附近的自助點(diǎn)進(jìn)行物品的存取，按照客戶點(diǎn)的需求分類還可將客戶點(diǎn)分為三類，取貨需求、送貨需求、取送貨雙重需求，這三種類型的需求都可以通過(guò)配送點(diǎn)或自助點(diǎn)進(jìn)行實(shí)現(xiàn)，文章后面部分將會(huì)以“二級(jí)設(shè)施”來(lái)指代配送點(diǎn)和自助點(diǎn)。

為了構(gòu)建該配送網(wǎng)絡(luò)，需要進(jìn)行三種決策。（1）對(duì)二級(jí)設(shè)施的選址決策：在已有的配送點(diǎn)和自助點(diǎn)集合中，確定提供配送服務(wù)的配送點(diǎn)的數(shù)量和位置，確定開放的自助點(diǎn)的數(shù)量和位置。（2）客戶分配決策：決定開放的二級(jí)設(shè)施為哪些客戶進(jìn)行服務(wù)，一位客戶只能被分配到一個(gè)配送點(diǎn)或自助點(diǎn)。（3）路徑?jīng)Q策：確定一級(jí)路徑上卡車訪問(wèn)二級(jí)設(shè)施的順序，以及二級(jí)路徑上配送車訪問(wèn)客戶點(diǎn)的順序。為了更好地界定問(wèn)題，本文進(jìn)行了下述假設(shè)：

（1）配送中心的數(shù)量是唯一的，且其位置已知，其運(yùn)輸能力足夠大，不考慮車輛限制。（2）全部配送點(diǎn)和自助點(diǎn)的位置、待回收量已知，且各配送點(diǎn)擁有的配送車量的數(shù)量和類型已知，各自助點(diǎn)的容量已知。（3）各客戶點(diǎn)的需求量和待回收量、位置已知。（4）所有物品從配送中心開始配送。（5）客戶點(diǎn)、配送點(diǎn)、自助點(diǎn)的需求量不可分。（6）備選配送點(diǎn)和自助點(diǎn)的數(shù)目、位置已知，但是否開放需要在求解后確定。（7）物品的配送和回收始終需要經(jīng)過(guò)配送點(diǎn)或自助點(diǎn)轉(zhuǎn)運(yùn)。（8）一級(jí)路徑只能使用卡車運(yùn)輸，二級(jí)路徑表示使用配送車進(jìn)行取送貨，配送車分為大型配送車和小型配送車兩類，二者區(qū)別于最大載重限制。（9）一級(jí)路徑必須始于配送中心最后再返回配送中心。二級(jí)車輛路徑，必須始于配送點(diǎn)，最后再返回同一配送點(diǎn)。（10）選擇自助點(diǎn)進(jìn)行服務(wù)的客戶，其自行的取送貨操作對(duì)于一級(jí)路徑的車輛而言是及時(shí)的。（11）在以下情況下客戶點(diǎn)只能接受配送服務(wù)，一是客戶點(diǎn)位于待開放自助點(diǎn)的服務(wù)范圍之外，二是可以為該客戶點(diǎn)通過(guò)服務(wù)的自助點(diǎn)已到達(dá)容量上限。（12）每個(gè)客戶點(diǎn)只能選擇一種服務(wù)。

1.2 定義變量

同時(shí)取送貨網(wǎng)絡(luò)G=(V,E)，其中V為所有節(jié)點(diǎn)的集合，其由J（可選配送點(diǎn)集合）、L（可選的自助點(diǎn)集合）、客戶點(diǎn)I和總倉(cāng)庫(kù)o構(gòu)成，其中I={I1,I2}，I1表示配送需求型客戶，I2表示自取需求型客戶，E:={(vi,vj):vi,vj∈V,vi≠vj}表示連接各節(jié)點(diǎn)的弧的集合，E1:={(i,j)∈E|i,j?I}表示一級(jí)運(yùn)輸路徑的弧集，E2:=EE1表示二級(jí)配送路徑的弧集。H、h、Hh都表示車輛集合的映射關(guān)系，對(duì)于各配送點(diǎn)j而言，映射H(j)表示其擁有的大型配送車集合，h(j)表示其擁有的小型配送車集合，Hh(J)表示全部配送車輛集合，H(o)表示總倉(cāng)庫(kù)可以使用的卡車集合。具體變量解釋如下。

1.3 數(shù)學(xué)模型

以上模型中，（1）表示最小化總成本，（2）至（5）分別表示各部分成本，（2）表示一、二級(jí)車輛固定成本，（3）表示一、二級(jí)配送網(wǎng)絡(luò)的運(yùn)輸成本，（4）表示自助點(diǎn)與自助型客戶的連接成本，（5）表示二級(jí)設(shè)施開放成本。（6）、（7）限制了每個(gè)配送點(diǎn)使用的配送車的數(shù)量，（8）、（9）分別表示每個(gè)配送型客戶和配送點(diǎn)的流量守恒約束，（10）、（11）分別保證每輛卡車和配送車的路徑起點(diǎn)和終點(diǎn)為同節(jié)點(diǎn)，并且每輛卡車或配送車只能出車一次，（12）表示當(dāng)二級(jí)設(shè)施被卡車訪問(wèn)時(shí)才能開放，（13）至（15）共同保證一位配送型客戶只能被一個(gè)配送點(diǎn)服務(wù)，一位自取型客戶只能被一個(gè)自助點(diǎn)服務(wù)，（16）至（21）表示對(duì)于一級(jí)路徑上運(yùn)輸能力的約束，其中（16）表示卡車訪問(wèn)某二級(jí)設(shè)施前后載重量的變化，（17）表示所有卡車從總倉(cāng)庫(kù)出發(fā)時(shí)的總載重量為所有客戶的需求量，（18）、（19）表示運(yùn)輸過(guò)程的連續(xù)性，即卡車在運(yùn)輸過(guò)程中載重量不變，（20）表示每一輛卡車離開總倉(cāng)庫(kù)時(shí)的載重量等于其所訪問(wèn)的所有二級(jí)設(shè)施所服務(wù)客戶點(diǎn)的需求量，（21）保證卡車在運(yùn)輸過(guò)程中的載重量始終不超過(guò)最大載重量，（22）至（29）表示對(duì)于二級(jí)路徑上運(yùn)輸能力的約束，其中（22）表示配送車訪問(wèn)一位配送型客戶前后載重量的變化，（23）保證每個(gè)配送點(diǎn)都需要滿足其所服務(wù)的客戶點(diǎn)的總需求量，（24）、（25）表示配送過(guò)程的連續(xù)性，（26）、（27）表示每輛配送車從配送點(diǎn)出發(fā)時(shí)的載重量等于該車輛所訪問(wèn)的配送型客戶點(diǎn)的總需求量，（28）、（29）保證配送車在配送過(guò)程中的載重量始終不超過(guò)最大載重量，（30）表示只有在自助點(diǎn)服務(wù)范圍內(nèi)的自取型客戶才能被自助點(diǎn)服務(wù)，（31）、（32）保證自助點(diǎn)存儲(chǔ)的物件量始終不超過(guò)其容量。

2 算法設(shè)計(jì)

ALNS（自適應(yīng)大鄰域搜索算法）是指在迭代過(guò)程中，不斷地使用多種破壞和修復(fù)算子來(lái)改進(jìn)解的質(zhì)量。其中破壞算子會(huì)對(duì)解進(jìn)行一定程度的破壞，修復(fù)算子則對(duì)破壞后的解進(jìn)行修復(fù)，通過(guò)這兩種算子復(fù)雜的共同作用，對(duì)當(dāng)前解的鄰域（破壞、修復(fù)算子對(duì)對(duì)當(dāng)前解進(jìn)行操作后得到的解集）進(jìn)行搜索，尋找更高質(zhì)量的解，并在迭代一定次數(shù)后更新破壞、修復(fù)算子對(duì)的權(quán)重，使得表現(xiàn)良好的算子對(duì)有更高的概率被選擇。圖2為本文設(shè)計(jì)ALNS算法的具體流程：

圖2 ALNS算法流程圖Fig.2 Flowchart of ALNS heuristic algorithm

步驟1初始化各種參數(shù)，置迭代次數(shù)Nc為0，并生成初始解。

步驟2判斷是否達(dá)到終止條件。若達(dá)到則結(jié)束算法，輸出目前最優(yōu)解。

步驟3依據(jù)“輪盤賭”原則確定本次迭代采用的算子對(duì)，然后對(duì)當(dāng)前解進(jìn)行破壞和修復(fù)操作。

步驟4對(duì)新得到的解進(jìn)行評(píng)價(jià)，通過(guò)Metropolis準(zhǔn)則以一定概率接受新解，若未被接受則轉(zhuǎn)至步驟7。

步驟5對(duì)接受的解進(jìn)行局部搜索。

步驟6若新的當(dāng)前解對(duì)應(yīng)目標(biāo)值優(yōu)于目前的最優(yōu)解則更新目前最優(yōu)解和局部最優(yōu)解，否則僅更新局部最優(yōu)解。

步驟7判斷是否達(dá)到規(guī)定更新權(quán)重的迭代次數(shù)，若達(dá)到，則更新算子對(duì)權(quán)重，并將算子對(duì)的調(diào)用次數(shù)和累計(jì)得分清零。

步驟8判斷最優(yōu)解是否連續(xù)Ncreset次迭代后仍未更新，若是，則將當(dāng)前解置為目前最優(yōu)解。

步驟9Nc=Nc+1，轉(zhuǎn)步驟2。

本文研究的問(wèn)題以2E-LRPSPD（考慮同時(shí)取送貨的二級(jí)選址-路徑問(wèn)題）為基礎(chǔ)，該種問(wèn)題求解極為復(fù)雜，屬于NP-hard問(wèn)題，一般采用啟發(fā)式算法進(jìn)行求解。在已有的相關(guān)文獻(xiàn)[7-9]中，通過(guò)實(shí)驗(yàn)驗(yàn)證了ALNS對(duì)此類問(wèn)題有良好的求解效果。接下來(lái)將會(huì)討論算法的初始化策略、自適應(yīng)權(quán)重、解的接受條件、各種破壞和修復(fù)算子、算子對(duì)的選擇與更新策略以及局部搜索算子。

2.1 初始化策略

在本文設(shè)計(jì)的ALNS算法中，首先根據(jù)貪婪思想在滿足載重約束的條件下生成初始解，貪婪初始化算法步驟如下：

步驟1選擇距離配送點(diǎn)最近的客戶，將其插入該配送點(diǎn)的配送路徑中，構(gòu)建路徑(j,i,j)為當(dāng)前配送路徑，其中j為配送點(diǎn)，更新待插入客戶集合。

步驟2當(dāng)前配送路徑下，依次遍歷每位待插入客戶的每一個(gè)插入位置，并計(jì)算出該客戶的最佳插入位置和對(duì)應(yīng)的最小插入成本，按照每個(gè)待插入客戶點(diǎn)的最小插入成本將客戶升序排序。ck=dik+dkj-dij表示待插入客戶k在當(dāng)前二級(jí)路徑上的節(jié)點(diǎn)(i,j)之間進(jìn)行插入的成本。

步驟3從排序最靠前的待插入客戶開始，嘗試將其插入至當(dāng)前路徑的最佳插入位置中，插入后若新路徑違背載重限制，則將其刪除后繼續(xù)嘗試下一位待插入客戶，直到能夠有一位客戶完成插入。若始終無(wú)客戶可插入，則轉(zhuǎn)至步驟5。

步驟4更新待插入客戶集合和當(dāng)前配送路徑，判斷待插入客戶集合是否為空，若是空集，則轉(zhuǎn)至步驟6，若不是，則轉(zhuǎn)至步驟2。

步驟5在待插入客戶集合中選擇距離配送點(diǎn)最近的客戶，同時(shí)按照各配送點(diǎn)與該客戶點(diǎn)的距離為指標(biāo)將各配送點(diǎn)進(jìn)行升序排序。從排名最前的配送點(diǎn)開始，依次檢查配送點(diǎn)是否存在閑余的配送車能夠進(jìn)行配送，若存在，則構(gòu)造一條新路徑，然后更新當(dāng)前路徑和待插入客戶集合，再轉(zhuǎn)至步驟2。

步驟6定義可以為自取需求型客戶i提供服務(wù)的自助點(diǎn)集合U(i)，以客戶點(diǎn)與U(i)中最近自助點(diǎn)的距離為指標(biāo)將客戶點(diǎn)進(jìn)行升序排序，按此順序依次安置客戶。

步驟7依次遍歷客戶點(diǎn)，依次安排U中距離較短的自助點(diǎn)對(duì)其進(jìn)行服務(wù)，若滿足容量約束，則將該客戶點(diǎn)安置到相應(yīng)自助點(diǎn)，直到遍歷完所有客戶點(diǎn)，算法結(jié)束。

2.2 自適應(yīng)權(quán)重

每進(jìn)行完一定的迭代次數(shù)?后，需要更新算子對(duì)的權(quán)重，整個(gè)迭代過(guò)程可以據(jù)此被劃分為幾個(gè)階段。依據(jù)該算子對(duì)的調(diào)用次數(shù)ldr以及在前一階段累計(jì)的分?jǐn)?shù)scdr更新權(quán)重。在第一階段每個(gè)算子對(duì)的權(quán)重都設(shè)為1，且每次更新完權(quán)重后，將ldr和sdr清零。

破壞、修復(fù)算子對(duì)(d,r)對(duì)應(yīng)的累計(jì)分?jǐn)?shù)scdr的累計(jì)方式根據(jù)該算子對(duì)在上一階段中的表現(xiàn)情況而定，具體而言，當(dāng)采用該算子對(duì)進(jìn)行迭代后，得到的解對(duì)全局最優(yōu)解進(jìn)行更新，對(duì)scdr累加σ1；當(dāng)?shù)玫降慕鈱?duì)局部最優(yōu)解進(jìn)行更新，則對(duì)scdr累加σ2；當(dāng)?shù)玫降慕獗染植孔顑?yōu)解差，但是仍被接受，則對(duì)sdr累加σ3，累加分?jǐn)?shù)的大小滿足σ1＞σ2＞σ3≥0。

更新算子對(duì)(d,r)對(duì)應(yīng)權(quán)重wdr的具體方式如下，其中ρ∈[0,1]為衡量算子對(duì)表現(xiàn)情況和其更新前權(quán)重的重要度因子，當(dāng)其值取0時(shí)，算子對(duì)的權(quán)重會(huì)一直在初始水平保持不變，當(dāng)其值取1時(shí)，算子對(duì)的權(quán)重更新僅依賴于其上一階段的表現(xiàn)，所以取0＜ρ＜1才能同時(shí)對(duì)兩方面進(jìn)行考慮。

2.3 退火條件

當(dāng)尋找到一個(gè)新解時(shí)，需要判斷其是否被接受，若該解優(yōu)于局部最優(yōu)解，則接受該解，否則按照下面這個(gè)準(zhǔn)則進(jìn)行判斷：以概率p=(exp(F(s)-F(s′))/T)接受較劣解，其中F(s′)是較差新解對(duì)應(yīng)的目標(biāo)值。這種依概率接受較劣解的方法與模擬退火中的Metropolis準(zhǔn)則相同，其中初始溫度[17]設(shè)置為，設(shè)置φ1=0.03，φ2=0.5。降溫過(guò)程為

2.4 相關(guān)算子設(shè)計(jì)

2.4.1 破壞算子

在算法迭代過(guò)程中，首先需要對(duì)當(dāng)前解進(jìn)行“破壞”操作，即從現(xiàn)有解中移除q個(gè)單位的客戶。一般的做法是，對(duì)當(dāng)前已經(jīng)被安置到二級(jí)設(shè)施的客戶，計(jì)算出一種特別的排序指標(biāo)，對(duì)這些客戶進(jìn)行排序，最后根據(jù)排序依次將客戶移除至集合R中，直到移除了q位客戶為止。下面所稱的“客戶”若無(wú)特別說(shuō)明則指代全部客戶。以下是算法中采用的七種破壞算子。

RaR：該算子隨機(jī)指定客戶進(jìn)行移除操作，這種破壞算子由于沒(méi)有借助任何信息，所以往往產(chǎn)生一組不太好的被移除客戶，但是這種隨機(jī)移除的方法有助于搜索到多樣化的解并脫離局部最優(yōu)。

RDR：首先隨機(jī)地產(chǎn)生一位待移除客戶，然后計(jì)算其余客戶與該客戶的關(guān)聯(lián)度指標(biāo)，關(guān)聯(lián)度考慮的是兩客戶點(diǎn)之間的距離的接近程度dij。

WCR：該破壞算子移除對(duì)于整個(gè)目標(biāo)值影響最大的那些客戶點(diǎn)，并希望能夠找到更好的插入位置，進(jìn)行移除操作所依據(jù)的指標(biāo)是“對(duì)目標(biāo)值的貢獻(xiàn)度”，計(jì)算式為Jk=F(s)-F(s-k)，其中s-k為去除客戶k后的解。

RoR：任意選擇一條配送路徑上的客戶進(jìn)行移除，直到移除q位客戶為止。

SBR：任意選擇一個(gè)二級(jí)設(shè)施，然后隨機(jī)地選擇該配送點(diǎn)提供服務(wù)的客戶進(jìn)行移除，直到移除q位客戶為止。

ARR：按照所有自取型客戶對(duì)應(yīng)的(|U|-1)為指標(biāo)，采用“輪盤賭”原則選擇客戶點(diǎn)進(jìn)行移除，直到移除q位客戶為止。

SPR[16]：隨機(jī)地選擇兩個(gè)同類型的二級(jí)設(shè)施，隨機(jī)移除兩個(gè)設(shè)施之間矩形區(qū)域內(nèi)的同一類型客戶點(diǎn)，直到達(dá)到規(guī)定數(shù)量為止。

2.4.2 修復(fù)算子

修復(fù)算子根據(jù)被移除的客戶集合R以及被破壞后的解進(jìn)行修復(fù)操作，在客戶點(diǎn)插入后均需檢查是否滿足約束。以下是算法中采用的五種修復(fù)算子。

RGI：隨機(jī)生成待插入客戶順序，依次對(duì)客戶進(jìn)行下述操作，對(duì)于客戶點(diǎn)k，遍歷每一個(gè)可行的插入位置，并計(jì)算出插入成本，選擇插入成本最小的位置進(jìn)行插入，插入成本主要考慮插入后所增加的配送距離或者連接成本，下面為計(jì)算配送需求型客戶插入成本的方法，其中i和j是進(jìn)行插入前相鄰的兩個(gè)節(jié)點(diǎn)，u(i,k,j)表示客戶點(diǎn)k插入i和j之間產(chǎn)生的插入成本。

對(duì)于自取型需求客戶，則按照下式選擇自助點(diǎn)。

BGI：遍歷每一位待插入客戶，計(jì)算出其最佳插入位置和對(duì)應(yīng)的最小插入成本，然后選擇所有客戶中插入成本最小的客戶以及插入位置，進(jìn)行插入操作。計(jì)算式如下：

對(duì)于自取型需求客戶，則按照下式選擇自助點(diǎn)。

NGI：在RGI計(jì)算插入成本的基礎(chǔ)上乘以干擾因子τ得到新的插入成本，干擾因子的取值為區(qū)間[1-λ,1+λ]內(nèi)服從均勻分布的隨機(jī)數(shù)，設(shè)置λ=0.25。

RaI：隨機(jī)插入，只要插入后的解滿足約束即可進(jìn)行插入。

BRI：后悔插入，首先按照后悔值指標(biāo)對(duì)待插入客戶進(jìn)行排序，然后依次將客戶插入至最佳可行位置。對(duì)于配送需求型客戶，后悔值的計(jì)算式為uk=dk2j-dk1i，其中dk1i是待插入客戶點(diǎn)距離未被移除客戶點(diǎn)的最小距離，dk2j是次小距離。對(duì)于自取需求型客戶而言，uk=+(1-yj)CPj-lk1i-(1-yi)CPi，其中i為使得插入成本最小的自助點(diǎn)，j為使得成本第二小的自助點(diǎn)。按照后悔值不減的順序依次進(jìn)插入客戶，對(duì)于配送需求型客戶，首先找到距離該待插入客戶最近的未被移除的客戶點(diǎn)，選擇此客戶點(diǎn)左右位置中使得目標(biāo)值增加較小的位置進(jìn)行插入，若都不可行則選擇距離次近的未被移除的客戶點(diǎn)，選擇其左右位置嘗試插入，直到該待插入客戶點(diǎn)安置完畢若始終無(wú)法插入則開啟一條新的配送路徑，將客戶點(diǎn)安置其中。對(duì)于自取需求型客戶，在符合容量約束的前提下，選擇使得插入成本最小的自助點(diǎn)。

2.4.3 選擇破壞/修復(fù)算子對(duì)

在算法迭代過(guò)程中，有多種破壞和修復(fù)算子的組合對(duì)可以選擇，本文采用輪盤賭的原理進(jìn)行算子對(duì)的選擇，具體做法是先依據(jù)不同算子對(duì)在過(guò)去的表現(xiàn)情況賦予其不同的權(quán)重，然后在此權(quán)重下根據(jù)輪盤賭法則進(jìn)行選擇。一般而言，一個(gè)算子對(duì)在過(guò)去的表現(xiàn)情況越好，其對(duì)應(yīng)權(quán)重也就越大。對(duì)于選擇某一個(gè)算子對(duì)的概率pdr，其計(jì)算式為：

2.4.4 局部搜索算子

如果當(dāng)前解滿足接受條件，就會(huì)對(duì)當(dāng)前解進(jìn)行局部搜索，每進(jìn)行一次局部搜索都會(huì)依次嘗試五種算子，順序是Inter_2-opt、Inter_swap、Inter_0-1exchange、Intra_swap、Intra_shift。前三種算子是徑內(nèi)搜索，后兩種是徑間搜索，只有當(dāng)改變后解的目標(biāo)值優(yōu)于當(dāng)前解的目標(biāo)值時(shí)，才會(huì)將當(dāng)前解替換。采用局部搜索時(shí)，首先是對(duì)二級(jí)路徑進(jìn)行優(yōu)化，而后對(duì)一級(jí)路徑進(jìn)行優(yōu)化。Inter_2-opt[18]的操作是隨機(jī)選擇路徑（一級(jí)路徑或二級(jí)路徑），然后隨機(jī)選擇路徑上的兩節(jié)點(diǎn)，對(duì)包括兩節(jié)點(diǎn)在內(nèi)以及兩節(jié)點(diǎn)之間的所有節(jié)點(diǎn)進(jìn)行逆序操作。Inter_swap的操作是隨機(jī)選擇路徑上兩節(jié)點(diǎn)進(jìn)行交換。Inter_0-1exchange的操作是隨機(jī)選擇一個(gè)節(jié)點(diǎn)插入到該路徑上的其他位置。Intra_swap的操作是交換兩個(gè)路徑上的兩個(gè)節(jié)點(diǎn)。Intra_shift的操作是將一條路徑上的一個(gè)節(jié)點(diǎn)插入到另一條路徑上。

3 基準(zhǔn)案例分析

本章首先說(shuō)明ALNS算法的參數(shù)設(shè)置，而后為驗(yàn)證算法的性能，對(duì)經(jīng)典2E-LRP案例——Nguyen數(shù)據(jù)集進(jìn)行求解，然后將結(jié)果同另外三種算法以及BKS（best known solution）進(jìn)行對(duì)比。接下來(lái)選擇兩個(gè)基準(zhǔn)案例進(jìn)行算法收斂性分析。最后介紹模擬數(shù)據(jù)集并進(jìn)行結(jié)果分析。實(shí)驗(yàn)計(jì)算機(jī)的配置為2.60 GHz Intel Core i5-7300U處理器，編程環(huán)境編寫為Matlab2019a，操作系統(tǒng)為Windows 10 64位。

3.1 算法參數(shù)設(shè)置

本文設(shè)計(jì)的ALNS算法主要涉及的參數(shù)除了在第2章中提到的外，還包括最大迭代次數(shù)Ncmax，權(quán)重因子ρ，兩次更新算子對(duì)權(quán)重的間隔迭代次數(shù)?，破壞算子移除客戶數(shù)量服從離散均勻分布，并設(shè)定在連續(xù)迭代Ncreset次后若仍未更新最優(yōu)解，則重新從目前找到的最優(yōu)解處開始搜索。通過(guò)進(jìn)行一定的算法測(cè)試和文獻(xiàn)參考[9，17]，算法參數(shù)設(shè)置如表1所示。

表1 算法參數(shù)Table 1 ALNS heuristic parameter tuning

3.2 算法對(duì)比分析

為了進(jìn)一步驗(yàn)證算法的有效性，采用參考文獻(xiàn)[6]中使用的Nguyen算例，該算例是2E-LRP問(wèn)題的國(guó)際通用算例，包含24個(gè)測(cè)試算例，每個(gè)算例均有1個(gè)配送中心，有5個(gè)或10個(gè)中轉(zhuǎn)配送點(diǎn)，25至200個(gè)客戶點(diǎn)，算例可以表示為n-m{N,MN}，n表示客戶點(diǎn)數(shù)，m表示配送點(diǎn)數(shù)，N表示客戶點(diǎn)呈正態(tài)分布，MN表示客戶點(diǎn)呈高維正態(tài)分布，該算例的物流成本由運(yùn)輸成本、車輛固定成本、二級(jí)設(shè)施開放成本組成。本文選取客點(diǎn)為{25，50}的測(cè)試算例，通過(guò)ALNS對(duì)每個(gè)算例進(jìn)行5次求解，記錄求得的最優(yōu)解和目標(biāo)值，并將求解結(jié)果與BKS[5]、GRASP-LP算法[5]、GRASP-LP-PR算法[6]、H4+VND2算法[6]做比較，結(jié)果如表2所示。

表2 不同算法求解Nguyen數(shù)據(jù)集的結(jié)果Table 2 Results comparisons for Nguyen instances

本文設(shè)計(jì)的ALNS算法在客戶規(guī)模為25的算例中更新了1個(gè)算例的目前最優(yōu)解，其余和最優(yōu)解相同，在客戶規(guī)模為50的算例中，均接近或達(dá)到最優(yōu)解。采用Gap值（由算法求解結(jié)果與BKS的差距除以BKS得到）衡量算法求解結(jié)果。所有算例求解的平均Gap值為1.22%，可見對(duì)于小規(guī)?？蛻舻乃憷撍惴軌虻玫捷^好的求解結(jié)果，算法性能明顯優(yōu)于GRASP-LP（Gap均值為1.75%）和H4+VND2（Gap均值為5.67%）算法，由此可以證明ALNS算法解決2E-LRP的有效性。

3.3 算法收斂性分析

為進(jìn)一步驗(yàn)證ALNS算法求解2E-LRP問(wèn)題的有效性，確保算法的求解結(jié)果可以收斂到較好水平，選取Nguyen數(shù)據(jù)集中的50-5Nb、50-10Nb兩個(gè)算例進(jìn)行求解并記錄每次迭代的目標(biāo)值繪制出迭代圖以驗(yàn)證算法收斂性能。

從圖3可以看出目標(biāo)值在100代以內(nèi)迅速下降，在200～300代的迭代過(guò)程中緩慢下降，50-5Nb算例在250代附近收斂于最優(yōu)結(jié)果，而50-10Nb算例在500～750代中仍有緩慢下降的趨勢(shì)，在750代左右收斂至最優(yōu)結(jié)果，這是由于50-10Nb算例的解空間更大。

圖3 兩個(gè)基準(zhǔn)案例收斂曲線Fig.3 Convergence curves of two classic instances

4 實(shí)際案例模擬

4.1 模擬數(shù)據(jù)

本文設(shè)計(jì)的案例有1個(gè)配送中心、5個(gè)待開放配送點(diǎn)、10個(gè)待開放自助點(diǎn)、75位客戶，其中含50位配送需求型客戶和25位自取需求型客戶，由于版面限制，表3只列出15位客戶的相關(guān)信息，其中“配送需求型”客戶的客戶類型為1，“自取需求型”的客戶類型為0。配送中心和二級(jí)設(shè)施的信息如表4所示。

表3 部分客戶信息表Table 3 Information sheet for some customers

表4 物流設(shè)施信息表Table 4 Information sheet for logistics facilities

本案例中包括的模型參數(shù)通過(guò)參考實(shí)際資料和相關(guān)文獻(xiàn)[5-7，9，18]來(lái)進(jìn)行設(shè)計(jì)。其中客戶點(diǎn)的坐標(biāo)位置呈二維正態(tài)分布，需求量和待回收量呈正態(tài)分布，考慮到在實(shí)際情況下存在待回收量的客戶數(shù)量要少于存在需求量的客戶數(shù)量，故案例中存在待回收量的客戶數(shù)量占客戶總數(shù)的53.3%。

考慮到物流服務(wù)的便利性，配送點(diǎn)和自助點(diǎn)這類二級(jí)設(shè)施一般設(shè)置在靠近客戶點(diǎn)處。本案例中的一級(jí)物流設(shè)施是配送中心，數(shù)量為1，且位置已知，一級(jí)路徑配送車輛無(wú)數(shù)量限制。每個(gè)二級(jí)設(shè)施對(duì)應(yīng)不同的開放成本和待回收量，其中每個(gè)配送點(diǎn)的可調(diào)用配送車數(shù)量如表4最后一列所示，斜杠左側(cè)表示可調(diào)用小型配送車數(shù)量，右側(cè)表示可調(diào)用大型配送車數(shù)量。

其余模型參數(shù)設(shè)置如下：一級(jí)車輛容量是600 kg，二級(jí)車輛中，小型配送車容量是30 kg，大型配送車容量是50 kg，一級(jí)車輛的固定成本是100元，小型配送車為20元，大型配送車為40元，車輛每千米運(yùn)輸費(fèi)用是1元。自助點(diǎn)的容量上限均為40 kg，服務(wù)范圍半徑均為2 km，每千米的連接成本為0.5元。

4.2 模型結(jié)果分析

基于以上數(shù)據(jù)，運(yùn)行ALNS算法10次，最優(yōu)的求解結(jié)果如下，其中0代表配送中心，負(fù)數(shù)代表二級(jí)設(shè)施，-1至-5依次代表1號(hào)至5號(hào)配送點(diǎn)，-6至-15依次代表1號(hào)至10號(hào)自助點(diǎn)。

選址決策：配送點(diǎn)-1，-4，自助點(diǎn)-7，-8，-10，-11，-12，-13

一級(jí)路徑：

0?-6?-2?-10?-13?-14?-12?-4?-11?-8?-1?-7?0

二級(jí)路徑：

-1?3?46?31?35?6?11?10?34?-1（大型配送車）

-1?47?2?20?5?50?-1（小型配送車）

-1?26?28?44?7?29?40?27?36?12?4?9?-1（大型配送車）

-4?23?18?16?42?19?15?8?14?21?49?37?48?-4（大型配送車）

-4?39?24?17?45?22?1?32?38?-4（大型配送車）

-4?25?30?33?13?41?43?-4（小型配送車）

自助點(diǎn)服務(wù)：

2號(hào)自助點(diǎn)（-7）：51，54，58，61，68，69

3號(hào)自助點(diǎn)（-8）：57，60，62，74

5號(hào)自助點(diǎn)（-10）：53，55，56，59，63，65，71，75

6號(hào)自助點(diǎn)（-11）：52，70，72

7號(hào)自助點(diǎn)（-12）：66，67

8號(hào)自助點(diǎn)（-13）：64，73

由此可知，物流總成本1 693.89元，包括車輛固定成本300.00元，運(yùn)輸成本115.72元，連接成本28.17元，開放成本1 250.00元。

從結(jié)果可以看出，只開放2個(gè)配送點(diǎn)，但一級(jí)車輛訪問(wèn)了3個(gè)配送點(diǎn)，這是由于部分配送點(diǎn)存在待回收量而不提供服務(wù)，自助點(diǎn)同理。共調(diào)用6輛配送車，而其余3個(gè)配送點(diǎn)的配送車均為閑置狀態(tài)，開放配送點(diǎn)配送車的使用率均達(dá)100%。開放6個(gè)自助點(diǎn)，但自助點(diǎn)的服務(wù)客戶數(shù)量差距較大，有的自助點(diǎn)服務(wù)8位客戶，接近容量上限，而有的自助點(diǎn)只服務(wù)2位客戶，還有較多的剩余容量，這是由于自助點(diǎn)的位置不同，在客戶點(diǎn)密集處的自助點(diǎn)往往有較大服務(wù)率，因此應(yīng)該在這些自助點(diǎn)附近增設(shè)一些自助點(diǎn)，而服務(wù)客戶少的自助點(diǎn)往往位于客戶點(diǎn)疏散的區(qū)域，若配送點(diǎn)離該區(qū)域較遠(yuǎn)，可以考慮設(shè)置自助點(diǎn)來(lái)對(duì)該區(qū)域客戶進(jìn)行服務(wù)，以縮短配送距離。

表5對(duì)比了“單一配送服務(wù)模式”和“存在服務(wù)差異的配送模式”的各項(xiàng)成本，前者的結(jié)果是將自取需求型客戶轉(zhuǎn)化成配送需求型客戶后，運(yùn)行算法5次所得到的最優(yōu)結(jié)果。可以看出前者的總成本比后者高出10%左右，其中運(yùn)輸成本增幅最大達(dá)43%，車輛固定成本增長(zhǎng)約33%，開放成本增長(zhǎng)約4%，可見提供差異化的客戶服務(wù)可以有效減少運(yùn)輸成本和車輛固定成本，從而降低總物流成本。

表5 兩種服務(wù)模式的比較Table 5 Comparison of two service modes

總的來(lái)說(shuō)，通過(guò)不同的服務(wù)方式滿足客戶取送貨需求的配送模式不僅有利于減少配送路徑的距離和使用的配送車數(shù)量進(jìn)而降低成本，還有助于減少規(guī)劃配送路徑的時(shí)間和難度的同時(shí)滿足客戶不同的服務(wù)需求。

4.3 模型靈敏度分析

為了考察模型參數(shù)對(duì)求解結(jié)果的影響，選擇重要參數(shù)小/大型配送車載重量Q1/Q2，客戶需求量d，自助點(diǎn)容量上限CZ，自助點(diǎn)服務(wù)半徑r，進(jìn)行靈敏度分析。以4.1節(jié)設(shè)置的模型參數(shù)為基準(zhǔn)值，將Q1/Q2、d、CZ、r的基準(zhǔn)值依次增加+10%、+5%、0%，-5%、-10%，某一參數(shù)改變時(shí)，其余參數(shù)則保持在基準(zhǔn)值不變，每次模型參數(shù)變化，運(yùn)行算法5次，記錄平均求解結(jié)果和標(biāo)準(zhǔn)差，結(jié)果如表6所示。

表6 模型參數(shù)靈敏度分析Table 6 Sensitivity analysis of model parameters

配送車輛載重Q1/Q2與物流總成本呈現(xiàn)負(fù)相關(guān)，即車輛載重限制越大，則物流成本越小，且模型結(jié)果對(duì)該參數(shù)取值較為敏感。在滿足所有客戶點(diǎn)的需求的前提下，客戶需求與物流成本同樣呈正相關(guān)，總成本對(duì)該參數(shù)較為敏感。自助點(diǎn)的容量CZ和服務(wù)半徑r與總成本呈負(fù)相關(guān)，當(dāng)自助點(diǎn)的容量增加10%時(shí)，成本會(huì)有明顯的下降，服務(wù)半徑增大時(shí)，物流成本的波動(dòng)性會(huì)有明顯的增大。因此，決策者可以考慮增加自助點(diǎn)的容量、服務(wù)范圍，或者提高配送車量的載重上限，進(jìn)而減少總物流成本。

4.4 實(shí)際案例算法對(duì)比

為進(jìn)一步驗(yàn)證自適應(yīng)大鄰域算法的有效性，依次采用基本遺傳算法、蟻群算法、粒子群算法對(duì)實(shí)際案例進(jìn)行求解，每種算法運(yùn)行10次，記錄每次運(yùn)行的結(jié)果，得到平均求解結(jié)果和最佳求解結(jié)果，再計(jì)算每種算法最佳結(jié)果與ALNS算法最佳結(jié)果的Gap值。

從表7可以看出，ALNS對(duì)案例的求解結(jié)果優(yōu)于三種基本經(jīng)典啟發(fā)式算法，其中GA與ALNS算法的最佳結(jié)果最為接近，二者的總成本相差4.99%，而后是ACO（總成本相差6.35%），最后是PSO（總成本相差8.76%）。因此，本文設(shè)計(jì)的ALNS算法求解服務(wù)差異下的二級(jí)選址-路徑問(wèn)題有良好效果。

表7 三種經(jīng)典算法與ALNS的對(duì)比Table 7 Comparison between three classical algorithms and ALNS

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

本文研究了在客戶存在不同服務(wù)需求的情況下的二級(jí)選址-路徑問(wèn)題，將客戶分為配送需求型和自取需求型兩類，通過(guò)開放配送點(diǎn)和自助點(diǎn)兩種二級(jí)物流設(shè)施來(lái)滿足不同客戶的取送貨需求。進(jìn)而根據(jù)問(wèn)題設(shè)計(jì)了一種有效的自適應(yīng)大鄰域算法，并使用2E-LRP的Nguyen算例進(jìn)行測(cè)試，與GRASP-LP、GRASP-LP-PR、H4+VND2算法所求結(jié)果進(jìn)行比較，并在25-5MN算例中更新了已知最優(yōu)解，而在其他算例中達(dá)到或接近最優(yōu)解。同時(shí)將ALNS與三種經(jīng)典啟發(fā)式算法進(jìn)行對(duì)比，驗(yàn)證了ALNS算法求解問(wèn)題的有效性。

本文研究為存在自取需求型客戶和配送需求型客戶的物流企業(yè)提供了理論模型和算法支持，保證有效地進(jìn)行二級(jí)設(shè)施選址決策和兩級(jí)路徑?jīng)Q策和自助點(diǎn)的服務(wù)決策，以達(dá)到降低物流成本和滿足客戶需求的目的。

下一步仍繼續(xù)對(duì)該配送模式進(jìn)行研究，考慮擁有雙重需求用戶的取貨、送貨需求由不同的二級(jí)設(shè)施進(jìn)行滿足的情況，并考慮不確定服務(wù)類型的客戶，通過(guò)算法求解得到合理的服務(wù)方式，還可以探究客戶接受某種服務(wù)的柔性，即可以以一定代價(jià)將客戶接受服務(wù)類型改變，以便近一步降低成本費(fèi)用。