徐易杰,夏小云,袁建中,莊鶴林,劉會(huì)娟,劉一卓
(嘉興學(xué)院數(shù)理與信息工程學(xué)院,嘉興 314001)
隨著互聯(lián)網(wǎng)的快速發(fā)展和信息技術(shù)的不斷演變,電子商務(wù)已經(jīng)進(jìn)入密集創(chuàng)新和快速擴(kuò)張的階段,成為我國(guó)新興產(chǎn)業(yè)的重要組成部分,極大地影響和改變著人們的生活生產(chǎn)方式。在電子商務(wù)飛速發(fā)展的背景下,對(duì)快遞業(yè)的發(fā)展也產(chǎn)生了深遠(yuǎn)的影響。2018年,全國(guó)快遞包裹量突破500億件,快遞從業(yè)人員超過(guò)300萬(wàn)。根據(jù)國(guó)家郵政局統(tǒng)計(jì)數(shù)據(jù),“十二五”期間國(guó)內(nèi)快遞業(yè)務(wù)量連續(xù)5年保持50%左右的高速增長(zhǎng),郵政業(yè)發(fā)展“十三五”規(guī)劃預(yù)計(jì),2018年至2020年快遞業(yè)務(wù)量復(fù)合增長(zhǎng)率為19.5%。
然而,當(dāng)前快遞產(chǎn)業(yè)的發(fā)展仍然落后于電子商務(wù)爆炸式增長(zhǎng)的需求,不斷增長(zhǎng)的業(yè)務(wù)量給物流運(yùn)輸行業(yè)終端帶來(lái)極大的配送壓力。快遞企業(yè)也逐漸認(rèn)識(shí)到,要想獲得絕對(duì)的競(jìng)爭(zhēng)優(yōu)勢(shì),必須要在最短的時(shí)間內(nèi),花費(fèi)最低的成本,給顧客提供最好的產(chǎn)品和服務(wù)[1]。
近年來(lái),研究人員從理論的角度研究了物流配送車(chē)輛路徑問(wèn)題,如考慮交通擁堵情況[2]、考慮駕駛員滿意度[3]等。這類問(wèn)題考慮了配送過(guò)程中的一些特殊情況,但是還不能用于實(shí)際應(yīng)用中。此外,有學(xué)者研究了路徑規(guī)劃的搜索算法,分析比較了混合搜索算法[4]、遺傳算法[5]等在路徑規(guī)劃中的應(yīng)用。物流配送問(wèn)題已成為當(dāng)前物流行業(yè)研究的熱點(diǎn)領(lǐng)域,非常有必要開(kāi)發(fā)一款針對(duì)快遞員的自動(dòng)配送路徑規(guī)劃軟件,快遞員可以通過(guò)Android手機(jī)端App自動(dòng)獲取配送任務(wù),根據(jù)自動(dòng)規(guī)劃好的路線進(jìn)行快遞配送。
智慧物流配送路徑規(guī)劃問(wèn)題是物流系統(tǒng)中最受關(guān)注的問(wèn)題之一。該問(wèn)題自提出之后就受到物流科學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)等相關(guān)學(xué)科的學(xué)者和研究人員的廣泛關(guān)注,成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與熱點(diǎn)研究問(wèn)題,也是一直困擾學(xué)術(shù)界和工業(yè)界的難題。快遞配送路徑規(guī)劃問(wèn)題可以建模為一個(gè)帶約束的優(yōu)化問(wèn)題,是一類NP-難問(wèn)題,傳統(tǒng)的優(yōu)化算法設(shè)計(jì)復(fù)雜、收斂速度慢、且不易找到較優(yōu)解。路徑規(guī)劃問(wèn)題可以描述為給定一定數(shù)量的配送車(chē)輛或快遞員,以及已知的客戶數(shù)量及位置,在滿足需要的約束條件之下,要求從配送中心由快遞員將商品送到不同的客戶手中。目標(biāo)是確定一個(gè)配送方案,使得快遞員的總路程或者總代價(jià)最小?;镜奈锪髋渌吐窂揭?guī)劃問(wèn)題如圖1所示。
圖1 快遞配送路線規(guī)劃示意圖
一般的,我們可以將快遞配送路徑規(guī)劃問(wèn)題表示為一個(gè)具有n+1個(gè)節(jié)點(diǎn)的帶全完全圖G=(V,E)[6]。其中V=(0,1,2,...,N)為頂點(diǎn)集合,代表客戶或者運(yùn)輸點(diǎn)i(i=1,2,...,N)和配送中心 0,E={(i,j):i≠j}為邊的集合。每一條邊(i,j)上具有一個(gè)非負(fù)的權(quán)重dij,表示客戶i與j之間的距離??蛻鬷的需求為qi,快遞員k的最大運(yùn)輸容量為Qk。則物流配送路徑規(guī)劃問(wèn)題的數(shù)學(xué)模型描述如下。
其中,N表示客戶數(shù),K為車(chē)輛數(shù)目為由車(chē)輛k從客戶i運(yùn)輸?shù)娇蛻鬸的代價(jià)。約束以及確保每個(gè)客戶不被重復(fù)服務(wù)確保任何一條路徑的總需求不能超過(guò)快遞員的最大運(yùn)輸容量。
需要指出的是,客戶或運(yùn)輸點(diǎn)之間的為歐氏距離,可以根據(jù)配送點(diǎn)的經(jīng)緯度進(jìn)行計(jì)算。假定當(dāng)前派出五名快遞員,則需要?jiǎng)討B(tài)規(guī)劃五個(gè)配送區(qū)域。蟻群算法是一種非常有效的啟發(fā)式搜索算法,在TSP問(wèn)題、調(diào)度問(wèn)題等NP難問(wèn)題中獲得廣泛應(yīng)用[7]。系統(tǒng)中在服務(wù)器端采用蟻群算法自動(dòng)生成配送路徑,然后推送到Android端給快遞員分配相應(yīng)任務(wù)。
整個(gè)軟件主要分為以下五個(gè)模塊,每個(gè)模塊對(duì)應(yīng)的功能如下:
(1)快遞數(shù)據(jù)入庫(kù):快遞員通過(guò)快遞掃件入庫(kù)端對(duì)快遞掃碼入庫(kù),并存入訂單數(shù)據(jù)庫(kù)中。
(2)快遞地址逆編碼:把數(shù)據(jù)庫(kù)里面的快遞的地址進(jìn)行逆編碼,將地址轉(zhuǎn)換成經(jīng)緯度信息,再重新更新數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)增加經(jīng)度和緯度字段。
(3)定時(shí)任務(wù):每天在規(guī)定時(shí)間啟動(dòng)任務(wù),對(duì)當(dāng)天訂單進(jìn)行運(yùn)算。主要是通過(guò)經(jīng)緯度信息和快遞員數(shù)量并結(jié)合算法進(jìn)行運(yùn)算,得到配送順序,將配送順序以數(shù)組的方式存入數(shù)據(jù)庫(kù)中。
(4)配送信息獲取:快遞員打開(kāi)配送端App,App將通過(guò)對(duì)應(yīng)快遞員的id查詢對(duì)應(yīng)配送路線數(shù)據(jù)。
(5)路線導(dǎo)航:規(guī)劃配送路線,將已規(guī)劃好的路線推送到App上,快遞員進(jìn)行配送時(shí),App將根據(jù)已有路線自動(dòng)導(dǎo)航。
Android客戶端采用MVP架構(gòu),多模塊化設(shè)計(jì),代碼復(fù)用,降低耦合度,提高內(nèi)聚性。項(xiàng)目的邏輯流程如圖2所示。
圖2 項(xiàng)目邏輯流程圖
數(shù)據(jù)庫(kù)采用開(kāi)源MySQL數(shù)據(jù)庫(kù),在數(shù)據(jù)庫(kù)中建立四個(gè)表,分別為用戶表、總訂單表、當(dāng)天訂單表、路線規(guī)劃表。這些數(shù)據(jù)表是軟件的數(shù)據(jù)基礎(chǔ)。
(1)用戶表(user):對(duì)注冊(cè)的快遞員用戶進(jìn)行統(tǒng)一管理,包括快遞員id、用戶名、密碼、配送公司、實(shí)名及所在配送驛站地址;
(2)總訂單表(all_orders):快遞中心對(duì)當(dāng)天所有客戶下單所產(chǎn)生的快遞訂單入庫(kù)登記表,包括訂單id、訂單編號(hào)、配送地址、收件人、寄件地址、聯(lián)系方式、下單時(shí)間;
(3)當(dāng)天訂單(daily_orders):快遞員對(duì)當(dāng)天的訂單進(jìn)行掃碼入庫(kù),來(lái)源為總訂單庫(kù)。包括訂單id、訂單編號(hào)、配送地址、收件人、寄件地址、聯(lián)系方式、下單時(shí)間;
(4)路線規(guī)劃表(router_plan):后端根據(jù)當(dāng)天快遞訂單及分派快遞員進(jìn)行路線規(guī)劃,生成配送路線。包括路徑方案id、快遞員id、規(guī)劃路線數(shù)組。
本節(jié)主要介紹系統(tǒng)的具體功能。系統(tǒng)Android端主要是數(shù)據(jù)采集及數(shù)據(jù)展示。請(qǐng)求服務(wù)器數(shù)據(jù)接口,獲取對(duì)應(yīng)數(shù)據(jù),供快遞員查看。然后通過(guò)數(shù)據(jù)信息在地圖上進(jìn)行標(biāo)識(shí),快遞員只需查看對(duì)應(yīng)配送點(diǎn)的信息,包括配送路線、收貨人姓名、收貨人聯(lián)系方式等。圖3為App軟件的首頁(yè)界面,顯示當(dāng)前天氣情況,派送所在地點(diǎn)??爝f員能夠查看派單的歷史記錄,當(dāng)前的派送任務(wù)等??爝f員還能查看所在的快遞站點(diǎn),如圖4所示。服務(wù)器端根據(jù)派送的訂單情況,訂單所在位置等信息自動(dòng)計(jì)算派送路線,然后推送給Android端供快遞員接收派遞任務(wù),如圖5所示。快遞員能夠在Android端收到派送任務(wù)之后,根據(jù)規(guī)劃好的路線進(jìn)行快遞配送。
物流行業(yè)是當(dāng)下熱門(mén)行業(yè),其存在的物流配送效率低等問(wèn)題也較為突出。通過(guò)研究快遞配送路線的合理規(guī)劃,確實(shí)幫助快遞小哥尋找最優(yōu)的配送路線,解決當(dāng)前快遞不快的現(xiàn)象,減少客戶因?yàn)榘倪t到而發(fā)生的抱怨、負(fù)面情緒甚至投訴等現(xiàn)象的發(fā)生,真正幫助快遞企業(yè)樹(shù)立良好的企業(yè)形象,降低快遞成本,創(chuàng)造更多價(jià)值。實(shí)現(xiàn)了快遞員配送路線自動(dòng)規(guī)劃需求,極大地將快遞員從繁瑣的任務(wù)中解脫出來(lái)。軟件基于智能手機(jī)Android端實(shí)現(xiàn),使用非常方便。不僅能夠有效提高物流配送效率,增強(qiáng)客戶服務(wù)的滿意度,減少因客戶投訴以及客戶退貨退款的經(jīng)濟(jì)損失,緩解城市交通壓力,而且能夠減少物流配送過(guò)程給環(huán)境帶來(lái)的影響。
圖3 App軟件首頁(yè)界面
圖4 快遞站點(diǎn)列表
圖5 快遞員配送路線規(guī)劃示意圖