王揚(yáng)　張文浩

關(guān)鍵詞：車輛路徑問題；末端物流配送；深度強(qiáng)化學(xué)習(xí)

中圖分類號(hào)：F252文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2096-7934（2024）04-0078-10

一、引言

物流是一個(gè)復(fù)合型產(chǎn)業(yè)，主要由發(fā)貨方、收貨方以及將二者聯(lián)系在一起的快遞公司組成，其中又涉及到了倉儲(chǔ)、運(yùn)輸、配送、信息共享等多個(gè)方面，是集多方面于一體的綜合性服務(wù)產(chǎn)業(yè)，對(duì)國(guó)家經(jīng)濟(jì)的發(fā)展起到了不可忽視的作用［1］。隨著社會(huì)分工的不斷細(xì)化，各個(gè)地區(qū)的經(jīng)濟(jì)往來不斷密切，經(jīng)濟(jì)結(jié)構(gòu)和產(chǎn)業(yè)結(jié)構(gòu)的調(diào)整是必然的進(jìn)程，對(duì)我國(guó)當(dāng)前的產(chǎn)業(yè)結(jié)構(gòu)進(jìn)行分析，可以得出第三產(chǎn)業(yè)已經(jīng)成為我國(guó)經(jīng)濟(jì)支柱產(chǎn)業(yè)的結(jié)論，而物流行業(yè)正是屬于第三產(chǎn)業(yè)的服務(wù)業(yè)，因此，對(duì)物流的發(fā)展進(jìn)行研究有助于我國(guó)經(jīng)濟(jì)的發(fā)展和社會(huì)的進(jìn)步［2］。1978年“物流”這一概念第一次引入我國(guó)，隨后物流產(chǎn)業(yè)不斷發(fā)展，四十余年后的今天，我國(guó)已經(jīng)成為全球物流總額最大的國(guó)家［3］，形成了一個(gè)完備的物流體系。我國(guó)物流總額不斷增加的情況，既體現(xiàn)出了物流行業(yè)高速發(fā)展的大環(huán)境，同時(shí)也在一定程度上體現(xiàn)出物流行業(yè)中龐大的成本，如果能在當(dāng)前的基礎(chǔ)上節(jié)約成本，無疑是對(duì)物流行業(yè)的正向激勵(lì)，對(duì)我國(guó)經(jīng)濟(jì)的發(fā)展也有不可忽視的作用。

小批量、多批次是目前城市末端配送的兩大特點(diǎn)，現(xiàn)有的城市物流管理體系未對(duì)末端的配送進(jìn)行統(tǒng)一規(guī)劃，導(dǎo)致參與末端配送的配送主體混雜，服務(wù)質(zhì)量參差不齊，物流資源浪費(fèi)嚴(yán)重，大量的物流配送車輛一定程度上也加劇了城市的擁堵，影響城市的交通效率［4］。如果可以對(duì)配送車輛的行駛路徑進(jìn)行優(yōu)化，無疑可以提高配送效率。

車輛路徑問題（Vehicle Routing Problem， 以下簡(jiǎn)稱“VRP”）最早在1959 年被丹齊格（Dantzig）和拉姆瑟（Ramser）提出［5］，并提出了基于線性規(guī)劃的求解過程，之后受到了眾多學(xué)者的關(guān)注，在隨后的幾十年里，VRP問題得到不斷的擴(kuò)充和發(fā)展。

自車輛路徑問題被提出后，利納斯（Linus）（1981），博?。˙odin）和戈?duì)柕牵℅olden）（1981），阿薩德（Assad）（1988），德羅謝爾（Desrochers）（1990）等許多學(xué)者從不同視角，按不同標(biāo)準(zhǔn)對(duì)該問題進(jìn)行了分類［6］。

其中，按車輛類型可分為單車型問題和多車型問題，單車型問題指所有車輛的容量都給定同一值，多車型問題指所有車輛的容量都給定不同值；按配送中心（車場(chǎng)）數(shù)目可分為單配送中心（車場(chǎng)）問題和多配送中心（車場(chǎng)）問題；按有需求點(diǎn)有無時(shí)間窗要求，可分為無時(shí)間窗問題、硬時(shí)間窗問題、軟時(shí)間窗問題。硬時(shí)間窗問題指車輛必須在時(shí)間窗內(nèi)到達(dá)，早到則等待，晚到則拒收。軟時(shí)間窗問題指車輛不一定要在時(shí)間窗內(nèi)到達(dá)，但是在時(shí)間窗外到達(dá)必須受到懲罰。

多車型車輛路徑問題是車輛路徑問題的一種擴(kuò)展。根據(jù)車輛的型號(hào)是否相同，可將車輛路徑問題分為單車型問題（Homogeneous Vehicle Routing Problem，以下簡(jiǎn)稱“VRP”）和多車型問題（Heterogeneous Vehicle Routing Problem，HVRP）［7］。戈?duì)柕牵℅olden）等人于1984年首次對(duì)不同的車輛類型建立了假設(shè)，并以此假設(shè)為約束，提出了多車型的車輛路徑問題，之后通過啟發(fā)式算法進(jìn)行了計(jì)算［8］。之后漢達(dá)（Handa）對(duì)多車型車輛路徑的數(shù)學(xué)模型進(jìn)行了拓展，并提出了一個(gè)新的下界［9］。劉（Liu）針對(duì)多車型車輛路徑問題的兩個(gè)延伸問題進(jìn)行了研究：一個(gè)是僅具有可變成本的多車型車輛路徑問題，另一個(gè)在前者的基礎(chǔ)上添加了固定成本，并設(shè)計(jì)了一種能夠同時(shí)求解這兩個(gè)變體問題的混合種群?jiǎn)l(fā)式算法［10］。

多車場(chǎng)車輛路徑問題（Multi-Depot Vehicle Routing Problem，以下簡(jiǎn)稱“MDVRP”）是基本車輛路徑問題的擴(kuò)展，指的是有數(shù)個(gè)車場(chǎng)同時(shí)對(duì)多個(gè)用戶進(jìn)行服務(wù)，要求對(duì)各車場(chǎng)的車輛和行駛路線進(jìn)行適當(dāng)?shù)陌才?，在保證滿足各用戶需求的前提下，使總的運(yùn)輸成本最低。MDVRP 最早由蒂爾曼（Tillman）于1969年采用節(jié)約算法進(jìn)行求解［11］。隨后，蒂爾曼（Tillman）等人在1972年對(duì)先前采用的節(jié)約算法進(jìn)行了改進(jìn)，再次對(duì)MDVRP進(jìn)行了更加高效的求解［12］。之后雷恩（Wren）等人通過掃描算法對(duì)先前的求解過程進(jìn)行了改進(jìn)，使得多車場(chǎng)的路徑規(guī)劃問題可求解規(guī)模擴(kuò)大到5個(gè)配送中心［13］。近年來湯雅連等人通過改進(jìn)蟻群算法對(duì)多車場(chǎng)的車輛路徑問題進(jìn)行了求解，其依靠3-opt策略來提高算法的局部搜索能力，將提出的算法應(yīng)用在3個(gè)隨機(jī)產(chǎn)生的實(shí)例中，使得精確度得以提高［14］。葉勇等人針對(duì)動(dòng)態(tài)的多車場(chǎng)模型，建立最小化車輛行駛里程的數(shù)學(xué)模型，并運(yùn)用狼群算法對(duì)其進(jìn)行求解［15］。李（Li）等人以收益最大化、成本最小化、時(shí)間最小化和碳排放最小化為目標(biāo)，設(shè)計(jì)了改進(jìn)的蟻群算法對(duì)該問題進(jìn)行求解，算法使用了一種新的方法來更新信息素，獲得了更優(yōu)的解決方案［16］。布蘭度（Brando）研究了開放多車場(chǎng)車輛路徑問題，車輛在向客戶交付貨物后不返回原車場(chǎng)，即路線的終點(diǎn)不是起點(diǎn)，提出了一種迭代局部搜索算法來求解該問題［17］。凡（Fan）等人考慮了車輛的速度、負(fù)載和道路的坡度對(duì)燃油消耗的影響，建立了車輛的固定成本、時(shí)間懲罰成本以及運(yùn)輸成本總和最小的整數(shù)規(guī)劃數(shù)學(xué)模型。

帶時(shí)間窗的車輛路徑問題（the vehicle routing problem with time windows，以下簡(jiǎn)稱“VRPTW”）是指若干車輛從配送中心出發(fā)，給周邊客戶進(jìn)行配送貨物。每個(gè)客戶都有接受服務(wù)的時(shí)間范圍，配送服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)進(jìn)行［18］。陳（Chen）等人提出一種結(jié)合了和聲搜素算法和可變鄰域下降算法求解帶時(shí)間窗的動(dòng)態(tài)車輛路徑問題［19］。尼（Ni）等人建立一種帶軟時(shí)間窗約束的模糊需求車輛路徑模型，采用改進(jìn)的遺傳算法求解該模型，得到了最優(yōu)配送路徑［20］。哈勒（Khale）等人提出了一種硬時(shí)間窗約束條件下車輛路徑問題的精確求解方法，該算法以一種緊湊的方式形成標(biāo)簽，將資源需求松弛信息整合到其中［21］。

深度強(qiáng)化學(xué)習(xí)（Deep reinforcement learning，以下簡(jiǎn)稱“DRL”）作為一種近年來應(yīng)用較多的求解方法，在處理連續(xù)問題時(shí)取得了較多的成果。其特點(diǎn)在于訓(xùn)練時(shí)間較長(zhǎng)，測(cè)試時(shí)間較短，如果能夠?qū)⒂?xùn)練好的模型應(yīng)用到現(xiàn)實(shí)車輛路徑規(guī)劃問題中，便可以提高配送效率，降低配送成本。

溫亞爾斯（Vinyals）首次將指針網(wǎng)絡(luò)與VRP問題相結(jié)合，使得在輸入維度時(shí)，不會(huì)因?yàn)榫S度限制模型的架構(gòu)，但是該研究主要是用以解決小規(guī)模的車輛路徑?jīng)Q策問題［22］。李（Li）提出了一種利用DRL解決多目標(biāo)優(yōu)化問題的想法，即將一個(gè)總的優(yōu)化目標(biāo)分解成多個(gè)子目標(biāo)，通過建立一個(gè)端到端的模型框架求解問題［23］。?？思{（Falkner）等人提出了一種雙向的搜索模型，該模型的雙向編碼器會(huì)分別學(xué)習(xí)節(jié)點(diǎn)和位置特征的嵌入，一次提高DRL在求解VRP問題時(shí)的速度和精準(zhǔn)度［24］。哈利勒（Khalil）等人提出了一種將強(qiáng)化學(xué)習(xí)與圖嵌入神經(jīng)網(wǎng)絡(luò)相結(jié)合的框架，然后通過Q-Learning來學(xué)習(xí)貪婪策略的想法，以此擴(kuò)大求解范圍［25］。

綜合來看，用深度強(qiáng)化學(xué)習(xí)來求解車輛路徑問題，其所使用的算法在求解時(shí)的策略更新幅度較大，在這種情況下，往往需要花費(fèi)較多的時(shí)間找到最優(yōu)解。因此，本文在現(xiàn)有研究的基礎(chǔ)上，建立一個(gè)多配送中心的數(shù)學(xué)模型，利用近端策略優(yōu)化算法中以新舊策略變化幅度來控制狀態(tài)更新的特點(diǎn)，求解多配送中心的末端物流配送模型。

二、多配送中心末端物流配送模型

（一）問題描述

有多個(gè)配送中心，不同配送中心有隸屬于各自配送中心的車輛，車輛首先在各自的配送中心裝載快遞包裹，包裹分配結(jié)束后，各車輛出發(fā)，按照所裝載快遞包裹的需求點(diǎn)依次進(jìn)行配送，在將所有的快遞包裹配送完成后，車輛返回各自的配送中心，具體描述如下。

1.配送中心分配貨物

在配送中心接收到需要進(jìn)行末端配送的貨物后，需根據(jù)不同快遞包裹目的地，將不同的包裹分配給不同的配送人員進(jìn)行配送。為了保證分配過程的合理性和精確性，對(duì)每個(gè)包裹分別進(jìn)行決策，選擇最合適的配送人員完成后續(xù)配送過程。

2.配送車輛配送貨物

不同配送中心有不同的配送車輛，其配送過程可以大致分為由配送中心到第一個(gè)快遞柜以及第一個(gè)快遞柜到后續(xù)快遞柜（返回配送中心）兩個(gè)過程。在完成一個(gè)地點(diǎn)的配送工作后，配送人員需要對(duì)下一個(gè)配送目的地進(jìn)行決策，以保證選擇出的路徑最合理，所有包裹配送完成后，各配送車輛返回各自的配送中心。

（二）模型假設(shè)

①配送中心和配送終點(diǎn)的坐標(biāo)位置已知。②不考慮包裹重量和體積的影響。③不考慮道路狀況、天氣條件、車輛行駛距離的影響。④所有車輛的型號(hào)都相同，配送人員的業(yè)務(wù)水平都相同。

（三）符號(hào)定義

（四）目標(biāo)函數(shù)

該模型的目標(biāo)函數(shù)為配送總成本最小，配送成本包括固定成本與可變成本。

表1 多配送中心模型符號(hào)定義

1.固定成本

固定成本是指與車輛的使用或者配送過程中固定的成本，不論行駛的距離或貨物的數(shù)量如何變化，其成本不變。包括車輛購買或租賃成本、車輛保養(yǎng)和維護(hù)成本、保險(xiǎn)費(fèi)用、車輛存儲(chǔ)和停車費(fèi)用以及管理成本。本次研究模型的固定成本僅與參與配送的車輛數(shù)目有關(guān)。

式（1）表示所有參與配送車輛的總固定成本。

2.可變成本

可變成本是指隨著配送過程而變化的成本，包括燃料成本、車輛損耗成本等。本次研究模型的可變成本僅與車輛的行駛距離有關(guān)。

式（2）表示所有參與配送車輛的可變成本。

（五）數(shù)學(xué)模型

1.目標(biāo)函數(shù)

2.約束條件

3.模型解釋

式（3）為目標(biāo)函數(shù)，表示配送總成本最小。目標(biāo)函數(shù)分為兩個(gè)部分，一個(gè)是固定成本，由配送車輛的數(shù)量決定，另一個(gè)是可變成本，由所有車輛行駛的總距離決定；式（4）表示在配送中心進(jìn)行快遞包裹分配時(shí)，對(duì)于任何一件包裹，只能且必須放在某個(gè)配送中心的某一輛車上；式（5）表示某一配送中心所有配送車輛在完成整個(gè)分配過程后，所有車輛總計(jì)裝載的包裹數(shù)量等于該配送中心的包裹總量；式（6）表示任意配送中心任意車輛的初始裝載量都要小于車輛的最大容量限制；式（7）表示車輛發(fā)車約束，當(dāng)車輛沒有裝載快遞時(shí)，該車輛不能參與配送；式（8）表示從任意配送中心出發(fā)的車輛，只能選擇一個(gè)快遞柜作為初始目的地；式（9）表示當(dāng)車輛裝載快遞時(shí)，該車輛必須發(fā)車，參與后續(xù)配送過程；式（10）表示排除某輛車決策到同一個(gè)快遞柜的情況，即避免決策出的下一目的地仍為此配送點(diǎn)；式（11）表示任意車輛由快遞柜i到j(luò)時(shí)，只有一個(gè)方向可以選擇；式（12）表示車輛在i放下的包裹數(shù)量為該車攜帶的以i點(diǎn)為終點(diǎn)的包裹數(shù)量；式（13）表示車輛在裝載貨物時(shí)，必須前往下一個(gè)快遞柜處；式（14）表示路徑連續(xù)性約束，其中n為某個(gè)快遞柜的索引且n≠i，j ；式（15）表示車輛在配送結(jié)束后需返回原配送中心；式（16）表示從任意配送中心出發(fā)的車輛在完成某次配送后，若還存在包裹，車輛繼續(xù)配送；式（17）表示在車輛返回配送中心時(shí)，只有一個(gè)方向可以選擇；式（18）至式（22）為變量約束。

三、算法設(shè)計(jì)

由于常規(guī)的啟發(fā)式算法在解決規(guī)模較大的問題時(shí)，難以適應(yīng)環(huán)境的變化，求解準(zhǔn)確度可能存在一些問題，而深度強(qiáng)化學(xué)習(xí)DRL能夠從與環(huán)境的交互中學(xué)習(xí)，并不斷優(yōu)化其決策策略。DRL通過試錯(cuò)學(xué)習(xí)并逐步改進(jìn)策略，特別適用于那些難以為人類直覺所理解的高維或連續(xù)動(dòng)作空間問題。因此本次研究考慮通過深度強(qiáng)化學(xué)習(xí)對(duì)問題進(jìn)行求解。

在深度強(qiáng)化學(xué)習(xí)中，環(huán)境和策略是兩個(gè)核心概念，它們共同定義了學(xué)習(xí)過程的動(dòng)態(tài)和目標(biāo)。環(huán)境在深度強(qiáng)化學(xué)習(xí)中扮演著至關(guān)重要的角色。它是智能體進(jìn)行學(xué)習(xí)和交互的外部世界的抽象表示。環(huán)境的特征包括狀態(tài)、動(dòng)作以及反饋機(jī)制。環(huán)境的設(shè)計(jì)需要平衡現(xiàn)實(shí)性和計(jì)算效率。過于復(fù)雜的環(huán)境可能會(huì)增加學(xué)習(xí)的難度和計(jì)算成本，而過于簡(jiǎn)單的環(huán)境可能會(huì)導(dǎo)致無法抓住現(xiàn)實(shí)問題的關(guān)鍵點(diǎn)。

策略是智能體在給定狀態(tài)下采取動(dòng)作的規(guī)則。在深度強(qiáng)化學(xué)習(xí)中，策略通常由深度神經(jīng)網(wǎng)絡(luò)表示，能夠處理高維的輸入并輸出相應(yīng)的動(dòng)作。策略可以分為確定性策略和隨機(jī)性策略，確定性策略是指對(duì)于給定的狀態(tài)，某一策略總是產(chǎn)生相同的動(dòng)作。這種策略適用于環(huán)境動(dòng)態(tài)較為確定的情況。隨機(jī)性策略是指在某些狀態(tài)下，某一策略會(huì)根據(jù)概率分布選擇動(dòng)作。這種策略有助于探索環(huán)境，防止策略陷入局部最優(yōu)解之中。

（一）環(huán)境設(shè)置

為了求解此次研究的問題，需要首先建立環(huán)境以此模擬場(chǎng)景。建立的環(huán)境里有若干個(gè)配送中心和若干個(gè)配送終點(diǎn)。每個(gè)配送中心有一定數(shù)量的車輛，這些車輛需要將包裹送達(dá)不同的配送終點(diǎn)。具體來看，這個(gè)環(huán)境包含以下五點(diǎn)內(nèi)容。

1.狀態(tài)空間

狀態(tài)空間定義了智能體可以感知的所有可能環(huán)境狀態(tài)。在深度強(qiáng)化學(xué)習(xí)中，狀態(tài)通常是高維的，可能包括圖像、傳感器數(shù)據(jù)或其他形式的觀測(cè)信息。狀態(tài)空間的大小和復(fù)雜性決定了問題的難度。例如，在棋盤游戲中，狀態(tài)空間包括棋盤上所有可能的棋子排列；在自動(dòng)駕駛車輛中，狀態(tài)空間可能包括周圍環(huán)境的高維傳感器數(shù)據(jù)。

在此次研究?jī)?nèi)容中，狀態(tài)表示當(dāng)前的配送情況。它包括每個(gè)配送終點(diǎn)已經(jīng)配送完成的快遞包裹數(shù)量，還未配送的快遞包裹數(shù)量，當(dāng)前配送車輛的位置，配送車輛已裝載的快遞包裹數(shù)量等信息。

2.動(dòng)作空間

動(dòng)作空間是強(qiáng)化學(xué)習(xí)中的一個(gè)關(guān)鍵概念，它定義了在特定環(huán)境下智能體可以執(zhí)行的所有可能的動(dòng)作。動(dòng)作空間的設(shè)計(jì)對(duì)于強(qiáng)化學(xué)習(xí)算法的性能有著重要的影響，因?yàn)闆Q定了智能體如何與環(huán)境互動(dòng)以及如何學(xué)習(xí)完成特定任務(wù)的策略。

此次研究中設(shè)置的動(dòng)作主要由兩部分組成，分別是選擇的配送終點(diǎn)和在配送終點(diǎn)放下的包裹數(shù)量。這兩個(gè)部分使得建立的模型能夠決定某一配送車輛下一個(gè)要訪問的位置和該車輛在某一配送點(diǎn)需要放下包裹的數(shù)量。

3.獎(jiǎng)勵(lì)機(jī)制

獎(jiǎng)勵(lì)機(jī)制是強(qiáng)化學(xué)習(xí)的核心，它定義了智能體接收獎(jiǎng)勵(lì)（或懲罰）的條件。獎(jiǎng)勵(lì)通常是一個(gè)數(shù)值信號(hào)，指導(dǎo)智能體學(xué)習(xí)如何改進(jìn)其行為以最大化總獎(jiǎng)勵(lì)。設(shè)計(jì)有效的獎(jiǎng)勵(lì)機(jī)制是成功應(yīng)用深度強(qiáng)化學(xué)習(xí)的關(guān)鍵，其決定了智能體的學(xué)習(xí)目標(biāo)和優(yōu)化方向。

在此次研究中，獎(jiǎng)勵(lì)的優(yōu)劣主要基于是否能有效減少車輛的行駛距離以及能否在某個(gè)配送點(diǎn)盡可能放下更多的快遞包裹。如果配送車輛選擇了合適的配送終點(diǎn)并成功放下了較多數(shù)量的包裹，那么此次動(dòng)作就會(huì)得到正獎(jiǎng)勵(lì)；如果選擇了一個(gè)配送終點(diǎn)，但在該位置沒有包裹需要被放下，或者車輛行駛距離相對(duì)較遠(yuǎn)，那么此次動(dòng)作可能會(huì)得到負(fù)獎(jiǎng)勵(lì)。

4.環(huán)境動(dòng)態(tài)

車輛在完成一個(gè)動(dòng)作后，環(huán)境的狀態(tài)也會(huì)發(fā)生變化，因此，需要把這個(gè)變化結(jié)果表示出來。如更新配送車輛的位置，計(jì)算移動(dòng)到新配送終點(diǎn)的距離，更新各配送終點(diǎn)完成與未完成的包裹數(shù)量等。

5.結(jié)束條件

根據(jù)模型中設(shè)置的約束條件，當(dāng)所有包裹都被送達(dá)后結(jié)束。

（二）策略設(shè)置

由于車輛可以選擇的配送點(diǎn)較多，且每個(gè)配送點(diǎn)的貨物需求量有有所不同，因此環(huán)境中所涉及的狀態(tài)較多，在這種情況下，求解所需的時(shí)間可能較長(zhǎng)，因此為了盡可能縮小求解時(shí)間，需要避免在探索最優(yōu)解時(shí)所產(chǎn)生的波動(dòng)，基于這種特點(diǎn)，本文考慮通過使用PPO算法來解決問題。

近端策略優(yōu)化（Proximal Policy Optimization，以下簡(jiǎn)稱“PPO”）是一種用于深度強(qiáng)化學(xué)習(xí)的優(yōu)化算法。PPO算法由OpenAI的研究人員于2017年提出，具有較易實(shí)現(xiàn)，并且在多種環(huán)境中表現(xiàn)出良好的性能的特點(diǎn)。設(shè)計(jì)此類算法的初衷是解決策略梯度方法中的一些問題，例如難以穩(wěn)定和調(diào)整的訓(xùn)練過程，防止出現(xiàn)波動(dòng)較大而結(jié)果難以收斂的情況。

PPO之所以更穩(wěn)定，是因?yàn)槠浜诵乃枷胧窃诿看胃虏呗詴r(shí)，盡量減少從舊策略到新策略的變化，從而避免在學(xué)習(xí)過程中出現(xiàn)大的波動(dòng)。故在構(gòu)建目標(biāo)函數(shù)時(shí)，為了體現(xiàn)出新舊策略的變化，通過KL散度來表示兩種策略的差異性。

四、案例求解

本章針對(duì)O1公司、O2公司、O3公司2023年某日的實(shí)際訂單數(shù)據(jù)進(jìn)行求解，分別選取3家公司各1個(gè)配送中心。

（一）案例數(shù)據(jù)

表2 包裹配送數(shù)據(jù)

（二）參數(shù)設(shè)置

設(shè)置如下參數(shù)：固定費(fèi)用，單位為元/次，取值為30；單位運(yùn)費(fèi)，單位為元/公里，取值為1.5。

（三）求解結(jié)果

經(jīng)過深度強(qiáng)化學(xué)習(xí)求解，得到的不同配送中心的車輛配送路徑如圖1至圖3所示。其配送總成本1397.88，調(diào)動(dòng)車輛24輛，總行駛距離451.92公里。

圖1 多配送中心S公司求解路徑

圖2 多配送中心Y公司求解路徑

圖3 多配送中心J公司求解路徑

（四）結(jié)果分析

在配送中心位置、配送點(diǎn)位置以及配送點(diǎn)需求量已知的情況下，本次研究通過建立車輛配送的數(shù)學(xué)模型，進(jìn)而將數(shù)學(xué)模型轉(zhuǎn)化為深度強(qiáng)化學(xué)習(xí)的求解模型，實(shí)現(xiàn)了對(duì)多配送中心車輛配送問題的求解。

由以上車輛配送路徑圖中可以看出，在求解出的路徑中，配送點(diǎn)之間間隔距離較小時(shí)，能夠保證車輛可以通過較少的配送距離完成較多快遞包裹的配送任務(wù)；同時(shí)線路交叉情況較少，在這種情況下提高了避免了配送車輛走重復(fù)的路線的可能，減少了車輛的行駛距離。車輛的配送路徑也較為合理，所規(guī)劃的路徑連續(xù)性強(qiáng)，基本避免了配送車輛出現(xiàn)大距離折返的情況。

同時(shí)也可以發(fā)現(xiàn)，在某些配送點(diǎn)，車輛配送的快遞包裹數(shù)量較少，為了配送少量包裹而行駛較遠(yuǎn)的距離，例如，1配送中心的7車前往D74配送點(diǎn)進(jìn)行配送時(shí)，僅完成了5個(gè)快遞包裹的配送任務(wù)以及2配送中心的2車在前往D78配送點(diǎn)進(jìn)行配送時(shí)，僅僅為了完成7個(gè)包裹的配送任務(wù)，就付出了較大的距離成本，這種配送方式顯然“性價(jià)比”不高，無疑提高了配送成本。

五、結(jié)論與啟示

本文基于多配送中心的車輛路徑問題，建立了以包裹狀態(tài)為研究對(duì)象的數(shù)學(xué)模型，設(shè)計(jì)了深度強(qiáng)化學(xué)習(xí)中的環(huán)境狀態(tài)，并以PPO為策略網(wǎng)絡(luò)對(duì)案例進(jìn)行求解，最終求解結(jié)果表明，以深度強(qiáng)化學(xué)習(xí)結(jié)合不同包裹的配送狀態(tài)對(duì)問題進(jìn)行求解這一思路具有可行性，所求解出的車輛配送路徑較為合理，基本沒有出現(xiàn)車輛繞路行駛的情況。另外針對(duì)某些配送點(diǎn)配送包裹數(shù)量較少的問題，后續(xù)還需針對(duì)此方向進(jìn)行擴(kuò)展研究。

參考文獻(xiàn)：

［1］趙林度.中國(guó)物流研究現(xiàn)狀及發(fā)展趨勢(shì)［J］.物流研究，2020（1）：1-10.

［2］王珊珊.制度變遷視角下中國(guó)物流行業(yè)發(fā)展政策演變研究［D］.北京：北京郵電大學(xué)，2021.

［3］魏際剛.中國(guó)物流業(yè)發(fā)展的現(xiàn)狀、問題與趨勢(shì)［J］.北京交通大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2019，18（1）：1-9.

［4］邢少偉.考慮同時(shí)取送貨的電動(dòng)無人車末端協(xié)同配送研究［D］.重慶：重慶郵電大學(xué)，2021.

［5］DANTZIG G B， RAMSER J H.The truck dispatching problem.［J］.Management science 2020，6（1），80-89.

［6］李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法［M］.北京：中國(guó)物資出版社，2001.

［7］陳君蘭，葉春明.物流配送車輛調(diào)度問題算法綜述［J］.物流科技，2012，35（3）：8-12.

［8］史春燕，黃輝.車輛路徑問題：研究綜述及展望［J］.物流科技，2014，37（12）：75-77.

［9］GOLDEN B， ASSAD A， LEVY L， et al.The fleet size and mix vehicle routing problem［J］.Pergamon， 1984， 11（1）：49-66.

［10］HANDE Y.Formulations and alid inequalities for the heterogeneous vehicle routing problem［J］.Mathematical programming，2006，106（2）：365-390.

［11］TILLMAN F A.The multipl terminal delivery problem with probabilistic demands［J］.Transportation science，1969，3（3）：192-204.

［12］TILLMAN F A， CAIN T M.An upperbound algorithm for the single and multiple terminal delivery problem［J］.Management science，1972，18（11）：664-682.

［13］GOLDEN B L， MAGNANTI T L， NGUYEN H Q.Implementing vehicle routing algorithms［J］.Networks，1977，7（2）：113-148.

［14］湯雅連， 蔡延光， 楊期江.求解帶軟時(shí)間窗多車場(chǎng)多車型車輛路徑問題的一種改進(jìn)蟻群算法（英文）［J］.Journal of southeast university（English Edition），2015，31（1）：94-99.

［15］葉勇，張惠珍.多配送中心車輛路徑問題的狼群算法［J］.計(jì)算機(jī)應(yīng)用研究，2017，34（9）：2590-2593.

［16］LI Y， SOLEIMANI H， ZOHAL M.An improved ant colony optimization algorithm forthe multi-depot green vehicle routing problem with multiple objectives［J］.Journal of cleaner production，2019，227：1161-1172.

［17］BRANDO J.A memory-based iterated local search algorithm for the multi-depotopen vehicle routing problem［J］.European journal of operational research，2020，284（2）：559-571.

［18］FAN H， ZHANG Y， TIAN P， et al.Time-dependent multi-depot green vehiclerouting problem with time windows considering temporal-spatial distance［J］.Computersand operations research，2021：105211.

［19］OLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints［M］.Informs，1987.

［20］CHEN S F， CHEN R， GAO J， et al.A modified harmony search algorithm for solving the dynamic vehicle routing problem with time windows［J］.Scientific programming，2017.

［21］NI S Q.Fuzz demand vehicle routin problem with soft time window based on genetic algorithm［J］.Management sciencean engineering，2018，12（3）.

［22］SILVER D， HUANG A， MADDISON C J， et al.Mastering the game of go with deep neural networks and tree search［J］.Nature，2016，529（7587）：484-489.

［23］VINALYS O，F(xiàn)ORTUNATO M，JAITLY N.Pointer net-works［J］.Advances in neural information processing systems，2015.

［24］LI K， ZHANG T， WANG R.Deep reinforcement learning for multi-objective optimization［J］.IEEE transactions on cybernetics，2020，51（6）：3103-3114.

［25］FALKNER J K，THYSSENS D，SCHMIDT T L.Large neighborhood search based on neural construction heuristics［J］.Computer science，2022，2.

Research on Terminal Logistics Distributionwith Multiple Distribution Centers

WANG Yang，ZHANG Wen-hao

（Beijing University of Technology， Beijing 100124）

Abstract：The terminal logistics distribution process is the most complex one for the participating parties， and its distribution cost and efficiency are closely related to the logistics company and customers.This paper focuses on the logistics distribution situation of multiple distribution centers， with the goal of minimizing distribution costs， and establishes a logistics distribution mathematical model.Then， by designing deep reinforcement learning algorithms， a learning environment is established， and the case is solved to obtain the driving path of distribution vehicles.The results show that using deep reinforcement learning to solve the vehicle routing problem is highly feasible.

Keywords：vehicle routing problem;terminal logistics distribution;deep reinforcement learning