王揚　張文浩

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

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

一、引言

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

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

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

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

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

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

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

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

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

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

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

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

（一）問題描述

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

1.配送中心分配貨物

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

2.配送車輛配送貨物

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

（二）模型假設(shè)

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

（三）符號定義

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

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

表1 多配送中心模型符號定義

1.固定成本

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

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

2.可變成本

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

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

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

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

2.約束條件

3.模型解釋

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

三、算法設(shè)計

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

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

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

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

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

1.狀態(tài)空間

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

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

2.動作空間

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

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

3.獎勵機(jī)制

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

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

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

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

5.結(jié)束條件

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

（二）策略設(shè)置

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

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

PPO之所以更穩(wěn)定，是因為其核心思想是在每次更新策略時，盡量減少從舊策略到新策略的變化，從而避免在學(xué)習(xí)過程中出現(xiàn)大的波動。故在構(gòu)建目標(biāo)函數(shù)時，為了體現(xiàn)出新舊策略的變化，通過KL散度來表示兩種策略的差異性。

四、案例求解

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

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

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

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

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

（三）求解結(jié)果

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

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

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

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

（四）結(jié)果分析

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

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

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

五、結(jié)論與啟示

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

參考文獻(xiàn)：

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

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

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

［4］邢少偉.考慮同時取送貨的電動無人車末端協(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］.北京：中國物資出版社，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］湯雅連， 蔡延光， 楊期江.求解帶軟時間窗多車場多車型車輛路徑問題的一種改進(jìn)蟻群算法（英文）［J］.Journal of southeast university（English Edition），2015，31（1）：94-99.

［15］葉勇，張惠珍.多配送中心車輛路徑問題的狼群算法［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