基于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)路線的決策問題?！娟P(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)濟指標依然有很好的增長?，F(xiàn)在的各種物流配送系統(tǒng)中，需要采取一些配送的策略來降低貨運費用和行駛路程，提高物流配送速度和服務(wù)水平，物流配送策略其中車輛路線安排問題（VRP）是物流領(lǐng)域中一個研究的熱點問題。VRP屬于多約束條件的組合優(yōu)化問題，是由Dantzig和Ramser于1959年首次提出，是運籌學、管理學、計算機應(yīng)用、組合數(shù)學、圖論等學科的組合優(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）是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。迪杰斯特拉算法主要特點是從起始點開始，采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節(jié)點，直到擴展到終點為止。（二）Dijkstra算法應(yīng)用原理物流配送點根據(jù)服務(wù)端發(fā)來的訂單數(shù)據(jù)，解析數(shù)據(jù)得到客戶的地理位置信息，利用地圖可將配送點與客戶看作地圖上兩點，其余點都是各個城市所設(shè)立的快遞中轉(zhuǎn)站。將配送點作為起點、客戶作為終點，所以有物流配送網(wǎng)絡(luò)圖模型表示為G=<v，e>，表示起點、終點以及各個中轉(zhuǎn)站點，E表示每兩個點之間的路線距離。以圖1物流配送模擬圖為例：G=<v，e>其中，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主要承擔尋找最優(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)中各個部分的職責，得到相應(yīng)的基于Agent的物流配送決策系統(tǒng)如圖3所示。系統(tǒng)中每個部分都是獨立一個功能模塊，包含了以下幾個方面：（1）用戶單元：包含用戶與下單界面，用戶在下單界面下單，服務(wù)端通過網(wǎng)絡(luò)將接受與否富人結(jié)果反饋到下單界面。（2）Agent實體單元：包含各個功能Agent實體以及Agent總控部分。具體有①Agent總控：主要負責管理系統(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)利