DOI：10.3969/j.issn.10001565.2024.04.002

摘要：為做好集配一體化背景下物流網(wǎng)絡(luò)選址-路徑規(guī)劃設(shè)計(jì)，用大規(guī)模鄰域搜索算法的破壞、重組策略代替?zhèn)鹘y(tǒng)混合自適應(yīng)遺傳算法中的交叉、變異過(guò)程，實(shí)現(xiàn)算法的優(yōu)化設(shè)計(jì).通過(guò)模擬算例分析可知，優(yōu)化后的算法能夠有效克服傳統(tǒng)算法在運(yùn)算過(guò)程中出現(xiàn)的早熟及穩(wěn)定性差等問(wèn)題，在一定程度上提升獲取更優(yōu)解的概率，提高客戶滿意度.利用已知標(biāo)桿數(shù)據(jù)對(duì)算法進(jìn)行有效性檢驗(yàn).計(jì)算結(jié)果表明：優(yōu)化后的算法各項(xiàng)指標(biāo)表現(xiàn)良好，對(duì)于部分?jǐn)?shù)據(jù)的計(jì)算結(jié)果優(yōu)于其他3個(gè)已有算法，與已知最優(yōu)解基本保持一致，進(jìn)一步驗(yàn)證了優(yōu)化算法的科學(xué)性和有效性.

關(guān)鍵詞：集配一體化；鄰域搜索；選址路徑

中圖分類號(hào)：U492.2;TP301.6文獻(xiàn)標(biāo)志碼：A文章編號(hào)：10001565（2024）04034609

Algorithm of site selection path integration problem

under the background of simultaneous distribution and collection

CHENG Tao， LI Meixi， LI Jiali

（School of Computer and Information Engineering， Harbin University of Commerce， Harbin 150028， China）

Abstract： In order to do a good job in the site selection-path planning and design of logistics network under the background of integration of simultaneous distribution and collection， the crossover and mutation processes in the traditional hybrid adaptive genetic algorithm are replaced by the destruction and recombination strategies of the large-scale neighborhood search algorithm， and the optimization design of the algorithm is realized.After analyzing the simulation example， it can be seen that the optimized algorithm can effectively overcome the problems of early maturity and poor stability of the traditional algorithm in the calculation process， improve the probability of obtaining a better solution to a certain extent， and improve customer satisfaction.The effectiveness of the algorithm is tested by using the known benchmark data， and the calculation results show that the indicators of the optimized algorithm perform well， and the calculation results of some data are better than the other three existing algorithms， which is basically consistent with the known optimal solution， and this further verifies the scientificity and effectiveness of the optimization algorithm in this paper.

Key words： set distribution integration;neighborhood search;location routing problem

收稿日期：20221101;修回日期：20240301

基金項(xiàng)目：黑龍江省哲學(xué)社會(huì)科學(xué)研究規(guī)劃項(xiàng)目（23XZT052）；2023年度黑龍江省省屬本科高校優(yōu)秀青年教師基礎(chǔ)研究支持計(jì)劃項(xiàng)目（黑龍江省數(shù)字化與農(nóng)業(yè)現(xiàn)代化融合發(fā)展研究）

第一作者：程濤（1978—），男，哈爾濱商業(yè)大學(xué)教授，博士，主要從事電子商務(wù)、現(xiàn)代流通及數(shù)字農(nóng)業(yè)方向研究.

E-mail：6885854@qq.com

通信作者：李佳俐（1981—），女，哈爾濱商業(yè)大學(xué)講師，博士，主要從事現(xiàn)代流通業(yè)與產(chǎn)業(yè)競(jìng)爭(zhēng)力方向研究.

E-mail：53031009@qq.com

1研究概述

設(shè)施選址問(wèn)題（location allocation problem，LAP）與車輛路徑規(guī)劃問(wèn)題（vehicle routing problem，VRP）是物流管理決策的重要組成部分，早期研究通常沿著LAP或VRP的單一視角展開(kāi)［1］.美國(guó)物流專家韋伯是研究LAP問(wèn)題的先行者，在1909年就開(kāi)始了對(duì)倉(cāng)庫(kù)與多個(gè)客戶之間的配送距離及物流成本關(guān)系的研究.湯杼彬［2］綜合考慮交通、用地等因素，以運(yùn)輸成本最小化為優(yōu)化目標(biāo)構(gòu)建了多層次物流中心選址模型；鄒筱等［3］針對(duì)冷鏈物流配送，通過(guò)增加貨損成本目標(biāo)函數(shù)，重新設(shè)計(jì)了選址模型，研究發(fā)現(xiàn)單級(jí)配送網(wǎng)絡(luò)是局部最優(yōu)解，兩級(jí)配送網(wǎng)絡(luò)則是整體最優(yōu)解；田立霞等［4］采用多主體均衡優(yōu)化方法對(duì)加氫站的選址問(wèn)題展開(kāi)研究；韋子輝等［5］將改進(jìn)后的PFA算法與Levy飛行相融合，有效解決了算法早熟、易陷入局部最優(yōu)等問(wèn)題，能夠在復(fù)雜環(huán)境下得到更準(zhǔn)確的定位結(jié)果.

VRP由Dantzig Ramser等［6］于1959年提出，為解決物流管理問(wèn)題提供了新的方案.馬貴平等［7］、濮明月等［8］利用改進(jìn)蟻群算法對(duì)物流配送車輛路徑問(wèn)題進(jìn)行規(guī)劃設(shè)計(jì)，并在此基礎(chǔ)上搭建了運(yùn)輸路徑優(yōu)化模型，提高了物流行業(yè)的運(yùn)輸效率；夏強(qiáng)等［9］以水果罐頭運(yùn)輸為例，利用Matlab軟件建立線性規(guī)劃數(shù)學(xué)模型進(jìn)行求解，得出最優(yōu)路徑選擇方案；王祺等［10］利用大規(guī)模鄰域搜索算法對(duì)多配送中心的冷鏈物流車輛路徑問(wèn)題展開(kāi)研究，得出嵌入局部搜索的改進(jìn)遺傳算法能夠避免局部最優(yōu)、加快收斂性這一結(jié)論.

19世紀(jì)60年代后，開(kāi)始有學(xué)者將LAP和VRP綜合考慮，逐步衍生出選址-路徑集成問(wèn)題（location routing problem，LRP）理論研究框架，Maranzana［11］是這一領(lǐng)域的創(chuàng)始人，在1964年首次同時(shí)對(duì)供貨點(diǎn)的地理位置以及從供貨點(diǎn)到服務(wù)點(diǎn)的距離之和這2方面問(wèn)題開(kāi)展研究，為物流網(wǎng)絡(luò)建設(shè)的研究工作開(kāi)辟新思路.目前，學(xué)術(shù)界對(duì)于選址-路徑集成問(wèn)題的研究已經(jīng)取得了較為豐碩的成果：王萬(wàn)良等［12］針對(duì)傳統(tǒng)啟發(fā)式算法在解決大規(guī)模LRP時(shí)通用性差、效率低的缺點(diǎn)，設(shè)計(jì)了以選擇函數(shù)法作為選擇策略的超啟發(fā)算法，能夠高效、準(zhǔn)確、智能地設(shè)計(jì)出調(diào)度方案；劉凡等［13］利用改進(jìn)的蘑菇繁殖算法對(duì)開(kāi)放式選址路徑問(wèn)題進(jìn)行了研究，有效解決了在離散、連續(xù)空間轉(zhuǎn)換時(shí)的數(shù)據(jù)丟失問(wèn)題；周迅等［14］在綜合考慮倉(cāng)庫(kù)開(kāi)放成本、配送成本、車輛成本及懲罰成本的基礎(chǔ)上，設(shè)計(jì)了新型離散煙花算法，并通過(guò)求解算例對(duì)算法有效性和可行性進(jìn)行了驗(yàn)證；張得志等［15］搭建了兩階段物流配送網(wǎng)絡(luò)布局優(yōu)化模型，利用改進(jìn)遺傳算法對(duì)北京市綠色物流配送網(wǎng)絡(luò)展開(kāi)研究，為超大型城市綠色物流布局與服務(wù)路徑優(yōu)化決策提供了相應(yīng)的理論依據(jù).

目前，眾多學(xué)者從降低成本、提高效率、優(yōu)化通用性、加快收斂速度等多個(gè)視角對(duì)選址-路徑集成問(wèn)題展開(kāi)研究，所采用的算法十分豐富.但是，現(xiàn)有的研究主要圍繞物流配送環(huán)節(jié)展開(kāi)，缺少了對(duì)集貨路徑問(wèn)題（vehicle routing problem with backhaul，VRPB）的考量，能夠同時(shí)兼顧配送物流與集貨物流這2個(gè)逆向過(guò)程的研究則更為少見(jiàn).鑒于此，本文借鑒大規(guī)模鄰域搜索算法的破壞重組策略對(duì)傳統(tǒng)自適應(yīng)遺傳算法進(jìn)行優(yōu)化設(shè)計(jì)，將優(yōu)化后的算法應(yīng)用于集配一體化背景下的選址-路徑集成問(wèn)題，在節(jié)點(diǎn)選擇及往返路徑規(guī)劃中借鑒了孿生網(wǎng)絡(luò)［16］和無(wú)線傳感器網(wǎng)絡(luò)［17］的設(shè)計(jì)思想，為相關(guān)工作的開(kāi)展提供決策依據(jù).

2模型構(gòu)建

2.1問(wèn)題描述及研究假設(shè)

現(xiàn)代物流配送網(wǎng)絡(luò)的設(shè)計(jì)過(guò)程中需要同時(shí)考慮正向物流和逆向物流，本文以專業(yè)配送企業(yè)的物流網(wǎng)絡(luò)結(jié)構(gòu)為研究對(duì)象，針對(duì)集配一體化背景下城市內(nèi)物流選址-路徑集成問(wèn)題展開(kāi)研究.企業(yè)在進(jìn)行物流網(wǎng)絡(luò)規(guī)劃時(shí)，通常要按照三級(jí)層次進(jìn)行設(shè)計(jì)：作為一級(jí)子節(jié)點(diǎn)的分撥中心，作為二級(jí)子節(jié)點(diǎn)中轉(zhuǎn)站以及作為三級(jí)子節(jié)點(diǎn)的服務(wù)網(wǎng)點(diǎn)，其中服務(wù)網(wǎng)點(diǎn)同時(shí)具備收、發(fā)雙重功能，運(yùn)輸車輛在配送的同時(shí)完成集貨任務(wù).物流網(wǎng)絡(luò)三級(jí)結(jié)構(gòu)模型如圖1所示.圖1城市內(nèi)物流網(wǎng)絡(luò)三級(jí)結(jié)構(gòu)模型

Fig.1Model diagram of three-level structure of urban intralogistics network

提高物流效率不僅是降低企業(yè)經(jīng)營(yíng)成本的重要途徑，也是提高消費(fèi)者滿意度的有效手段.LRP不是LAP和VRP的簡(jiǎn)單疊加，二者的綜合會(huì)讓問(wèn)題變得異常復(fù)雜.在有效解決選址-路徑集成問(wèn)題的同時(shí)，還需兼顧因顧客寄發(fā)及退貨所引發(fā)的逆向物流問(wèn)題，進(jìn)一步增加了問(wèn)題的復(fù)雜程度.在這個(gè)過(guò)程中，要解決3個(gè)層次子節(jié)點(diǎn)的選址分布問(wèn)題和3個(gè)層次子節(jié)點(diǎn)間的往返行車路線規(guī)劃問(wèn)題.因此，為了更好地完成模型設(shè)計(jì)，做出假設(shè).

假設(shè)1：分撥中心、中轉(zhuǎn)站及服務(wù)網(wǎng)點(diǎn)的數(shù)量、服務(wù)能力及分?jǐn)偝杀疽阎?/p>

假設(shè)2：每個(gè)服務(wù)網(wǎng)點(diǎn)的服務(wù)顧客對(duì)象及其配送、集貨數(shù)量已知；

假設(shè)3：三級(jí)網(wǎng)點(diǎn)之間的配送車輛數(shù)量及總承載量已知；

假設(shè)4：物流網(wǎng)絡(luò)節(jié)點(diǎn)之間的歐式距離、車輛行駛距離及車輛行駛單位距離的成本已知.

2.2數(shù)學(xué)模型構(gòu)建

根據(jù)物流網(wǎng)絡(luò)三級(jí)結(jié)構(gòu)模型及假設(shè)，構(gòu)建數(shù)學(xué)模型.

1）物流配送總成本Min Z1=∑（d∈NDFD*ZK+∑i∈N∑j∈N∑k∈KRC*dij xijk+∑i∈N∑j∈N∑k∈KFV*xijk，（1）其中：Z1是物流配送總成本；FD是商品分?jǐn)偝杀?；ZK （K={1，2，…，k}）是第K件商品的物流成本；RC是運(yùn)輸車輛單位距離運(yùn)送成本；FV是運(yùn)輸車輛固定派遣費(fèi)用；dij是節(jié)點(diǎn)i和j之間的距離;xijk是決策變量，當(dāng)xijk=1時(shí)，表示車輛K從i駛向j，當(dāng)xijk=0時(shí)，表示i和j之間沒(méi)有可用路徑.

2）最大客戶滿意度水平Max Z2=∑j∈Nc （（S（Ti ）+Uj （Tj ））*（dj+pj ）/∑j∈Nc （dj+pj）），（2）其中：Z2是客戶滿意度；Nc={1，2，…，c}是物流網(wǎng)絡(luò)顧客點(diǎn)集合.

3）集配一體化限定

要求每輛車需一次性完成顧客配送和集貨需求，即滿足集配一體化標(biāo)準(zhǔn).同時(shí)還要保證每個(gè)顧客只能由1輛車提供服務(wù).∑t∈n∑k∈Kxijk=1，j∈J，（3）

∑j∈Nxijk-∑j∈Nxjik=0，i∈N，k∈K，（4）其中，xijk是決策變量：xijk=1時(shí)，表示車輛k從節(jié)點(diǎn)i駛向j; xijk=0時(shí)，表示i、j之間沒(méi)有可用路徑.

4）為保障顧客滿意度水平，需要對(duì)顧客服務(wù)時(shí)間進(jìn)行約束，約束模型為Max（ATj，Inf（λj ））≤Tj≤Sup（λj ），j∈Nc；（5）

ATj=∑i∈vxij （Ti+tij+td di+tp pi），j∈Nc.（6）其中：Tj是顧客j開(kāi)始的服務(wù)時(shí)間;ATj是運(yùn)輸車輛到達(dá)顧客j的時(shí)間;tp是單位貨物的平均集貨時(shí)間;pi是顧客i的集貨需求量，i∈Nc.

5）每個(gè)中轉(zhuǎn)站負(fù)責(zé)服務(wù)的顧客的集配貨物總量不能超過(guò)中轉(zhuǎn)站的最大承受能力，其約束模型為∑i∈Ncdi yid≤CDzd，d∈ND，（7）

∑i∈Ncpi yid≤CDzd，d∈ND，（8）其中：CD是配送中心的服務(wù)能力限制；ND={i|i=1，2，…，m}是配送系統(tǒng)中中轉(zhuǎn)站的集合；zd是決策變量，當(dāng)za=1時(shí)，表示配送中心點(diǎn)d被選用，否則不被選用.

6）每條配送路徑中安排配送車輛的總承載量要大于該條路徑的集送貨總量，約束模型為Uij+Vij≤CVij，i，j∈N，i≠j.（9）7）限定客戶與中轉(zhuǎn)站、車輛與中轉(zhuǎn)站之間均為一對(duì)一關(guān)系，同時(shí)，在行駛過(guò)程中，要避免車輛在顧客點(diǎn)之間形成回路，約束模型為∑k∈NDyik=1，i∈Nc，（10）

∑p∈Ncxipk +∑p∈N，p≠jxpjk≤1+yid，i∈Nc，d∈ND，k∈K，（11）

ui-uj+N∑k∈Kxijk≤N-1，i∈Nc，j∈Nc.（12）8）在配送過(guò)程中，每個(gè)參與服務(wù)顧客中轉(zhuǎn)站的集送貨數(shù)量上限是固定的，因此需要確保中轉(zhuǎn)站總的集送貨量保持守恒，其約束模型為∑j∈NcUkj=∑j∈Ncdj yjd，d∈ND，∑j∈NcVjk=∑j∈Ncpj ydj，d∈ND；（13）

∑j∈NcUkj=0，k∈ND" ∑j∈NcVjk=∑j∈Ncpj ydj，d∈ND.（14）3算法設(shè)計(jì)與算例分析

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

3.1.1設(shè)計(jì)思想

物流網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵在于鄰域搜索，傳統(tǒng)混合自適應(yīng)遺傳算法（adaptive genetic algorithm，AGA）能夠通過(guò)交叉及變異過(guò)程得到有效的鄰域解，在求解一般的全局最優(yōu)問(wèn)題方面有著不俗的表現(xiàn).然而，當(dāng)面對(duì)同時(shí)考慮集貨、配貨過(guò)程的選址-路徑集成問(wèn)題時(shí)，其交叉和變異過(guò)程的早熟性及穩(wěn)定性差的缺點(diǎn)就會(huì)暴露出來(lái)，當(dāng)交叉概率和變異概率選取不當(dāng)時(shí)，鄰域解的偏差率明顯增高，特別是當(dāng)解空間較為復(fù)雜時(shí)，用于進(jìn)行鄰域搜索的自適應(yīng)策略科學(xué)性不夠，算法需要耗費(fèi)大量時(shí)間用于適應(yīng)值估算，從而降低了工作效率，因此需要對(duì)其搜索策略加以優(yōu)化.自適應(yīng)大規(guī)模鄰域搜索算法（adaptive large neighborhood search，ALNS）是一種啟發(fā)式方法，其本質(zhì)是對(duì)初始解不斷交替進(jìn)行破壞和修復(fù)，最終求得最優(yōu)解.ALNS在鄰域搜索的基礎(chǔ)上增加了對(duì)算子作用效果的衡量，使算法能夠自動(dòng)選擇更適合的算子進(jìn)行破壞和修復(fù)，這樣可以很大程度上提高獲得更優(yōu)解的概率.因此，本文將大規(guī)模鄰域搜索算法的破壞、修復(fù)策略引入到傳統(tǒng)自適應(yīng)遺傳算法中，用破壞、修復(fù)過(guò)程替代交叉與變異過(guò)程，從而實(shí)現(xiàn)算法優(yōu)化.

3.1.2算法策略及求解流程

以圖1所示模型為例，將優(yōu)化后的混合自適應(yīng)遺傳算法應(yīng)用于物流網(wǎng)絡(luò)的選址-路徑設(shè)計(jì)時(shí)，其破壞過(guò)程就是隨機(jī)移除服務(wù)網(wǎng)點(diǎn)及配送路徑，關(guān)閉或開(kāi)啟中轉(zhuǎn)站，將所移除的對(duì)象臨時(shí)存放在Insert數(shù)組中.修復(fù)過(guò)程則是從Insert數(shù)組中隨機(jī)取出存放的對(duì)象，插入到物流網(wǎng)絡(luò)中可插入的位置，并重新計(jì)算成本.在求解過(guò)程的不同階段，根據(jù)不同階段解的狀態(tài)特征重新調(diào)整搜索因子組合策略，從而進(jìn)一步豐富解的多樣性.在每次迭代運(yùn)算后期，利用模擬退火算法進(jìn)行鄰域搜索并比較計(jì)算結(jié)果，如果出現(xiàn)更優(yōu)解，則重復(fù)搜索過(guò)程，直至找到最優(yōu)解.具體過(guò)程如圖2所示.圖2求解流程

Fig.2Solution process

1）破壞過(guò)程

小規(guī)模破壞主要指移除服務(wù)網(wǎng)點(diǎn)及配送路徑，大規(guī)模破壞則是指關(guān)閉、開(kāi)啟中轉(zhuǎn)站.本文僅對(duì)小規(guī)模破壞過(guò)程進(jìn)行分析.

移除服務(wù)網(wǎng)點(diǎn)分3步進(jìn)行.

第1步：確定移除根節(jié)點(diǎn).在配送網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)服務(wù)網(wǎng)點(diǎn)作為移除根節(jié)點(diǎn);

第2步：計(jì)算最多移除點(diǎn)數(shù)量Max R1，Max R1=［RP1·|Nc |］，其中R為移除對(duì)象，P為客戶點(diǎn)的集貨需求量，Nc為配送網(wǎng)絡(luò)中服務(wù)網(wǎng)點(diǎn)最大數(shù);

第3步：在［1，MaxR1 ］之間選擇一個(gè)隨機(jī)數(shù)NumR1，作為移除點(diǎn)數(shù)，將根節(jié)點(diǎn)與距離根節(jié)點(diǎn)最近的NumR1-1個(gè)服務(wù)網(wǎng)點(diǎn)從配送網(wǎng)絡(luò)中移除，并存入Insert數(shù)組中.

移除配送路徑分3步進(jìn)行.

第1步：計(jì)算最多移除路徑數(shù)量Max R2=RP2·∑i∈cdiQK；

第2步：在［1，MaxR2 ］之間選擇一個(gè)隨機(jī)數(shù)NumR2，作為移除路徑數(shù);

第3步：隨機(jī)選擇NumR2條路徑進(jìn)行移除，并將移除路徑后產(chǎn)生的空白服務(wù)網(wǎng)點(diǎn)存入Insert數(shù)組中.

2）修復(fù)過(guò)程

在修復(fù)過(guò)程中，需要將Insert數(shù)組中存放的所有移除點(diǎn)按照隨機(jī)順序重新插入到配送網(wǎng)絡(luò)中可插入的位置，具體分為4步進(jìn)行.

第1步：檢查配送網(wǎng)絡(luò).如果不存在空白插入點(diǎn)，則結(jié)束，否則執(zhí)行第2步；

第2步：計(jì)算每條配送路徑是否滿足當(dāng)前待插入點(diǎn)的需求量，如存在可供插入的路徑，則執(zhí)行第3步，否則執(zhí)行第4步；

第3步：隨機(jī)插入服務(wù)網(wǎng)點(diǎn)后，計(jì)算增加成本，選擇成本增加最小或者第二小的位置，然后返回執(zhí)行第1步；

第4步：計(jì)算待插入點(diǎn)到所有可供使用的中轉(zhuǎn)站之間的距離，隨機(jī)選擇距離最小或者第二小的中轉(zhuǎn)站建立一條配送路徑，然后返回執(zhí)行第1步.

3）鄰域搜索過(guò)程

當(dāng)配送網(wǎng)絡(luò)經(jīng)過(guò)破壞、修復(fù)過(guò)程后，開(kāi)展鄰域搜索工作.為了防止陷入局部最優(yōu)，采用模擬退火算法，執(zhí)行4次搜索過(guò)程：首先隨機(jī)選擇某條節(jié)點(diǎn)路徑，交換這條路徑上的節(jié)點(diǎn)順序從而產(chǎn)生新路徑，計(jì)算成本，如果成本降低則保留；其次隨機(jī)選擇某個(gè)中轉(zhuǎn)站的2條路徑，交換2條路徑的前后連接順序，形成新路徑.如果新路徑滿足配送車輛的容量約束且成本降低，則保留；再次將某個(gè)需求點(diǎn)插入到距離最近的需求點(diǎn)的前面或者后面，如果導(dǎo)致成本降低，則保留；最后交換2個(gè)或者多個(gè)需求點(diǎn)，如果交換后能夠滿足配送車輛的容量約束且成本降低，則保留.

3.1.3編碼及懲罰函數(shù)設(shè)計(jì)

以圖1所示為例，采用自然數(shù)進(jìn)行編碼，編碼由3部分組成：第1部分為顧客順序號(hào)，共有10個(gè)客戶點(diǎn)需要提供物流服務(wù)，編號(hào)分別為C1～C10；第2部分為車輛編碼，共有6輛運(yùn)輸車輛，其編號(hào)為V1～V6，車輛編碼由車輛起始服務(wù)顧客編碼表示，未被啟用的運(yùn)輸車輛編碼用0占位；第3部分為中轉(zhuǎn)站編碼，本例中共建有6個(gè)中轉(zhuǎn)站，編號(hào)分別為S11～S16，其中S11、S12、S13、S14 4個(gè)中轉(zhuǎn)站被選中，未被選中的中轉(zhuǎn)站編碼用0占位.按照上述規(guī)則，生成編碼為［1，5，8，10，2，9，7，6，3，4，5，2，7，6，0，0，11，12，13，14，0，0］.此編碼共分為3個(gè)子串，如圖3所示.圖3LRP解自然數(shù)編碼示例

Fig.3Example of natural number coding of LRP solution

4個(gè)被選中的中轉(zhuǎn)站產(chǎn)生4條車輛運(yùn)輸路徑，分別為：路徑1：11-5-1-11；路徑2：12-2-10-8-12；路徑3：13-7-9-13；路徑4：14-6-3-4-14.

根據(jù)算法設(shè)計(jì)需求，懲罰約束函數(shù)分別如式（15）～（17）所示.P1=∑i∈Nd∑j∈NcMax（Uij+Vij-CVk xijk，0），（15）

P2=∑j∈NcMax（Inf（λj）-ATj，0）+∑j∈Nc Max（ATj-Sup（λj），0），（16）

P3=∑i∈NdMax（∑j∈Ncdj zij-CDi zi，0）+∑i∈NdMax（∑j∈NcPj zij-CDi zi，0），（17）其中：用P1代表超出車輛運(yùn)載能力上限的懲罰;P2代表超出顧客最大等待時(shí)間的懲罰;P3代表超出中轉(zhuǎn)站最大服務(wù)能力的懲罰.3.1.4初始解的生成

本文采用C-W節(jié)約算法生成初始解，C-W算法屬于啟發(fā)式構(gòu)造方法，其核心是按照配送距離由大到小的順序構(gòu)造路徑，將不在線路上的點(diǎn)陸續(xù)加入線路中.在車輛行駛速度恒定的前提下，距離可用時(shí)間變化量加以描述.車輛從i出發(fā)到j(luò)的時(shí)間變化量為EFj，則EFj=Ti+tij+td di+tp pi-Tj.（18）用Δj 表示j與其后面的顧客點(diǎn)之間允許最大的時(shí)間前推量，則Δj-=Minr≥j{Tr-ETr }.（19）用Δj+ 表示j與其后面的顧客點(diǎn)之間允許最大的時(shí)間后推量，則Δj+=Minr≥j{LTr-ETr}.（20）用時(shí)間變化量代替距離，通過(guò)運(yùn)算得到初始解，具體運(yùn)算過(guò)程如下：

1）逐一掃描尚未分配服務(wù)中轉(zhuǎn)站的顧客，將其和距離最近的中轉(zhuǎn)站建立聯(lián)系，并將對(duì)應(yīng)關(guān)系寫(xiě)入指定關(guān)系集合中；

2）根據(jù)待服務(wù)顧客數(shù)量對(duì)中轉(zhuǎn)站進(jìn)行排序，將最靠前的中轉(zhuǎn)站設(shè)為選中狀態(tài)，安排車輛；

3）根據(jù)最短距離優(yōu)先原則，對(duì)選中中轉(zhuǎn)站的服務(wù)顧客進(jìn)行排序，并逐一計(jì)算選中中轉(zhuǎn)站與每一名待服務(wù)顧客的距離成本，生成距離成本排序表；

4）按照距離成本排序表順序逐一與客戶連接，并判斷是否滿足當(dāng)前車輛運(yùn)力，如不滿足，則跳轉(zhuǎn)至7）；如滿足，則執(zhí)行5）.

5）計(jì)算EFj，若EFj=0，則執(zhí)行6）.若EFj≠0，則計(jì)算Δj-和Δj+，若|EFj|lt;Δj-或者|EFj|lt;Δj+，則執(zhí)行6），否則跳轉(zhuǎn)至7）；

6）把顧客對(duì)加入到當(dāng)前路徑集的最后，重新計(jì)算車輛到達(dá)每個(gè)顧客的時(shí)間；

7）從距離成本排序表中移除當(dāng)前顧客對(duì)，并跳轉(zhuǎn)至4）.

3.2算例分析

3.2.1算例設(shè)定

根據(jù)3.1節(jié)的算法設(shè)計(jì)思想，依然以圖1物流網(wǎng)絡(luò)模型為例，假設(shè)共有4個(gè)中轉(zhuǎn)站對(duì)外提供服務(wù)，編號(hào)分別為S11～S14，中轉(zhuǎn)站所處位置隨機(jī)分配，具體用坐標(biāo)（x，y）描述.每個(gè)中轉(zhuǎn)站最大服務(wù)量已知，且對(duì)外提供服務(wù)能力相同，分?jǐn)偣潭ㄖ惦S機(jī)分配，如表1所示.表1中轉(zhuǎn)站信息

Tab.1Transfer station information編號(hào)位置（x，y）最大服務(wù)量分?jǐn)偣潭ㄖ礢11（11，15）16011.2S12（30，19）16012.5S13（79，13）1608.9S14（109，80）1605.6

假設(shè)需要提供服務(wù)的客戶點(diǎn)共有10個(gè)，編號(hào)分別為C1～C10，客戶點(diǎn)所處位置隨機(jī)分配，具體用坐標(biāo)（x，y）描述.每個(gè)客戶點(diǎn)的配貨量及集貨量已知，配貨量和集貨量之和大致相同，且集配貨總量不超過(guò)中轉(zhuǎn)站最大服務(wù)量之和.用于描述客戶滿意度的時(shí)間窗隨機(jī)分配.客戶點(diǎn)信息如表2所示.

根據(jù)算例設(shè)計(jì)需要，參考其他標(biāo)桿算例數(shù)據(jù)，對(duì)本文所需參變量進(jìn)行預(yù)設(shè)，具體如表3所示.

3.2.2算例分析結(jié)果

在本文設(shè)計(jì)的算例中，啟用了4個(gè)中轉(zhuǎn)站和4臺(tái)運(yùn)輸車輛，客戶服務(wù)點(diǎn)共10個(gè)，設(shè)定4條配送路徑.假設(shè)客戶最低滿意度為0.9，采用MathWorks出品的工具M(jìn)atlab作為數(shù)據(jù)分析及算法運(yùn)行環(huán)境，利用C#編寫(xiě)算法核心邏輯.將C#類庫(kù)算法函數(shù)調(diào)入Matlab中，同時(shí)結(jié)合Matlab工具箱的內(nèi)置函數(shù)，共同完成對(duì)模擬算例集的求解過(guò)程，求得物流總成本、固定分?jǐn)偝杀炯皟?yōu)化滿意度，具體結(jié)果：總成本 36 371.4元，配送成本 36 789元，固定分?jǐn)偝杀?1.5元，啟用車輛4輛，啟用中轉(zhuǎn)站S11、S12、S13、S14，最低滿意度0.9，優(yōu)化滿意度0.918.經(jīng)過(guò)優(yōu)化后，顧客滿意度由0.9提升至0.918，提升了2%，這充分說(shuō)明本文的設(shè)計(jì)思想實(shí)現(xiàn)了對(duì)傳統(tǒng)算法的優(yōu)化，能夠進(jìn)一步提高物流效率、降低物流成本，為物流企業(yè)選址路徑規(guī)劃決策提供指導(dǎo).

3.3有效性驗(yàn)證

為進(jìn)一步說(shuō)明算法的有效性，本文從Barreto［18］整理的選址-路徑問(wèn)題標(biāo)桿數(shù)據(jù)集中選取具有代表性的10組數(shù)據(jù)對(duì)所設(shè)計(jì)的算法進(jìn)行驗(yàn)證，并與其他常見(jiàn)算法比較分析，結(jié)果如表4所示.

從表4可見(jiàn)，本文所設(shè)計(jì)的算法在求解過(guò)程中存在概率突變的可能性，對(duì)某些規(guī)模較小問(wèn)題的求解可能會(huì)耗費(fèi)很多時(shí)間，甚至在系統(tǒng)設(shè)定的時(shí)間范圍并沒(méi)有找到全局最優(yōu)解.相反，有的規(guī)模較大的問(wèn)題卻可能在很短時(shí)間內(nèi)找到全局最優(yōu)解.很明顯，突變概率的存在可能會(huì)給算法的公平性埋下隱患.雖然如此，通過(guò)與其他3類算法以及已知最優(yōu)解進(jìn)行比較可知，本文設(shè)計(jì)算法的各項(xiàng)指標(biāo)總體表現(xiàn)良好.在Gaskell67-21*5和Gaskell67-22*5兩個(gè)算例中，本文算法所得結(jié)果與最優(yōu)解完全一致，進(jìn)一步驗(yàn)證了表4中運(yùn)算結(jié)果的科學(xué)性和有效性.

4結(jié)論與展望

傳統(tǒng)混合自適應(yīng)遺傳算法在解決單一的選址、路徑問(wèn)題時(shí)具有較好的效果，但在處理集配一體化背景下選址-路徑集成問(wèn)題時(shí)，算法中交叉及變異過(guò)程的不足之處就會(huì)顯現(xiàn)出來(lái).本文將大規(guī)模鄰域搜索算法的破壞、重組策略引入傳統(tǒng)混合自適應(yīng)遺傳算法中代替原有的交叉、變異過(guò)程，根據(jù)這一思想重新設(shè)計(jì)了模型及算法.在此基礎(chǔ)上，以物流企業(yè)城市內(nèi)物流網(wǎng)絡(luò)規(guī)劃為例，選取4個(gè)中轉(zhuǎn)站、10個(gè)服務(wù)點(diǎn)及4臺(tái)運(yùn)輸車輛，設(shè)計(jì)了4條車輛行進(jìn)路線，生成模擬數(shù)據(jù)進(jìn)行計(jì)算.結(jié)果表明：利用改進(jìn)后的算法進(jìn)行求解，可以將客戶滿意度從默認(rèn)的0.9提升至0.918.最后選取已知標(biāo)桿數(shù)據(jù)對(duì)優(yōu)化算法的有效性進(jìn)行了驗(yàn)證，經(jīng)過(guò)運(yùn)算可知，本文算法與已知最優(yōu)解基本完全一致，這個(gè)結(jié)論進(jìn)一步證明了前文算例計(jì)算結(jié)果的科學(xué)性和有效性，說(shuō)明本文所設(shè)計(jì)的優(yōu)化算法能夠進(jìn)一步提高物流效率，降低物流成本，提高客戶滿意度，為物流企業(yè)選址路徑規(guī)劃決策提供指導(dǎo)意見(jiàn).

本文在進(jìn)行算例分析時(shí)所用的模擬物流網(wǎng)絡(luò)結(jié)構(gòu)規(guī)模較小，所采用的模擬數(shù)據(jù)量較少，因此，優(yōu)化后的算法在對(duì)大規(guī)模物流網(wǎng)絡(luò)計(jì)算時(shí)在效率和收斂性方面的表現(xiàn)需要進(jìn)一步進(jìn)行驗(yàn)證.此外，本文算法僅適用于單級(jí)選址-路徑的規(guī)劃設(shè)計(jì)，無(wú)法實(shí)現(xiàn)對(duì)兩級(jí)選址-路徑的規(guī)劃設(shè)計(jì).下一步將重點(diǎn)從大規(guī)模物流網(wǎng)絡(luò)及兩級(jí)選址-路徑規(guī)劃的思路出發(fā)進(jìn)行研究.

參考文獻(xiàn)：

［1］黃凱明，盧才武，連民杰.三層級(jí)設(shè)施選址-路徑規(guī)劃問(wèn)題建模及算法研究［J］.系統(tǒng)工程理論與實(shí)踐，2018，38（3）：743-754. DOI： 10.12011/1000-6788（2018）03-0743-12.

［2］湯杼彬.基于和聲搜索算法的多層級(jí)物流中心 選址問(wèn)題［J］.物流技術(shù)，2019， 38（11）： 89-92. DOI： 10.3969/j.issn.1005-152X.2019.11.019.

［3］鄒筱，張曉寧.準(zhǔn)時(shí)達(dá)限制條件的冷鏈物流配送中心選址模型［J］.統(tǒng)計(jì)與決策，2020， 36（12）： 185-188. DOI： 10.13546/j.cnki.tjyjc.2020.12.041.

［4］田立霞，黃元生，趙恒鳳，等.均衡條件下加氫站的選址定容優(yōu)化［J］.河北大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2021， 41（3）： 245-250. DOI： 10.3969/j.issn.1000-1565.2021.03.004.

［5］韋子輝，李小陽(yáng)，王勒，等.基于自適應(yīng)Levy飛行改進(jìn)的TDOA三維定位算法［J］.河北大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2023， 43（2）： 207-215. DOI： 10.3969/j.issn.1000-1565.2023.02.013.

［6］DANTZIG G B， RAMSER J H. The truck dispatching problem［J］. Manag Sci， 1959， 6（1）： 80-91. DOI： 10.1287/mnsc.6.1.80.

［7］馬貴平，潘峰.基于改進(jìn)蟻群算法的物流運(yùn)輸路徑研究［J］.計(jì)算機(jī)工程與科學(xué)， 2020， 42（3）： 523-528. DOI： 10.3969/j.issn.1007-130X.2020.03.019.

［8］濮明月，張彥如.基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化方法［J］.吉林化工學(xué)院學(xué)報(bào)， 2021， 38（5）： 90-94. DOI： 10.16039/j.cnki.cn22-1249.2021.05.019.

［9］夏強(qiáng)，周健勇.基于MATLAB軟件的運(yùn)輸路徑優(yōu)化研究［J］.物流科技， 2020， 43（10）： 97-100. DOI： 10.13714/j.cnki.1002-3100.2020.10.024.

［10］王祺，肖青.模糊需求下的多中心冷鏈配送車輛路徑問(wèn)題［J］.計(jì)算機(jī)工程與應(yīng)用， 2023， 59（23）： 341-350. DOI： 10.3778/j.issn.1002-8331.2208-0143.

［11］MARANZANA F E. On the location of supply points to minimize transportation costs［J］. IBM Syst J， 2010， 2（2）： 129-135. DOI： 10.1147/sj.22.0129.

［12］王萬(wàn)良，朱文成，趙燕偉.基于全局邊緣排序的超啟發(fā)算法在綠色物流選址—路徑優(yōu)化問(wèn)題中的應(yīng)用［J］.計(jì)算機(jī)集成制造系統(tǒng)， 2020， 26（4）： 1097-1107. DOI： 10.13196/j.cims.2020.04.023.

［13］劉凡，張惠珍，周迅.帶模糊需求的開(kāi)放式選址路徑問(wèn)題的混合離散蘑菇繁殖算法［J］.計(jì)算機(jī)應(yīng)用研究， 2021， 38（3）： 738-744， 750. DOI： 10.19734/j.issn.1001-3695.2020.02.0023.

［14］周迅，張惠珍.求解開(kāi)放式選址路徑問(wèn)題的離散煙花算法［J］.軟件導(dǎo)刊， 2021， 20（3）： 43-50. DOI： 10.11907/rjdk.202389.

［15］張得志，張湘鵬，王潤(rùn)澤，等.基于兩階段的超大型城市物流網(wǎng)絡(luò)選址與服務(wù)路徑優(yōu)化［J］.鐵道科學(xué)與工程學(xué)報(bào)， 2023， 20（4）： 1270-1279. DOI： 10.19713/j.cnki.43-1423/u.t20220845.

［16］陳麗萍，苑侗侗，楊文柱，等.基于模板更新的深層孿生網(wǎng)絡(luò)跟蹤算法［J］.河北大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2022， 42（2）： 217-224. DOI： 10.3969/j.issn.1000-1565.2022.02.016.

［17］尹博然，馬俊，陳博行，等.基于未覆蓋頂點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化［J］.河北大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2023， 43（5）： 553-560. DOI： 10.3969/j.issn.1000-1565.2023.05.015.

［18］BARRETO S S. Analysis and modeling of Location-routing problems［D］. Aveiro：University of Averiro，Portugal，2004.

（責(zé)任編輯：王蘭英）