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

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

最優(yōu)路線

決策系統(tǒng)

Agent建模

Dijkstra算法一、引言物流配送是現(xiàn)代物流管理的一個(gè)重要環(huán)節(jié)，是實(shí)現(xiàn)電商、直播帶貨的關(guān)鍵一環(huán)和基本保證。近年來(lái)，隨著互聯(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)?，F(xiàn)在的各種物流配送系統(tǒng)中，需要采取一些配送的策略來(lái)降低貨運(yùn)費(fèi)用和行駛路程，提高物流配送速度和服務(wù)水平，物流配送策略其中車輛路線安排問(wèn)題（VRP）是物流領(lǐng)域中一個(gè)研究的熱點(diǎn)問(wèn)題。VRP屬于多約束條件的組合優(yōu)化問(wèn)題，是由Dantzig和Ramser于1959年首次提出，是運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)應(yīng)用、組合數(shù)學(xué)、圖論等學(xué)科的組合優(yōu)化問(wèn)題。當(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ā)展起來(lái)。智能體具有自治性、反應(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算法概述在物流配送過(guò)程中最重要的一環(huán)是選擇車輛最優(yōu)配送路線問(wèn)題即VRP問(wèn)題，在車輛配送過(guò)程中，耗費(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算法來(lái)求解兩點(diǎn)之間的最短路線即為物流配送最優(yōu)路線。迪杰斯特拉算法（Dijkstra）是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問(wèn)題。迪杰斯特拉算法主要特點(diǎn)是從起始點(diǎn)開(kāi)始，采用貪心算法的策略，每次遍歷到始點(diǎn)距離最近且未訪問(wèn)過(guò)的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。（二）Dijkstra算法應(yīng)用原理物流配送點(diǎn)根據(jù)服務(wù)端發(fā)來(lái)的訂單數(shù)據(jù)，解析數(shù)據(jù)得到客戶的地理位置信息，利用地圖可將配送點(diǎn)與客戶看作地圖上兩點(diǎn)，其余點(diǎn)都是各個(gè)城市所設(shè)立的快遞中轉(zhuǎn)站。將配送點(diǎn)作為起點(diǎn)、客戶作為終點(diǎn)，所以有物流配送網(wǎng)絡(luò)圖模型表示為G=<v，e>，表示起點(diǎn)、終點(diǎn)以及各個(gè)中轉(zhuǎn)站點(diǎn)，E表示每?jī)蓚€(gè)點(diǎn)之間的路線距離。以圖1物流配送模擬圖為例：G=<v，e>其中，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來(lái)更新其它頂點(diǎn)的距離;④重復(fù)步驟②和③，直到遍歷完所有頂點(diǎn)。通過(guò)以上四步即可求出v1到v6之間的最短路徑即為物流網(wǎng)絡(luò)配送過(guò)程的最優(yōu)路線。三、構(gòu)建基于Agent的物流配送決策系統(tǒng)為了對(duì)構(gòu)建基于Agent的物流配送決策系統(tǒng)，我們需要知道現(xiàn)在的網(wǎng)絡(luò)物流配送決策過(guò)程，然后從現(xiàn)有的決策系統(tǒng)中判斷哪些模塊是可以具有智能體的特性，以此構(gòu)建基于Agent的物流決策系統(tǒng)。（一）典型的網(wǎng)絡(luò)配送決策結(jié)構(gòu)典型的網(wǎng)絡(luò)配送決策過(guò)程主要分四部分：客戶端、服務(wù)端、配送點(diǎn)以及運(yùn)輸。（1）客戶端的主要任務(wù)是與客戶進(jìn)行交互，客戶在客戶端上進(jìn)行訂單的填寫以及訂單的提交，并根據(jù)客戶的應(yīng)決定是否進(jìn)行訂單的修改。在客戶端用一個(gè)客戶Agent來(lái)完成，用來(lái)響應(yīng)客戶請(qǐng)求以及向客戶反饋處理結(jié)果。（2）服務(wù)端的主要任務(wù)是分析客戶的需求信息、提取關(guān)鍵信息并廣播給各個(gè)配送點(diǎn)，然后對(duì)配送點(diǎn)反饋的結(jié)果進(jìn)行分析，尋找合適的配送點(diǎn)。如果沒(méi)有找到合適的配送點(diǎn)，則向客戶返回拒絕信息及拒絕的原因，客戶可以根據(jù)提示原因修改訂單信息繼續(xù)提交。否則向客戶返回訂單接受信息。在服務(wù)端可以使用訂單Agent和訂單分配Agent來(lái)處理，訂單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)來(lái)完成，且決策過(guò)程依賴模型庫(kù)、合作庫(kù)、知識(shí)庫(kù)等等。（4）運(yùn)輸主要是根據(jù)GPS導(dǎo)航將訂單物品通過(guò)公路、高速或空運(yùn)運(yùn)抵客戶所在城市，這部分可以使用車輛Agent來(lái)完成。典型的網(wǎng)絡(luò)配送決策過(guò)程如下圖所示：（二）基于Agent的物流配送決策系統(tǒng)通過(guò)上一節(jié)的分析，我們了解物流配送決策過(guò)程，其中許多的功能都是可以通過(guò)Agent來(lái)完成，依據(jù)圖2的決策過(guò)程以及物流配送系統(tǒng)中各個(gè)部分的職責(zé)，得到相應(yīng)的基于Agent的物流配送決策系統(tǒng)如圖3所示。系統(tǒng)中每個(gè)部分都是獨(dú)立一個(gè)功能模塊，包含了以下幾個(gè)方面：（1）用戶單元：包含用戶與下單界面，用戶在下單界面下單，服務(wù)端通過(guò)網(wǎng)絡(luò)將接受與否富人結(jié)果反饋到下單界面。（2）Agent實(shí)體單元：包含各個(gè)功能Agent實(shí)體以及Agent總控部分。具體有①Agent總控：主要負(fù)責(zé)管理系統(tǒng)中的各個(gè)功能Agent以及監(jiān)聽(tīng)系統(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ù)來(lái)進(jìn)行決策，選擇出最適合的最優(yōu)路線。在模型庫(kù)中主要模型是基于Dijkstra算法求解最短路線的模型。四、結(jié)語(yǔ)本文研究的基于Agent的物流配送最優(yōu)路線決策系統(tǒng)利