基于Agent的物流配送最優(yōu)路線決策系統(tǒng)研究

孫勇 喻飛根 徐昊 汪余意

【摘要】近年來隨著電商平臺(tái)與直播帶貨的火熱發(fā)展，直接地帶動(dòng)了中國(guó)物流行業(yè)的快速發(fā)展以及促進(jìn)行業(yè)資源的整合，提高了現(xiàn)在的物流速度。但是，現(xiàn)在的物流配送路線是由各個(gè)公司根據(jù)自己的效益所決定的，并不是最優(yōu)路線。為了解決配送的最優(yōu)路線問題，本文利用Agent的移動(dòng)性、主動(dòng)反應(yīng)性以及實(shí)時(shí)性等特點(diǎn)，構(gòu)建了基于Agent的物流配送決策系統(tǒng)，在系統(tǒng)的最優(yōu)路線決策模型中利用Dijkstra算法來求解發(fā)貨地與目的地之間的最優(yōu)路線，從而實(shí)現(xiàn)物流配送最優(yōu)路線的決策問題。

【關(guān)鍵詞】物流配送? 最優(yōu)路線? 決策系統(tǒng)? Agent建模? Dijkstra算法

一、引言

物流配送是現(xiàn)代物流管理的一個(gè)重要環(huán)節(jié)，是實(shí)現(xiàn)電商、直播帶貨的關(guān)鍵一環(huán)和基本保證。近年來，隨著互聯(lián)網(wǎng)的大力發(fā)展，電子商務(wù)得到了空前的發(fā)展。在今年疫情下，直播帶貨又將電子商務(wù)推上了一個(gè)新的高度。因此，也直接的帶動(dòng)了物流行業(yè)的迅猛發(fā)展。在今年一、二季度因疫情原因使得市場(chǎng)經(jīng)濟(jì)低迷的情況下，物流行業(yè)的經(jīng)濟(jì)指標(biāo)依然有很好的增長(zhǎng)。

現(xiàn)在的各種物流配送系統(tǒng)中，需要采取一些配送的策略來降低貨運(yùn)費(fèi)用和行駛路程，提高物流配送速度和服務(wù)水平，物流配送策略其中車輛路線安排問題（VRP）是物流領(lǐng)域中一個(gè)研究的熱點(diǎn)問題。VRP屬于多約束條件的組合優(yōu)化問題，是由Dantzig和Ramser于1959年首次提出，是運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)應(yīng)用、組合數(shù)學(xué)、圖論等學(xué)科的組合優(yōu)化問題。當(dāng)前的物流配送路線決策涉及客戶信息管理、訂單信息管理、配送點(diǎn)管理、地理位置信息管理等許多方面，體系復(fù)雜龐大。因此需要建立一個(gè)物流配送決策系統(tǒng)，管理物流系統(tǒng)中的各種數(shù)據(jù)信息，選擇配送的最優(yōu)路線。

智能體（Agent）是人工智能領(lǐng)域中一個(gè)很重要的概念，出現(xiàn)于20世紀(jì)70年代，80年代后發(fā)展起來。智能體具有自治性、反應(yīng)性、交互性、主動(dòng)性以及社會(huì)性等特征。它自身?yè)碛行袨榭刂茩C(jī)制，可根據(jù)自身狀態(tài)以及外部環(huán)境的感知，做出決策和相應(yīng)的行為;因?yàn)榫哂猩鐣?huì)性，所以它可以與其他的智能體進(jìn)行交流合作;同時(shí)可以感知所處環(huán)境信息，可以實(shí)時(shí)的做出適當(dāng)?shù)姆磻?yīng)。智能體的概念和方法不僅是計(jì)算機(jī)領(lǐng)域和人工智能領(lǐng)域研究的熱點(diǎn)，而且引起了軍事、教育、交通、物流等許多領(lǐng)域的關(guān)注和相關(guān)的應(yīng)有研究。

本文利用Agent的移動(dòng)性、主動(dòng)反應(yīng)性以及實(shí)時(shí)性等特點(diǎn)，構(gòu)建了基于Agent的物流配送決策系統(tǒng)。在系統(tǒng)的最優(yōu)路線決策模型中采用Dijkstra算法選擇最優(yōu)路線。

二、利用Dijkstra算法求解最優(yōu)路線

（一）Dijkstra算法概述

在物流配送過程中最重要的一環(huán)是選擇車輛最優(yōu)配送路線問題即VRP問題，在車輛配送過程中，耗費(fèi)的油量、花費(fèi)的時(shí)間以及高速路費(fèi)等支出與兩點(diǎn)之間的路程是具有正相關(guān)性的。故而本文選擇車輛配送最優(yōu)路線以配送點(diǎn)與客戶兩點(diǎn)之間的最短路徑為標(biāo)準(zhǔn)，即最短路線為最優(yōu)路線。決策系統(tǒng)利用圖論知識(shí)中的Dijkstra算法來求解兩點(diǎn)之間的最短路線即為物流配送最優(yōu)路線。

迪杰斯特拉算法（Dijkstra）是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是從起始點(diǎn)開始，采用貪心算法的策略，每次遍歷到始點(diǎn)距離最近且未訪問過的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。

（二）Dijkstra算法應(yīng)用原理

物流配送點(diǎn)根據(jù)服務(wù)端發(fā)來的訂單數(shù)據(jù)，解析數(shù)據(jù)得到客戶的地理位置信息，利用地圖可將配送點(diǎn)與客戶看作地圖上兩點(diǎn)，其余點(diǎn)都是各個(gè)城市所設(shè)立的快遞中轉(zhuǎn)站。將配送點(diǎn)作為起點(diǎn)、客戶作為終點(diǎn)，所以有物流配送網(wǎng)絡(luò)圖模型表示為G=，表示起點(diǎn)、終點(diǎn)以及各個(gè)中轉(zhuǎn)站點(diǎn)，E表示每?jī)蓚€(gè)點(diǎn)之間的路線距離。以圖1物流配送模擬圖為例：

G=

其中，V={v1，v2，v3，v4，v5，v6}，E={dij|1≤i，j≤6}

Dijkstra算法求解流程包含以下方面：①初始時(shí)S只包含起點(diǎn)v1;U包含除v1外的其他頂點(diǎn)，且U中頂點(diǎn)的距離為起點(diǎn)v1到該頂點(diǎn)的距離;② 從U中選出距離最短的頂點(diǎn)k，并將頂點(diǎn)k加入到S中;同時(shí)，從U中移除頂點(diǎn)k;③更新U中各個(gè)頂點(diǎn)到起點(diǎn)v1的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來更新其它頂點(diǎn)的距離;④重復(fù)步驟②和③，直到遍歷完所有頂點(diǎn)。通過以上四步即可求出v1到v6之間的最短路徑即為物流網(wǎng)絡(luò)配送過程的最優(yōu)路線。

三、構(gòu)建基于Agent的物流配送決策系統(tǒng)

為了對(duì)構(gòu)建基于Agent的物流配送決策系統(tǒng)，我們需要知道現(xiàn)在的網(wǎng)絡(luò)物流配送決策過程，然后從現(xiàn)有的決策系統(tǒng)中判斷哪些模塊是可以具有智能體的特性，以此構(gòu)建基于Agent的物流決策系統(tǒng)。

（一）典型的網(wǎng)絡(luò)配送決策結(jié)構(gòu)

典型的網(wǎng)絡(luò)配送決策過程主要分四部分：客戶端、服務(wù)端、配送點(diǎn)以及運(yùn)輸。

（1）客戶端的主要任務(wù)是與客戶進(jìn)行交互，客戶在客戶端上進(jìn)行訂單的填寫以及訂單的提交，并根據(jù)客戶的應(yīng)決定是否進(jìn)行訂單的修改。在客戶端用一個(gè)客戶Agent來完成，用來響應(yīng)客戶請(qǐng)求以及向客戶反饋處理結(jié)果。

（2）服務(wù)端的主要任務(wù)是分析客戶的需求信息、提取關(guān)鍵信息并廣播給各個(gè)配送點(diǎn)，然后對(duì)配送點(diǎn)反饋的結(jié)果進(jìn)行分析，尋找合適的配送點(diǎn)。如果沒有找到合適的配送點(diǎn)，則向客戶返回拒絕信息及拒絕的原因，客戶可以根據(jù)提示原因修改訂單信息繼續(xù)提交。否則向客戶返回訂單接受信息。在服務(wù)端可以使用訂單Agent和訂單分配Agent來處理，訂單Agent分析處理訂單信息分析、向配送點(diǎn)廣播、向客戶反饋結(jié)果以及分析配送點(diǎn)反饋的結(jié)果。訂單分配Agent主要承擔(dān)尋找最優(yōu)配送點(diǎn)任務(wù)。

（3）配送點(diǎn)的任務(wù)是可以根據(jù)GPS與GIS系統(tǒng)信息尋找配送點(diǎn)與客戶之間的最優(yōu)路線，同時(shí)對(duì)各個(gè)訂單的信息進(jìn)行跟蹤，了解配送車輛的位置并將位置反饋給客戶，客戶可以實(shí)時(shí)查看訂單的狀態(tài)，這部分需要決策系統(tǒng)來完成，且決策過程依賴模型庫(kù)、合作庫(kù)、知識(shí)庫(kù)等等。

（4）運(yùn)輸主要是根據(jù)GPS導(dǎo)航將訂單物品通過公路、高速或空運(yùn)運(yùn)抵客戶所在城市，這部分可以使用車輛Agent來完成。典型的網(wǎng)絡(luò)配送決策過程如下圖所示：

（二）基于Agent的物流配送決策系統(tǒng)

通過上一節(jié)的分析，我們了解物流配送決策過程，其中許多的功能都是可以通過Agent來完成，依據(jù)圖2的決策過程以及物流配送系統(tǒng)中各個(gè)部分的職責(zé)，得到相應(yīng)的基于Agent的物流配送決策系統(tǒng)如圖3所示。

系統(tǒng)中每個(gè)部分都是獨(dú)立一個(gè)功能模塊，包含了以下幾個(gè)方面：

（1）用戶單元：包含用戶與下單界面，用戶在下單界面下單，服務(wù)端通過網(wǎng)絡(luò)將接受與否富人結(jié)果反饋到下單界面。

（2）Agent實(shí)體單元：包含各個(gè)功能Agent實(shí)體以及Agent總控部分。具體有①Agent總控：主要負(fù)責(zé)管理系統(tǒng)中的各個(gè)功能Agent以及監(jiān)聽系統(tǒng)各個(gè)事件，若發(fā)生某種事件則可以是對(duì)應(yīng)的功能Agent活躍。②客戶Agent：響應(yīng)客戶請(qǐng)求以及向客戶反饋處理結(jié)果。③訂單Agent：分析處理訂單信息分析、向配送點(diǎn)廣播、向客戶反饋結(jié)果以及分析配送點(diǎn)反饋的結(jié)果。④訂單分配Agent：尋找最優(yōu)配送點(diǎn)。⑤車輛Agent：根據(jù)GPS與GIS將產(chǎn)品運(yùn)到客戶手中。

（3）信息提取及分析：提取客戶訂單信息的關(guān)鍵信息如家庭住址、聯(lián)系電話、聯(lián)系人等等。分析提取的關(guān)鍵信息以及系統(tǒng)其他功能模塊反饋的日志信息。

（4）決策系統(tǒng)及決策庫(kù)：決策系統(tǒng)根據(jù)模型庫(kù)推演的最優(yōu)路線以及其他的數(shù)據(jù)庫(kù)、知識(shí)庫(kù)中提供的歷史數(shù)據(jù)來進(jìn)行決策，選擇出最適合的最優(yōu)路線。在模型庫(kù)中主要模型是基于Dijkstra算法求解最短路線的模型。

四、結(jié)語(yǔ)

本文研究的基于Agent的物流配送最優(yōu)路線決策系統(tǒng)利用Dijkstra算法求解物流配送的最短路線，較為快速的為客戶以及配送點(diǎn)給出合適的配送路線。利用Agent的主動(dòng)性，移動(dòng)性等特點(diǎn)構(gòu)建了基于Agent的物流配送結(jié)構(gòu)，整合了物流配送的各節(jié)點(diǎn)，使物流配送具有系統(tǒng)性，整體性。本系統(tǒng)可以為物流配送行業(yè)提高配送效率，降低了物流配送過程的費(fèi)用，促進(jìn)了物流行業(yè)的發(fā)展，具有很廣泛的應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1]申靜.基于多Agent協(xié)商的物流配送最優(yōu)路徑選擇問題研究[J].物流技術(shù)，2014，33（11）：95-98.

[2]陳宇.基于物流配送路徑優(yōu)化問題的最優(yōu)化方法研究[J].今日南國(guó)（理論創(chuàng)新版），2008（12）：8-9.

[3]周宏，廖雪珍.基于Agent的網(wǎng)絡(luò)物流配送決策系統(tǒng)研究[J].系統(tǒng)工程與電子技術(shù)，2004（10）：1421-1425.

[4]劉小玲，李輝，郭治國(guó).基于狄克斯特拉算法的車間動(dòng)態(tài)生產(chǎn)能力評(píng)估與實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2006（12）：96-98

[5]王華.基于Dijkstra算法的物流配送最短路徑算法研究[J].計(jì)算機(jī)與數(shù)字工程，2011，39（03）：48-50.

作者簡(jiǎn)介：孫勇（1994-），男，漢族，湖北襄陽(yáng)人，中國(guó)科學(xué)院科技戰(zhàn)略咨詢研究院2019級(jí)博士在讀，武漢市中城事大數(shù)據(jù)有限責(zé)任公司，高級(jí)算法工程師，研究方向：機(jī)器學(xué)習(xí)與自然語(yǔ)言處理;喻飛根（1999-），男，漢族，湖南岳陽(yáng)人，中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院2018級(jí)本科生在讀，研究方向：智能科學(xué)與技術(shù);徐昊（1999-），男，漢族，湖北孝感人，中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院2018級(jí)本科生在讀，研究方向：自動(dòng)化;汪余意（2000-），女，漢族，湖北大冶人，中南民族大學(xué)，計(jì)算機(jī)科學(xué)學(xué)院2018級(jí)本科在讀，武漢市中城事大數(shù)據(jù)有限責(zé)任公司，工程師，研究方向：文本分析與語(yǔ)義挖掘。