任宗偉，錢志軍，鄭瑋，蒲煒，張寧，祁彬彬

質(zhì)量體積雙約束下車輛裝載與配送路徑聯(lián)合優(yōu)化研究

任宗偉1*，錢志軍2，鄭瑋2，蒲煒3，張寧3，祁彬彬2

（1.哈爾濱商業(yè)大學(xué) 管理學(xué)院，哈爾濱 150028；2.昆侖數(shù)智科技有限責(zé)任公司，北京 100000； 3.中國石油天然氣股份有限公司河北銷售分公司，石家莊 050000）

針對質(zhì)量與體積共同限制的配送路徑問題，綜合考慮訂單不可拆分、貨物的體積等約束，構(gòu)建包含路徑最短和裝載率最高雙目標(biāo)的車輛裝載與配送路徑聯(lián)合優(yōu)化模型。在車輛路徑優(yōu)化模型的求解方面，首先利用聚類算法對配送區(qū)域進(jìn)行劃分，然后通過車輛的載質(zhì)量判斷是否能進(jìn)行站點(diǎn)貨物的配送，最后利用遺傳算法求得最優(yōu)路徑。在三維裝載模型的求解上使用貪心算法和基于塊的啟發(fā)式算法，解決了貨物的裝箱問題?；谀彻揪唧w實(shí)例對模型與算法的可行性進(jìn)行了驗(yàn)證，優(yōu)化后配送的車輛減少了1輛，配送距離減少了154.247 km，平均裝載率達(dá)到了93.89%，節(jié)省了企業(yè)的配送成本。所構(gòu)建的模型以及求解的算法可以提高裝載率和配送效率，為解決車輛裝載與配送路徑聯(lián)合優(yōu)化問題提供理論依據(jù)。

路徑優(yōu)化；遺傳算法；三維裝載；基于塊的啟發(fā)式算法

根據(jù)2022年的最新通報(bào)，我國物流受疫情影響態(tài)勢逐漸減小，現(xiàn)已逐漸恢復(fù)，社會物流逐漸增長。其中在運(yùn)輸方面為9.55萬億元，由此可見運(yùn)輸在人們的日常生活中占有很大的比重。隨著經(jīng)濟(jì)的快速發(fā)展，配送占領(lǐng)著重要的地位，在配送形式、配送路徑、配送時間等方面都要進(jìn)行具體合理的安排與規(guī)劃。但大多數(shù)的企業(yè)或物流公司尚未形成完整的配送體系，運(yùn)輸、倉儲、銷售等都存在極大的問題，深深地影響著企業(yè)的發(fā)展。想要降低企業(yè)的運(yùn)輸成本，促進(jìn)企業(yè)的發(fā)展，其中一個重要的措施是合理規(guī)劃配送路徑和車輛裝載?，F(xiàn)大多數(shù)企業(yè)在配送貨物時僅僅依靠人為經(jīng)驗(yàn)和貨物的緊急程度進(jìn)行配送，效率較低，如出現(xiàn)緊急情況也無法有效調(diào)動機(jī)動人員和車輛，經(jīng)常容易出現(xiàn)紕漏，需要花費(fèi)較多的人力成本和時間成本。現(xiàn)階段考慮路徑優(yōu)化時同時考慮裝箱問題的情況較少，如何在滿足盡可能多的裝箱基礎(chǔ)上優(yōu)化配送路徑，仍然是值得研究的現(xiàn)實(shí)問題。

車輛路徑問題（Vehicle Routing Problem，VRP）由Dantzig等[1]于1959年首次提出，現(xiàn)已成為運(yùn)籌學(xué)中一類經(jīng)典的組合優(yōu)化問題。隨著實(shí)際需求的不斷變化，各種各樣的VRP一直在出現(xiàn)，并不斷地發(fā)展。Agárdi等[2]提出了一種通用的VRP模型，并通過案例加以證明。在解決VRP問題時，Joanna等和Olaniyi等[3-4]討論了遺傳算法解決VRP問題。容量約束的車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）是車輛路徑問題的拓展問題[5]，針對CVRP問題，Simensen等[6]提出了一種混合元啟發(fā)式算法解決CVRP問題。梁彪等[7]提出了“一種求解CVRP問題的遺傳蟻群融合算法”，為解決帶容量約束的車輛路徑優(yōu)化問題提供了一種解決辦法。針對大規(guī)模的多倉庫多車型車輛路徑問題（Multi-Depot Heterogeneous Fleet Vehicle Routing Problem，MDHFVRP），多數(shù)研究采取先聚類再優(yōu)化的求解思路，此種方法可以縮小問題規(guī)模和降低求解難度。例如，Thangiah等[8]利用遺傳算法進(jìn)行客戶分群，將問題轉(zhuǎn)變?yōu)槁眯猩虇栴}，然后通過插入啟發(fā)式算法求解旅行商問題。Luo等[9]則改進(jìn)了蛙跳算法，對客戶聚類后再進(jìn)行優(yōu)化，然后對總體進(jìn)行調(diào)整以生成新的聚類，直到滿足設(shè)定的收斂標(biāo)準(zhǔn)為止，該方法被證明可以用來求解大規(guī)模的多車場車輛路徑問題。

針對三維裝載問題，王超等[10]提出三維裝載與CVRP聯(lián)合多目標(biāo)優(yōu)化問題（3LCVRPMO）模型，該模型在三維裝載約束下，CVRP問題（3LCVRP）的基礎(chǔ)上，考慮了配送車輛數(shù)目及路徑總距離2個目標(biāo)函數(shù)，在權(quán)衡裝箱和路徑優(yōu)化2個優(yōu)化過程的基礎(chǔ)上，構(gòu)建了多階段/兩層混合算法架構(gòu)（MSOTLH）及其算法，并對路徑優(yōu)化偏好的3LCVRPMO問題進(jìn)行求解。那日薩等[11]針對7種現(xiàn)實(shí)約束的集裝箱三維多箱異構(gòu)貨物裝載優(yōu)化問題，提出了一種基于“塊”和“空間”的啟發(fā)式搜索算法，并基于Net平臺開發(fā)了一款3D裝箱布局優(yōu)化可視化軟件，已在相關(guān)物流企業(yè)中得到推廣應(yīng)用，驗(yàn)證了算法的實(shí)用性。多數(shù)學(xué)者通過先聚類后裝載來提升車輛的裝載率[12-13]，為三維裝載約束下的路徑優(yōu)化提供了決策參考和方法支持。王勇等[14]設(shè)計(jì)了集成k-means時空聚類的Clarke-Wright-非支配排序遺傳算法，為求解三維裝載路徑優(yōu)化問題提供了方法。崔會芬等[15]探討了三維裝箱約束下的車輛路徑優(yōu)化問題，引入多種約束，采用遺傳算法進(jìn)行求解，提高了物流配送效率，降低了配送成本。

本文在車輛路徑優(yōu)化模型的基礎(chǔ)上增加三維裝載約束限制，考慮帶三維裝載的路徑優(yōu)化模型，建立質(zhì)量體積雙約束的路徑優(yōu)化模型以及車輛的三維裝載模型，并結(jié)合具體實(shí)例對模型和算法的可行性進(jìn)行分析。利用聚類算法對站點(diǎn)進(jìn)行分區(qū)，在遺傳算法求解過程中調(diào)用求解三維裝載的貪心算法和基于塊的啟發(fā)式算法，統(tǒng)籌進(jìn)行三維裝載和規(guī)劃路徑。

1 問題描述

首先已知配送中心和各個配送站點(diǎn)的位置信息、各個站點(diǎn)的需求量信息，其中配送中心有一定數(shù)量的車可用于配送，同時配送中心只有一種車型用于配送；已知車輛的載質(zhì)量和容量，在配送過程中每個車次所走路線裝載的貨物總質(zhì)量不能超過車的最大載質(zhì)量，同時每個車次所走路線裝載的貨物總體積不超過車輛容積，每個站點(diǎn)只被服務(wù)一次，在某一時刻所有負(fù)責(zé)配送的車同時從配送中心出發(fā)，分別完成各自配送任務(wù)之后回到配送中心。在車輛的裝箱問題上要求把一定數(shù)量的貨物放入車廂中，使得每個車廂中的貨物體積之和不超過車輛容量，并使車輛數(shù)量最少?；谝陨蠗l件，設(shè)計(jì)一個最優(yōu)的方案，使得車輛配送總路線最短（如圖1所示）。針對該問題，建立了路徑優(yōu)化模型和三維裝載模型，路徑優(yōu)化模型的目標(biāo)函數(shù)為車輛行駛的總距離最短，約束條件在經(jīng)典VRP問題的基礎(chǔ)上添加車載質(zhì)量約束和容量約束。三維裝載模型為個直方體貨箱在不相互干涉的情況下盡可能多地裝入貨車車廂內(nèi)，使貨車車廂的空間裝載率最高。將三維裝載模型與路徑優(yōu)化模型相融合，即在滿足裝箱約束的前提下，盡可能使車輛裝更多的站點(diǎn)的貨物，使配送車輛的總行駛距離最短，具體描述見圖2。

圖1 車輛配送路徑問題描述

圖2 車輛路徑優(yōu)化與三維裝載相融合描述

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

2.1 模型假設(shè)

根據(jù)現(xiàn)有條件，本文構(gòu)建的模型做出以下假設(shè)：

假設(shè)1：配送中心庫存量可滿足所有客戶需求，且僅有一個配送中心。

假設(shè)2：配送中心只有一種車型的車，車輛數(shù)足夠完成配送任務(wù)。

假設(shè)3：車輛從配送中心出發(fā)，完成配送任務(wù)后再返回配送中心。

假設(shè)4：客戶的需求不可分割，每個客戶只能被一輛車服務(wù)，且只能被服務(wù)一次。

假設(shè)5：所有的客戶位置已知，車輛都可以配送到。

假設(shè)6：配送車輛只承擔(dān)送貨任務(wù)，不承擔(dān)取貨，配送完成后車輛返回配送中心。

假設(shè)7：配送車輛在路上不存在交通擁堵情況。

假設(shè)8：所有車輛的實(shí)際載重不能超過其額定載重。

假設(shè)9：所有車輛的實(shí)際載貨體積不能超過其額定容積。

假設(shè)10：客戶需求是靜態(tài)的，確定后將不會發(fā)生改變。

假設(shè)11：不考慮單個客戶的需求量多于一輛車的最大載質(zhì)量的情況。

假設(shè)12：不考慮單個客戶的需求貨物體積大于一輛車的最大容積的情況。

假設(shè)13：貨物都是規(guī)則物體。

假設(shè)14：貨箱必須放置在車廂內(nèi)部，不能夠超出車輛的邊界范圍。

假設(shè)15：貨箱的長寬高和質(zhì)量信息都是已知的。

假設(shè)16：實(shí)際裝載過程中貨箱與貨箱之間的裝載間隙忽略或者可以看作車廂在計(jì)算空間的時候已經(jīng)預(yù)留一部分作為裝載間隙。

假設(shè)17：貨箱不會由于堆積而產(chǎn)生變形，不是危險(xiǎn)品等特殊貨物。

2.2 參數(shù)說明

本文建立的模型中所有參數(shù)說明如下。

2.3 模型的構(gòu)建

2.3.1 路徑優(yōu)化模型

數(shù)學(xué)模型建立如下：

目標(biāo)函數(shù)：

約束條件：

2.3.2 三維裝載模型

數(shù)學(xué)模型建立如下。

目標(biāo)函數(shù)：

式（12）為車廂體積利用率最優(yōu)，即在貨車車廂中對要裝入的貨箱1,2,3, ...,P尋找一個合適的貨物裝載順序，使得裝入的貨箱體積最大，車廂的剩余空間最小；式（13）表示貨箱總體積約束；式（14）、式（15）、式（16）表示貨箱三維尺寸長寬高約束；式（17）表示貨物總質(zhì)量約束；式（18）、式（19）、式（20）表示集裝箱裝滿貨物后的重心范圍約束；式（21）表示貨物 “先進(jìn)后出”的約束。

3 算法實(shí)現(xiàn)

在總體方案設(shè)計(jì)按照車輛路徑優(yōu)化和三維裝載優(yōu)化2個任務(wù)開展研究。車輛路徑優(yōu)化方面，在考慮車型種類、商品質(zhì)量和體積的基礎(chǔ)之上構(gòu)建優(yōu)化模型；在三維裝載優(yōu)化中主要考慮的因素包括配送順序、體積、三維旋轉(zhuǎn)、質(zhì)量等。2個任務(wù)的求解算法以元啟發(fā)式算法為主?？蚣苋鐖D3所示。

圖3 技術(shù)方案的設(shè)計(jì)框架

3.1 路徑優(yōu)化算法

3.1.1 路徑優(yōu)化模型

為使路徑規(guī)劃達(dá)到最優(yōu)，配送區(qū)域劃分不僅可以節(jié)約資源，避免不必要的資源浪費(fèi)，還可以更好地滿足顧客的需求，及時高效地完成配送計(jì)劃。配送區(qū)域劃分是根據(jù)臨近原則實(shí)施的，目的就是配送達(dá)到省時、省事、省力，給予顧客最優(yōu)的體驗(yàn)，滿足顧客最大的需求。為此在解決路徑優(yōu)化問題時先使用聚類算法。K-Means聚類算法是一種迭代求解的聚類分析算法，其主要步驟如下：

1）選取個對象作為初始的聚類中心。

2）計(jì)算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。利用K-means聚類算法的特點(diǎn)依據(jù)任意便利店的經(jīng)緯度坐標(biāo)進(jìn)行聚類，對配送區(qū)域進(jìn)行劃分，以得到最優(yōu)的配送區(qū)域劃分。

本文主要運(yùn)用平均輪廓系數(shù)法來求取最優(yōu)的值。平均輪廓系數(shù)法衡量了聚類結(jié)果的質(zhì)量，即衡量每個點(diǎn)被放到當(dāng)前類簇有多合適，平均輪廓系數(shù)很高意味著聚類的結(jié)果很好。這種方法計(jì)算不同值下所有點(diǎn)的平均輪廓系數(shù)，能夠使平均輪廓系數(shù)最大的就是最優(yōu)的類簇?cái)?shù)量。

3.1.2 遺傳算法

2）適應(yīng)度的好壞直接影響著染色體的選擇，因文中的目標(biāo)函數(shù)為車輛行駛總距離最短，故設(shè)定的適應(yīng)度函數(shù)是目標(biāo)函數(shù)最大值與當(dāng)前目標(biāo)函數(shù)值的差值，當(dāng)前目標(biāo)函數(shù)值越小，差值越大，則適應(yīng)度值越大，染色體越好。

3）染色體的選擇、交叉、變異也會影響遺傳算法的結(jié)果。在染色體選擇方面，使用了二元錦標(biāo)賽法進(jìn)行選擇，通過隨機(jī)選擇2個個體，將適應(yīng)度值好的留下，重復(fù)多次，直至選擇的種群規(guī)模達(dá)到預(yù)先設(shè)定的值。

4）交叉方面選擇了OX交叉法進(jìn)行交叉，在程序編寫中，從種群中隨機(jī)選擇2個父代后，再隨機(jī)選擇2個交叉點(diǎn)，將父代的中間部分交叉生成子代。交叉后的子代會被添加到模型的解列表中，直到解的數(shù)量達(dá)到種群數(shù)量為止。

5）染色體的變異選擇了二元突變，隨機(jī)選擇2個交換位置。通過對染色體交叉、變異概率的改變，可以實(shí)現(xiàn)遺傳算法的優(yōu)化。

將聚類算法與遺傳算法融合后的流程如圖4所示。

圖4 路徑規(guī)劃程序流程

3.2 三維裝載算法

3.2.1 貪心算法

貪心算法主要是在某種意義上的局部最優(yōu)解。在三維裝載的設(shè)計(jì)上，對于裝載，首先將貨物按站點(diǎn)分類，一個站點(diǎn)的所有貨箱是一個箱子列表BoxList，每個箱子列表中所有的箱子都按照尺寸大小進(jìn)行分類，并在每一類里進(jìn)行質(zhì)量降序，以便后續(xù)同種貨物或同等大小的箱子進(jìn)行集中裝載。在裝載前需要計(jì)算貨車3個方向能放置的最大貨箱個數(shù)，判斷貨箱個數(shù)是否小于方向可放置個數(shù)，若小于則優(yōu)先方向放置貨箱，否則判斷貨箱個數(shù)是否小于×方向可放置個數(shù)，若小于則優(yōu)先×方向放置貨箱，否則優(yōu)先××方向放置貨箱，以此優(yōu)先選擇體積最大且寬最大的塊為最優(yōu)塊chosen。

3.2.2 基于塊裝載的啟發(fā)式優(yōu)化算法

簡單塊是由同一朝向的同種類型的箱子堆疊而成的，箱子和箱子之間沒有空隙，堆疊的結(jié)果必須正好形成一個長方體，其生成必須滿足3個條件：簡單塊的長寬高必須在集裝箱的體積范圍內(nèi)；簡單塊的質(zhì)量必須在集裝箱的承受范圍內(nèi)；簡單塊使用的箱子數(shù)量必須符合該類箱子的剩余數(shù)量。

在每個裝載階段中根據(jù)剩余空間大小計(jì)算能使用的所有塊，然后從中選擇一個塊裝入剩余空間，這樣在裝載時不會考慮重心約束的條件。已知由貪心算法選出最優(yōu)塊后，再判斷是否能放入Space空間。若可以放下，將塊放入并標(biāo)記貨箱的位置，插入第1塊箱子后，每插入一個塊都有3個Space空間，并且每插入一個塊都更新空間列表，對每個塊都可以按照軸旋轉(zhuǎn)，所有貨箱的重疊部分是需要判斷的，以免出現(xiàn)懸空現(xiàn)象；若不能放下就判斷是否超過oversize的20%，若超過oversize的20%就判斷是否能放下單個貨箱，若不能放置就舍棄該空間，將貨箱放入備用空間，若能放下，判斷目標(biāo)貨箱放置的位置是否可能被后面的貨物所遮擋，若被遮擋則舍棄該空間，將貨箱放入備用空間，否則放置貨箱并標(biāo)記貨箱的位置。最后判斷是否為BoxList類里面的最后一個貨箱，若不是就循環(huán)BoxList類里面的貨箱，若是就判斷是否為BoxList列表里面的最后一個類，若不是就循環(huán)BoxList列表，若是就判斷是否為最后一個站點(diǎn)，若不是就循環(huán)站點(diǎn)，若是就判斷是否能全部放入貨車，如果可以放置就返回貨車已裝載的箱子具體位置和裝載率，如果不能就舍棄當(dāng)前站點(diǎn)，再返回路徑規(guī)劃重新尋找可以再裝載的站點(diǎn)。重復(fù)上述步驟直至所有站點(diǎn)都可以裝載完成，返回最終車次。

將貪心算法與基于塊裝載的啟發(fā)式優(yōu)化算法相結(jié)合后，具體裝載流程如圖5所示。

4 算法實(shí)例

本文以某連鎖便利店為例進(jìn)行研究。該連鎖店共148個站點(diǎn)。配送中心負(fù)責(zé)向各個便利店運(yùn)送所需貨物，部分站點(diǎn)的信息如表1所示。通過對連鎖便利店的現(xiàn)狀進(jìn)行分析，發(fā)現(xiàn)在運(yùn)輸過程中存在行駛道路迂回等情況，配送時人為因素干預(yù)較大，由人工隨機(jī)配送。根據(jù)訂單表中的日期篩選訂單，根據(jù)位置信息數(shù)據(jù)找到收貨人名對應(yīng)的發(fā)貨地編碼，按某一天的車次和客戶單號編號順序計(jì)算當(dāng)前車次的行駛距離，如表2所示。

對148個站點(diǎn)地理位置進(jìn)行聚類，利用平均輪廓系數(shù)法求解的結(jié)果如圖6所示。由此可得，當(dāng)聚類數(shù)=5時最優(yōu)，最終148個站點(diǎn)共分為五部分。

將站點(diǎn)聚類后，利用遺傳算法進(jìn)行求解，設(shè)車輛的最大載質(zhì)量為5 t，用于配送的車輛足夠多，考慮貨物的體積時，基本參數(shù)設(shè)置如表3所示，迭代500次，得出的結(jié)果如圖7所示，運(yùn)行時間及運(yùn)行結(jié)果如表4所示。同理，使用另外3種啟發(fā)式算法進(jìn)行求解。4種算法的基本參數(shù)設(shè)置如表3所示，設(shè)車輛的最大載質(zhì)量為5 t，用于配送的車輛足夠多，考慮貨物的體積時，迭代500次的運(yùn)行結(jié)果如圖7所示，運(yùn)行時間及運(yùn)行結(jié)果如表4所示。

圖5 裝箱算法流程

表1 部分站點(diǎn)的坐標(biāo)

Tab.1 Coordinates of some sites

表2 車輛配送初始數(shù)據(jù)

Tab.2 Initial data of vehicle delivery

圖6 站點(diǎn)聚類結(jié)果

表3 4種啟發(fā)式算法參數(shù)說明

Tab.3 Parameters explanation of four heuristic algorithms

圖7 各算法迭代圖

通過對比4種算法的迭代圖，可以發(fā)現(xiàn)禁忌搜索算法和蟻群算法過早收斂的現(xiàn)象較為明顯，粒子群算法也有輕微的陷入局部最優(yōu)的情況，而遺傳算法一直在向全局最優(yōu)的結(jié)果收斂，雖然最后沒有穩(wěn)定在某一個數(shù)值，但是比其他3種算法更優(yōu)。

表4 4種啟發(fā)式算法運(yùn)行結(jié)果

Tab.4 Running results of four heuristic algorithms

由表4對比分析，發(fā)現(xiàn)遺傳算法計(jì)算出的車次數(shù)和路線距離都更為理想，故后續(xù)程序設(shè)計(jì)時采用遺傳算法對構(gòu)建的模型進(jìn)行求解。

表5 4種啟發(fā)式算法性能分析

Tab.5 Performance analysis of four heuristic algorithms

由表5可知，隨著求解規(guī)模的變大，遺傳算法在性能參數(shù)和運(yùn)行時間方面優(yōu)勢更加明顯。采取不同的交叉、變異概率進(jìn)行求解，所求解的行駛車次數(shù)均為23輛，具體的路線距離結(jié)果如表6所示。

表6 遺傳算法優(yōu)化結(jié)果

Tab.6 Genetic algorithm optimization results

由表6可知，當(dāng)交叉概率為0.8，變異概率為0.2時，路線距離最短。

取車輛的最大載質(zhì)量為5 t，將企業(yè)的初始數(shù)據(jù)利用路徑優(yōu)化算法與三維裝載算法優(yōu)化后形成的配送路線結(jié)果如表7所示，配送路徑如圖8所示。

4種優(yōu)化算法與三維裝載算法相結(jié)合形成的三維裝載部分展示如圖9所示。表8展示了優(yōu)化前后相關(guān)優(yōu)化結(jié)果的變化情況，其中優(yōu)化前指人工隨機(jī)配送的結(jié)果，優(yōu)化后指利用遺傳算法為主的路徑優(yōu)化算法和三維裝載算法的優(yōu)化結(jié)果。

表7 優(yōu)化結(jié)果

Tab.7 Optimal results

圖8 優(yōu)化后的路線結(jié)果

圖9 三維裝載展示

表8 優(yōu)化前后相關(guān)結(jié)果對比

Tab.8 Comparison of relevant results before and after optimization

優(yōu)化后的車輛配送區(qū)間更加聚集，由圖10可以看出遺傳算法求解的裝載率最高。由表8可知，優(yōu)化前后結(jié)果對比，配送的車輛減少了1輛，配送距離減少了154.247 km，使用聚類算法、遺傳算法、貪心算法、基于塊的啟發(fā)式算法4種算法相結(jié)合的方式，使得車輛達(dá)到了較高的裝載率，平均裝載率達(dá)到了93.89%，節(jié)省了企業(yè)的配送成本。

5 結(jié)語

配送路徑與連鎖便利店的生產(chǎn)經(jīng)營有著密不可分的關(guān)系。本文根據(jù)存在的單一車型考慮質(zhì)量與體積的配送路徑問題，建立了相應(yīng)的路徑優(yōu)化模型與三維裝載模型，并利用聚類算法和遺傳算法進(jìn)行解決，在遺傳算法求解過程中調(diào)用解決三維裝載的貪心算法與基于塊的啟發(fā)式算法，通過前后對比發(fā)現(xiàn)該算法降低了車輛的使用數(shù)量，車輛的裝載率較高，為便利店節(jié)省了配送成本，優(yōu)化的結(jié)果科學(xué)合理。

在算法的求解過程中還存在不足之處，未來三維裝載關(guān)于貨物的承重、貨物的重心與平衡以及如何優(yōu)化貨物的裝載效率和裝載時間仍需繼續(xù)研究，進(jìn)一步完善三維裝載的程序代碼，實(shí)現(xiàn)高效裝載。

[1] DANTZIG G B，RAMSER J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.

[2] AGáRDI A, KOVáCS L, BáNYAI T. Mathematical Model for the Generalized VRP Model[J]. Sustainability, 2022, 14(18): 1639.

[3] JOANNA O, ANETA P, WITOLD M. Selected Genetic Algorithms for Vehicle Routing Problem Solving[J]. Electronics, 2021, 10(24): 3147.

[4] OLANIYI O S, JAMES A K, IBRAHIM A A, et al. On the Application of a Modified Genetic Algorithm for Solving Vehicle Routing Problems with Time Windows and Split Delivery[J]. IAENG International Journal of Applied Mathematics, 2022, 52(1): 1-9.

[5] 靳康飛, 閆軍, 梁云濤. 容量約束的車輛路徑問題研究現(xiàn)狀綜述[J]. 甘肅科技縱橫, 2022, 51(10): 52-56.

JIN K F, YAN J, LIANG Y T. A Review of the Current State of Research on the Capacited Vehicle Routing Problems[J]. Scientific & Technical Information of Gansu, 2022, 51(10): 52-56.

[6] SIMENSEN M, HASLE G, ST?LHANE M. Combining Hybrid Genetic Search with Ruin-and-Recreate for Solving the Capacitated Vehicle Routing Problem[J]. Journal of Heuristics, 2022, 28(5): 653-697.

[7] 梁彪, 嚴(yán)昌龍. 一種求解CVRP問題的遺傳蟻群融合算法[J]. 中國物流與采購, 2021(24): 34-35.

LIANG B, YAN C L. A Genetic Ant Colony Fusion Algorithm for Solving CVRP Problems[J]. China Logistics & Purchasing, 2021(24): 34-35.

[8] THANGIAH S R, SALHI S. Genetic Clustering: An Adaptive Heuristic for the Multidepot Vehicle Routing Problem[J]. Applied Artificial Intelligence, 2001, 15(4): 361-383.

[9] LUO J, CHEN M R. Multi-Phase Modified Shuffled Frog Leaping Algorithm with Extremal Optimization for the MDVRP and the MDVRPTW[J]. Computers & Industrial Engineering, 2014, 72: 84-97.

[10] 王超, 金淳, 韓慶平. 三維裝載與CVRP聯(lián)合多目標(biāo)優(yōu)化問題的模型及算法[J]. 控制與決策, 2016, 31(5): 929-934.

WANG C, JIN C, HAN Q P. Model and Algorithm for Multi-Objective Joint Optimization of Three-Dimensional Loading and CVRP[J]. Control and Decision, 2016, 31(5): 929-934.

[11] 那日薩, 韓琪瑋, 林正奎. 三維多箱異構(gòu)貨物裝載優(yōu)化及其可視化[J]. 運(yùn)籌與管理, 2015, 24(4): 76-82.

NA R S, HAN Q W, LIN Z K. Optimization and Visualization of Multiple 3 D Container Loading Problem with Non-Identical Items[J]. Operations Research and Management Science, 2015, 24(4): 76-82.

[12] YAN X X, WANG G R, JIANG K S, et al. Multi-Objective Scheduling Strategy of Mine Transportation Robot Based on Three-Dimensional Loading Constraint[J]. Minerals, 2023, 13(3): 431.

[13] LIU Y, YUE Z C, WANG Y, et al. Logistics Distribution Vehicle Routing Problem with Time Window under Pallet 3D Loading Constraint[J]. Sustainability, 2023, 15(4): 3594.

[14] 王勇, 魏遠(yuǎn)晗, 蔣瓊, 等. 三維裝載約束下基于運(yùn)輸資源共享的車輛路徑問題[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2023, 29(9): 3153-3170.

WANG Y, WEI Y H, JIANG Q, et al. Vehicle Routing Problem Based on Transportation Resource Sharing under Three-Dimensional Loading Constraints[J]. Computer Integrated Manufacturing Systems, 2023, 29(9): 3153-3170.

[15] 崔會芬, 許佳瑜, 楊京帥, 等. 基于遺傳算法的3L-CVRP優(yōu)化問題研究[J]. 交通信息與安全, 2018, 36(5): 124-131.

CUI H F, XU J Y, YANG J S, et al. An Optimization of 3L-CVRP Based on a Genetic Algorithm[J]. Journal of Transport Information and Safety, 2018, 36(5): 124-131.

Joint Optimization of Vehicle Loading and Distribution Routes under Dual Constraints of Quality and Volume

REN Zongwei1*, QIAN Zhijun2, ZHENG Wei2, PU Wei3, ZHANG Ning3,QI Binbin2

(1. School of Management, Harbin University of Commerce, Harbin 150028, China; 2. Kunlun Digital Intelligence Technology Co., Ltd., Beijing 100000, China; 3. China National Petroleum Corporation Hebei Sales Branch, Shijiazhuang 050000, China)

The work aims to constructa joint optimization model for vehicle loading and distribution routes with the shortest route and the highest loading rate, taking into account constraints such as the indivisibility of orders and the volume of goods, so as to address the delivery route problem with common limitations of quality and volume. In terms of solving the vehicle route optimization model, first the clustering algorithm was used to partition the distribution area, and then the load capacity of the vehicle was used to determine whether the station goods could be delivered. Finally, the genetic algorithm was used to obtain the optimal route. The greedy algorithm and the block based heuristic algorithm were used to solve the loading problem of goods in the 3D loading model. The feasibility of the model and the algorithm was verified based on a specific example of a company. After optimization, the number of vehicles for delivery was reduced by 1, the delivery distance was reduced by 154.247 km, and the average loading rate reached 93.89%, saving the company's delivery costs. The results indicate that the constructed model and the solved algorithm can improve loading rate and delivery efficiency, providing a theoretical basis for solving the joint optimization problem of vehicle loading and distribution routes.

route optimization; genetic algorithm; 3D loading; block based heuristic algorithm

TB485.3；F540

A

1001-3563(2024)09-0232-11

10.19554/j.cnki.1001-3563.2024.09.030

2023-10-20

國家自然科學(xué)基金（71371061）；國家重點(diǎn)研發(fā)計(jì)劃（2018YFB1402500）；黑龍江省哲學(xué)社會科學(xué)資助項(xiàng)目（23RKB134）；黑龍江省自然科學(xué)基金項(xiàng)目（LH2023G009）