楊雪鍵 何玉潔 劉森 劉玲

摘要：針對包含一個物流中心、多個中轉(zhuǎn)站和多個終端零售客戶的D公司物流網(wǎng)絡(luò)布局，根據(jù)物流配送決策的實際過程，建立一個基于接駁點的干線-支線聯(lián)合優(yōu)化問題模型。干線為中轉(zhuǎn)站選址與物流中心到中轉(zhuǎn)站的運(yùn)輸；支線優(yōu)化表示所選中轉(zhuǎn)站的車輛分配、客戶選擇及配送路徑問題。文章首先采用貪婪算法構(gòu)建初始方案，再使用變鄰域搜索算法優(yōu)化初始方案，采用移除算子和交換算子等進(jìn)行鄰域擾動，形成使配送與運(yùn)輸決策更加合理的方案，有效提高了D公司的車輛利用率，降低運(yùn)輸成本，節(jié)省運(yùn)輸時間，提升整個運(yùn)輸環(huán)節(jié)的效率。

關(guān)鍵詞：物流網(wǎng)絡(luò)； 選址-路徑問題； 貪婪算法； 變鄰域搜索算法

中圖分類號：U116.2；TP18? 文獻(xiàn)標(biāo)識碼：A? ?文章編號：1674-0688（2023）03-0117-06

0 引言

2018年12月21日，國家發(fā)展和改革委員會和交通運(yùn)輸部發(fā)布《國家物流樞紐布局和建設(shè)規(guī)劃》，其中大理白族自治州成功入選國家物流樞紐承載城市，并布局建設(shè)商貿(mào)服務(wù)型國家物流樞紐。大理D物流公司緊抓政策機(jī)遇，以“構(gòu)建智慧物流”為核心，逐步實現(xiàn)物流作業(yè)數(shù)字化、業(yè)務(wù)智能化，在降本增效的同時，推進(jìn)商貿(mào)和物流資源的整合，優(yōu)化物流網(wǎng)絡(luò)布局，積極推進(jìn)“滇西區(qū)域物流中心”建設(shè)。經(jīng)過多年的發(fā)展，大理D物流公司已經(jīng)建立起較為完善的零售產(chǎn)品運(yùn)輸體系，但受人工調(diào)度的局限性，運(yùn)輸效率并不高，存在車輛資源利用不充分、車輛載荷不均衡或路線不合理等問題，需從管理模式變革出發(fā)，利用智能算法等手段構(gòu)建智能調(diào)度系統(tǒng)，較快、較好地實現(xiàn)區(qū)域化驅(qū)動資源，整合跨縣級配送，從“打破行政區(qū)劃，打破城鄉(xiāng)界限，打破縣級中轉(zhuǎn)”入手，建設(shè)“區(qū)域中轉(zhuǎn)圈”物流配送服務(wù)新模式。

在兩階段選址?路徑問題中，中轉(zhuǎn)倉的選址及配送路徑的規(guī)劃之間相互影響，中轉(zhuǎn)倉的選址影響整個企業(yè)的運(yùn)作效率和配送路徑的規(guī)劃；而配送路徑的規(guī)劃又影響企業(yè)運(yùn)營狀況和競爭力水平［1-2］。因此，整合優(yōu)化大理D物流公司的中轉(zhuǎn)站選址和配送路徑十分必要。近年來，國內(nèi)外許多學(xué)者對多級車輛運(yùn)輸?shù)南嚓P(guān)選址路徑開展規(guī)劃方案及方法論研究［3-8］。Jacobsen等［9］考慮選址?路徑問題中多階存在性，提出3個建設(shè)性啟發(fā)式求解模型。路世昌等［10］構(gòu)建了以考慮碳排放量的物流綜合成本最小為目標(biāo)的規(guī)劃模型，并設(shè)計出兩階段啟發(fā)式算法，解決配送中心選址與多車型車輛路徑優(yōu)化組合的決策問題。李珍萍等［11］以總成本極小化為目標(biāo)，建立兩層級共同配送選址-路徑問題混合整數(shù)規(guī)劃模型，設(shè)計求解模型的自適應(yīng)大鄰域搜索算法。Nguyen等［12］提出了一種多起點迭代局部搜索算法，利用禁忌搜索算法框架，并通過路徑重連對解方案進(jìn)一步優(yōu)化。

物流網(wǎng)絡(luò)的布局與優(yōu)化問題是當(dāng)前大理D物流公司的痛點，如何從全縣域進(jìn)行中轉(zhuǎn)站選址建設(shè)、確定配送路線及客戶點分配是該問題的幾大難點。對此，本文建立跨縣域干線—支線聯(lián)合優(yōu)化模型，采用貪婪思想構(gòu)建初始方案，再使用變鄰域搜索算法對初始方案進(jìn)行優(yōu)化，采用移除算子、插入算子等方法形成鄰域擾動，優(yōu)化運(yùn)營過程，服務(wù)建設(shè)高效智能的物流智能調(diào)度系統(tǒng)。

1 問題描述

大理D物流公司是一家服務(wù)于大理白族自治州下轄12個縣（市）的物流企業(yè)，其現(xiàn)有的運(yùn)營模式表現(xiàn)為二級配送網(wǎng)絡(luò)：物流中心—中轉(zhuǎn)站—終端零售客戶。該公司以政區(qū)劃分為依據(jù)建設(shè)11個中轉(zhuǎn)站，物流中心位于大理市，并根據(jù)客戶訂單的收貨地址將商品分別發(fā)往11個中轉(zhuǎn)站；各個中轉(zhuǎn)站負(fù)責(zé)收貨并完成商品在本縣域配送工作。然而，受制于縣域直送的配送模式，大理D物流公司逐漸顯露出運(yùn)輸效率低、車輛資源利用不充分、車輛載荷不均衡和路線不合理等狀況。并且，“一縣一站”的建設(shè)使部分不宜或不必設(shè)立中轉(zhuǎn)站的地區(qū)設(shè)立了多余的中轉(zhuǎn)站，導(dǎo)致資源浪費(fèi)。同時，由于未考慮到跨縣域聯(lián)動功能，導(dǎo)致各個縣域間的物流配送工作存在割裂，不利于實現(xiàn)規(guī)模經(jīng)濟(jì)效應(yīng)。

為解決當(dāng)前大理D物流公司人工調(diào)度效率不高及資源浪費(fèi)的問題，本文從大理白族自治州全域優(yōu)化的角度考慮，完全打破各縣域的調(diào)度模式，實現(xiàn)跨區(qū)域聯(lián)合調(diào)度，具體做法是對中轉(zhuǎn)站進(jìn)行重新選址建設(shè)和功能優(yōu)化，為各中轉(zhuǎn)站的車輛和客戶進(jìn)行重新規(guī)劃和分配，重新組建路線。大理D物流公司將大理白族自治州除大理市以外的11個縣市劃分為東、西、南、北4個區(qū)域，計劃在各區(qū)域僅設(shè)置一個區(qū)域中轉(zhuǎn)站。在第一級配送過程中，物流中心根據(jù)各區(qū)域客戶的訂單將商品分別發(fā)往4個區(qū)域中轉(zhuǎn)站，每輛干線車輛只載運(yùn)同一個區(qū)域的商品，車輛到達(dá)中轉(zhuǎn)站以后，直接將商品卸下。在第二級配送過程中，車輛在縣域聯(lián)合優(yōu)化的基礎(chǔ)上重新確定客戶的送貨順序，并構(gòu)造每輛車的行駛路線。

本文以北域區(qū)為例，擬從洱源、鶴慶、劍川中選擇一個合理的中轉(zhuǎn)站，打破三縣原有的配送路線，重新確定每輛車的服務(wù)客戶以及規(guī)劃車輛路線，目標(biāo)是減少配送成本并提高配送效率。干線-支線聯(lián)合優(yōu)化調(diào)度運(yùn)營模式圖如圖1所示。

2 模型建立

基于接駁點的干線-支線聯(lián)合優(yōu)化問題可提煉為兩階段選址-路徑規(guī)劃問題，即已知中心倉庫（大理白族自治州物流中心）、多個候選中轉(zhuǎn)站、末端客戶，中心倉庫到候選中轉(zhuǎn)站為干線配送網(wǎng)絡(luò)，候選中轉(zhuǎn)站到客戶為支線配送網(wǎng)絡(luò)，如何進(jìn)行中轉(zhuǎn)點的選址，以及支線的路徑規(guī)劃，滿足所有客戶的需求且配送成本最低。

2.1 數(shù)學(xué)模型約束條件

數(shù)學(xué)模型的目標(biāo)為總運(yùn)輸里程最短且所考慮的約束條件如下：①候選中轉(zhuǎn)站選址約束；②干線車輛起始和終止位置約束；③支線車輛起始和終止位置約束；④支線客戶有且僅被服務(wù)一次約束；⑤支線車輛流進(jìn)出平衡約束；⑥支線車輛最大裝載約束；⑦支線車輛最大工作時間約束；⑧支線車輛訪問客戶的前后時間關(guān)系約束。

2.2 符號說明

數(shù)學(xué)模型中的各個符號說明見表1。

2.3 數(shù)學(xué)模型建立

數(shù)學(xué)模型中涉及公式如下：

以上公式中，目標(biāo)函數(shù)（1）表示最小化總配送成本（按箱公里結(jié)算）；約束（2）表示候選中轉(zhuǎn)站只能選擇其中的一個；約束（3）界定了干線網(wǎng)絡(luò)車輛出發(fā)時間和到達(dá)候選中轉(zhuǎn)站時間的關(guān)系；約束（4）界定了干線網(wǎng)絡(luò)和支線網(wǎng)絡(luò)之間的時間銜接約束；約束（5）界定了如果候選中轉(zhuǎn)站s不被選中，其車輛不訪問任何客戶；約束（6）和（7）保證每輛候選中轉(zhuǎn)站s中的車從中轉(zhuǎn)站s出發(fā)執(zhí)行任務(wù)，完成任務(wù)后返回到候選中轉(zhuǎn)站s；約束（8）表示每個客戶被服務(wù)且需求被一次性滿足；約束（9）表示每個客戶的車輛流平衡；約束（10）表示車輛k離開中轉(zhuǎn)站s和到達(dá)第一個所訪問客戶的時間關(guān)系約束；約束（11）表示車輛k到達(dá)客戶i和客戶j時間關(guān)系約束；約束（12）表示車輛k訪問客戶i的裝載平衡約束；約束（13）表示車輛k離開候選中轉(zhuǎn)站s所裝載成品煙數(shù)量等于其所要訪問的客戶需求量之和；約束（14）保證每輛車的裝載能力限制；約束（15）表示每輛車的工作時間限制；約束（16）～（22）表示決策變量的取值范圍約束。

3 算法設(shè)計

在大理D物流公司的干線-支線聯(lián)合優(yōu)化算法設(shè)計中，不僅需要考慮支線階段車輛從中轉(zhuǎn)站到各個客戶的行駛距離，還需考慮干線階段車輛從大理中心倉庫到中轉(zhuǎn)站的距離。本文首先采用貪婪思想構(gòu)建初始方案，再使用變鄰域搜索算法，采用移除算子、交換算子等進(jìn)行鄰域擾動，生成最終的優(yōu)化方案。

3.1 貪婪算法構(gòu)造初始方案

在該問題的初始解構(gòu)造中，首先選擇中轉(zhuǎn)站集合中的第一個中轉(zhuǎn)站為區(qū)域中轉(zhuǎn)站，從該區(qū)域中轉(zhuǎn)站開始，選擇離該中轉(zhuǎn)站最近的客戶加到一輛車中，再選擇離該客戶最近的客戶繼續(xù)加到該車輛，并形成相應(yīng)訪問順序的路徑，直至該輛車滿載或者達(dá)到工作時間限制時再啟用一輛新車服務(wù)。當(dāng)所有的客戶均加到車輛中，計算當(dāng)前解的成本，包括物流中心到當(dāng)前區(qū)域中轉(zhuǎn)站的配送距離及區(qū)域中轉(zhuǎn)站所有車輛的配送距離。其次選擇中轉(zhuǎn)站集合中的第一個中轉(zhuǎn)站為區(qū)域中轉(zhuǎn)站，重復(fù)上述解的構(gòu)成，形成第二個解，直至中轉(zhuǎn)站集合中的所有中轉(zhuǎn)站均被選擇，將所有的解進(jìn)行比較，選擇成本最低的解作為初始優(yōu)化方案。初始解構(gòu)造流程如圖2所示。

[輸出當(dāng)前路徑，并生成一條新的空路徑，設(shè)當(dāng)前點i為0，并把i插入新路徑中，更新當(dāng)前車輛編號nm=nm+1，Load=0，T=0

][nz=nz+1，nc=n，n，nm=0，生成一條新的空路徑，初始化i=0，Load=0，T=0][nz≤3][nc≥0][將點j插入當(dāng)前路徑中][將集合S中把點j移除，nc=nc-1][初始化N={0，1，2，…，n}，K={0，1，2，…，k}，其中，N代表客戶集合，集合中的0代表中轉(zhuǎn)站，K表示車輛集合，nc為未滿足的客戶數(shù)，nm為當(dāng)前使用車輛的編號，Capacity為當(dāng)前使用車輛的最大容量，Load為當(dāng)前使用車輛的載貨量，Time為當(dāng)前使用車輛的最大工作時間，T為當(dāng)前使用車輛己工作時間，Z={1，2，3}。Z代表中轉(zhuǎn)站集合，nz為當(dāng)前選中的中轉(zhuǎn)站編號。初始化一條空路徑。設(shè)當(dāng)前點i為0。并把i插入路徑中，集合S={1，2，…，n}，S代表以離當(dāng)前點i的距離按從近到遠(yuǎn)的順序進(jìn)行排序的客戶序列。設(shè)nm=0，即從車輛集合中的0號開始，派出車輛執(zhí)行配送任務(wù)滿足客戶需求。設(shè)nz=1，即從中轉(zhuǎn)站集合中的1號開始求解]

圖2 初始解構(gòu)造流程

3.2 變鄰域搜索算法改進(jìn)初始解

變鄰域搜索算法是一種局域搜索元啟發(fā)式方法，通過系統(tǒng)地改變鄰域結(jié)構(gòu)，不斷探索新的鄰域解來獲取全局可能最優(yōu)解。該算法從初始解開始，通過設(shè)計多種鄰域結(jié)構(gòu)進(jìn)行全面搜索解空間，在每次計算過程中，通過當(dāng)前鄰域結(jié)構(gòu)擾動當(dāng)前解產(chǎn)生一個鄰域解；若新的鄰域解優(yōu)于當(dāng)前解，則新的鄰域解取代當(dāng)前解，繼續(xù)在該鄰域內(nèi)搜索；若局部搜索得到的新的鄰域解劣于當(dāng)前解，則轉(zhuǎn)向下一個鄰域結(jié)構(gòu)繼續(xù)計算。達(dá)到最大鄰域結(jié)構(gòu)時，則停止變鄰域算法的計算。變鄰域搜索算法流程如圖3所示。

給定一個初始解，通過點移除與重新插入的方式生成新的解，每一種點的刪除方式與每一種點的插入方式構(gòu)成一類鄰域結(jié)構(gòu)。本節(jié)分別設(shè)計了單條路徑與多條路徑中點的刪除與插入算法，共計4類鄰域結(jié)構(gòu)。單路徑鄰域結(jié)構(gòu)對當(dāng)前解的改變較小，可看作集中搜索機(jī)制；多路徑鄰域結(jié)構(gòu)則對當(dāng)前解的改變較大，可看做分散搜索機(jī)制。在更換鄰域的過程中，多路徑鄰域結(jié)構(gòu)與單路徑結(jié)構(gòu)交替使用，為擴(kuò)大搜索范圍，每個鄰域結(jié)構(gòu)均可被重復(fù)使用。

（1）單路徑中點的刪除與插入。①鄰域結(jié)構(gòu)1：單路徑中單個點的刪除與插入。在當(dāng)前解中，選擇一條路徑中的一個點移出，插入該路徑中每個可行的位置，最后選擇造成該路徑成本最小的位置插入，即生成一個鄰域解。路徑成本指的是假設(shè)車輛到達(dá)該客戶時形式的距離。②鄰域結(jié)構(gòu)2：單路徑中2個點的刪除與插入。在當(dāng)前解中，隨機(jī)選擇一條路徑中的2個點移出，該路徑中每個可行的位置，最后選擇造成該路徑成本最小的位置插入。

（2）多條路徑中點的刪除與插入。③鄰域結(jié)構(gòu)3：多路徑中單個點的刪除與插入。在當(dāng)前解中，選擇一條路徑中的一個點i移出，插入其余路徑中每個可行的位置，計算插入后的每條路徑的行駛成本之和（計算方法同領(lǐng)域結(jié)構(gòu)1）；將點i插入造成總的路徑成本最小的位置。④鄰域結(jié)構(gòu)4：多路徑中2個點的交換。在當(dāng)前解中，選擇一條路徑中的一個點i，將點i與其余路徑中所有的點交換，最后選擇造成總的路徑成本最小的點交換。

4 實驗結(jié)果分析

4.1 優(yōu)化方案展示

選擇大理白族自治州北部三縣的實際運(yùn)作數(shù)據(jù)作為實驗數(shù)據(jù)進(jìn)行測試，包括客戶編號、客戶需求、客戶坐標(biāo)、物流中心及中轉(zhuǎn)站坐標(biāo)、車輛大小等信息。在Visual Studio 2017軟件上運(yùn)行算法后，得到具體優(yōu)化方案，區(qū)域中轉(zhuǎn)站確定為鶴慶中轉(zhuǎn)站，從區(qū)域中轉(zhuǎn)站出發(fā)，每輛車的行駛距離、行駛時間、配送客戶數(shù)、配送的商品數(shù)量、車輛空載率和車牌號，以及每輛車具體的配送任務(wù)均能體現(xiàn)在結(jié)果中（如圖4所示）。

4.2 優(yōu)化方案與原模式結(jié)果對比分析

4.2.1 干線成本對比

聯(lián)合優(yōu)化前后干線行駛距離對比情況見表2。

由表2可以看出，干線所有路線優(yōu)化前行駛距離為340.36 km，優(yōu)化后行駛距離為268.84 km，節(jié)省行駛距離約71.52 km，優(yōu)化率達(dá)到20.01%。

聯(lián)合優(yōu)化前后干線行駛時間對比情況見表3。

由表3可以看出，干線所有路線優(yōu)化前行駛時間為294.59 min，優(yōu)化后行駛時間為229.16 min，節(jié)省行駛時間約65.43 min，優(yōu)化率達(dá)到22.21%。

4.2.2 支線成本對比

聯(lián)合優(yōu)化前后支線行駛距離對比情況見表4。

由表4可以看出，三縣所有路線優(yōu)化前行駛距離為2 268.35 km，優(yōu)化后行駛距離為1 683.74 km，節(jié)省行駛距離約584.61 km，優(yōu)化率達(dá)到25.77%。

聯(lián)合優(yōu)化前后支線行駛時間對比情況見表5。

由表5可以看出，三縣所有路線優(yōu)化前行駛時間為7 117.52 min，優(yōu)化后行駛時間為5 654.21 min，節(jié)省行駛時間約1 463.31 min，優(yōu)化率達(dá)到20.56%。

聯(lián)合優(yōu)化前后使用車輛數(shù)及趟數(shù)對比情況見表6。

由表6可以看出，干線—支線聯(lián)合路線優(yōu)化前需使用車輛數(shù)為10輛，需要行駛的趟數(shù)一共為13趟，聯(lián)合優(yōu)化后需使用車輛數(shù)為16輛，需要行駛的趟數(shù)一共為16趟。在聯(lián)合優(yōu)化后，配送路線打破了行政區(qū)域的界限，以全域最優(yōu)為目標(biāo)，適當(dāng)增加了車輛的數(shù)量和趟數(shù)，以減少迂回運(yùn)輸、重復(fù)運(yùn)輸和過遠(yuǎn)運(yùn)輸，雖然車輛數(shù)和趟數(shù)增加，但是行駛總距離和時間減少，實現(xiàn)總成本的最小化。

5 結(jié)語

文章借助數(shù)學(xué)模型與智能優(yōu)化算法，對大理D物流公司的調(diào)度運(yùn)營模式進(jìn)行跨縣域干線-支線聯(lián)合優(yōu)化，打破行政區(qū)劃、突破城鄉(xiāng)界限、擺脫縣級中轉(zhuǎn)，以全域最優(yōu)為目標(biāo)，統(tǒng)籌規(guī)劃車輛配送路線，縮短車輛的行駛距離，減少迂回運(yùn)輸、重復(fù)運(yùn)輸和過遠(yuǎn)運(yùn)輸情況的發(fā)生，降低運(yùn)輸成本，提高公司的配送效率。同時，在支線配送過程中，采取甩箱模式，大幅度節(jié)省物品的裝卸搬運(yùn)時間，提高整個運(yùn)輸環(huán)節(jié)的效率，提升企業(yè)競爭力。

6 參考文獻(xiàn)

［1］萬孟然，葉春明，董君，等.考慮備災(zāi)的雙層規(guī)劃應(yīng)急資源調(diào)度選址—路徑優(yōu)化模型與算法［J］.計算機(jī)應(yīng)用研究，2021，38（10）：2961-2967.

［2］李航.多商品需求可拆分兩階段車輛路徑問題模型與算法研究［D］.開封：河南大學(xué)，2022.

［3］Jepsen M，Spoorendonk S，Ropke S.A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem［J］.Transportation Science，2013，47（1）：23-37.

［4］Kechmane L，Nsiri B，Baalal A.Optimization of a Two-Echelon Location Lot-Sizing Routing Problem with Deterministic Demand［J］.Mathematical Problems in Engineering，2018（1）：1-12.

［5］Mirhedayatian S M，Crainic T G，Guajardo M，et al.A two-echelon location-routing problem with synchronisation［J］.Journal of the Operational Research Society，2019（54）：1-16.

［6］唐震霆，胡志華.針對多中心場站下兩級選址路徑問題的雙智能集成算法［J］.大連理工大學(xué)學(xué)報，2022，62（5）：543-550.

［7］楊屹夫，孫冰，馬艷芳，等.服務(wù)差異二級選址路徑問題及大鄰域搜索算法［J］.計算機(jī)工程與應(yīng)用，2023，59（3）：282-292.

［8］李想，李蘇劍，李宏.兩級選址-路徑問題的大規(guī)模鄰域搜索模擬退火算法［J］.工程科學(xué)學(xué)報，2017，39（6）：953-961.

［9］Jacobsen S K，Madsen O.A comparative study of heuristics for a two-level routing-location problem［J］.European Journal of Operational Research，1980，5（6）：378-387.

［10］路世昌，邵旭倫，李丹.基于兩階段啟發(fā)式算法的低碳物流選址-多車型路徑問題研究［J］.制造業(yè)自動化，2023，45（3）：202-207.

［11］李珍萍，趙雨薇，張煜煒，等.共同配送選址-路徑問題及大鄰域搜索算法［J］.系統(tǒng)仿真學(xué)報，2021，33（10）：2518-2531.

［12］Nguyen V P，Prins C，Prodhon C.A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem［J］.Engineering Applications of Artificial Intelligence，2012，25（1）：56-71.