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

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

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

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

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

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

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

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

1 問題描述及數(shù)學模型

1.1 問題描述

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

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

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

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

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

1.2 定義變量

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

1.3 數(shù)學模型

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

2 算法設計

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

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

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

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

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

步驟4對新得到的解進行評價，通過Metropolis準則以一定概率接受新解，若未被接受則轉(zhuǎn)至步驟7。

步驟5對接受的解進行局部搜索。

步驟6若新的當前解對應目標值優(yōu)于目前的最優(yōu)解則更新目前最優(yōu)解和局部最優(yōu)解，否則僅更新局部最優(yōu)解。

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

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

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

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

2.1 初始化策略

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

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

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

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

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

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

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

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

2.2 自適應權(quán)重

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

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

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

2.3 退火條件

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

2.4 相關(guān)算子設計

2.4.1 破壞算子

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

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

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

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

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

SBR：任意選擇一個二級設施，然后隨機地選擇該配送點提供服務的客戶進行移除，直到移除q位客戶為止。

ARR：按照所有自取型客戶對應的(|U|-1)為指標，采用“輪盤賭”原則選擇客戶點進行移除，直到移除q位客戶為止。

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

2.4.2 修復算子

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

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

對于自取型需求客戶，則按照下式選擇自助點。

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

對于自取型需求客戶，則按照下式選擇自助點。

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

RaI：隨機插入，只要插入后的解滿足約束即可進行插入。

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

2.4.3 選擇破壞/修復算子對

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

2.4.4 局部搜索算子

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

3 基準案例分析

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

3.1 算法參數(shù)設置

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

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

3.2 算法對比分析

為了進一步驗證算法的有效性，采用參考文獻[6]中使用的Nguyen算例，該算例是2E-LRP問題的國際通用算例，包含24個測試算例，每個算例均有1個配送中心，有5個或10個中轉(zhuǎn)配送點，25至200個客戶點，算例可以表示為n-m{N,MN}，n表示客戶點數(shù)，m表示配送點數(shù)，N表示客戶點呈正態(tài)分布，MN表示客戶點呈高維正態(tài)分布，該算例的物流成本由運輸成本、車輛固定成本、二級設施開放成本組成。本文選取客點為{25，50}的測試算例，通過ALNS對每個算例進行5次求解，記錄求得的最優(yōu)解和目標值，并將求解結(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

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

3.3 算法收斂性分析

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

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

圖3 兩個基準案例收斂曲線Fig.3 Convergence curves of two classic instances

4 實際案例模擬

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

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

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

表4 物流設施信息表Table 4 Information sheet for logistics facilities

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

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

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

4.2 模型結(jié)果分析

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

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

一級路徑：

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

二級路徑：

-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（小型配送車）

自助點服務：

2號自助點（-7）：51，54，58，61，68，69

3號自助點（-8）：57，60，62，74

5號自助點（-10）：53，55，56，59，63，65，71，75

6號自助點（-11）：52，70，72

7號自助點（-12）：66，67

8號自助點（-13）：64，73

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

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

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

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

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

4.3 模型靈敏度分析

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

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

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

4.4 實際案例算法對比

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

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

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

5 結(jié)束語

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

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

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