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

孫勇 喻飛根 徐昊 汪余意

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

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

一、引言

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

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

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

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

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

（一）Dijkstra算法概述

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

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

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

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

G=

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

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

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

為了對構(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ù)端、配送點以及運輸。

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

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

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

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

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

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

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

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

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

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

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

四、結(jié)語

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

參考文獻：

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

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

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

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

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

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