基于多目標優化的快遞管理系統

畢志升，林澤宇

?

基于多目標優化的快遞管理系統

畢志升，林澤宇

（廣州醫科大學基礎學院，廣州 511436）

高效的配送是快遞企業生存和發展的前提。為了有效管理快遞和規劃路徑，首先，采用用例圖進行了需求分析。接著，采用Struts2、Spring和Hibernate框架進行了系統架構設計。然后，采用序列圖和類圖對展示了路徑規劃功能的用例實現。最后，實現了一個基于多目標優化的快遞管理系統。本系統提供快遞管理、配送中心管理和路徑規劃等功能，能產生多套路徑方案，供業務管理員根據實際情況進行選擇。通過實驗，本系統運行良好，系統的設計和實現是可行有效的。

多目標優化；快遞管理；Struts2；Spring；Hibernate

0 引言

高效的配送是快遞企業生存和發展的前提。在電子商務蓬勃發展的今天，僅僅一個城市快遞企業每日需要配送的貨物就數以百萬計[1]。不合理的配送路徑將為企業帶來巨大的損失。利用計算機技術合理規劃配送路徑[2]，是快遞企業實現快捷高效配送服務的必然選擇[3]。然而，路徑規劃是一個復雜的多目標優化問題，既要考慮配送成本，又要考慮客戶滿意度，不同配送中心的貨物吞吐量和快遞員的工作量也需要均衡考慮。面對一個復雜的多目標問題，僅僅給出一套規劃方案是不合適的[4]。從不同的角度考察配送問題，給出多套可行方案供企業選擇，并在地圖中直觀地展示出來是一個理想的快遞管理系統應當具備的功能?；谶@個目的，本文提出一種基于多目標優化的快遞管理系統的設計和實現。系統除了能實現收件、預約、查詢等基本的快遞管理功能，更重要的是運用了當前多目標優化在車輛路徑問題上的最新成果，采用多目標優化技術[5]同時考察路徑規劃需要考慮的各項目標，優化從多個配送中心到客戶的配送路徑，為快遞企業提供多個可選的路徑方案并在地圖上直觀地展示。本系統可用于由一個集散中心向多個配送中心發貨從而為一個區域提供配送服務的情況，以及多車場車輛路徑問題[6]理論研究的可視化平臺。

本文第1節對系統進行需求分析；第2節進行系統設計；第3節進行系統實現；第4節是本文結論。

1 需求分析

本系統的主要使用者主要包括客戶、收件員、快遞員和業務管理員?？蛻糁饕褂孟到y的預約收件和查詢快遞等功能。收件員主要使用系統的快遞登記等功能?？爝f員主要使用系統的查詢快遞、查詢配送路徑和快遞狀態更新等功能。業務管理員主要使用快遞管理和規劃路徑等功能。由于系統需要顯示實際配送路徑，為業務管理員規劃、查詢路徑，快遞員配送快遞提供支持，需要使用外部地圖系統。

采用UML建模，可以得到本系統的整體用例圖如圖1所示，用例概要描述如表1所示。

表1 用例概要描述

Tab.1 The summary of use case

2 系統設計

本節進行系統架構設計，并對系統的規劃路徑用例進行詳細設計。

圖1 系統用例圖

2.1 系統軟件架構設計

本文的快遞系統采用B/S結構[7]，框架使用Struts2+Spring+Hibernate[8-10]，前端技術采用Java Server Pages(JSP)[11-12]。系統架構如圖2所示。

系統對業務的處理流程是：JSP負責實現頁面交互、接收請求；Struts根據配置文件將從JSP接收到的請求交給相應的Action處理；Spring的IoC容器負責創建和管理完成業務邏輯所需的Service和Dao并通過注入向Action提供服務，實現業務邏輯；Hibernate實現數據持久化。

2.2 用例實現

本節以規劃路徑用例為例，描述系統的用例實現。該用例是本系統最重要部分也是最復雜的部分。

該用例的序列圖如圖3所示。整個用例可進一步細分為三個部分。具體流程如下：

1. 獲取客戶和配送中心

（1）業務管理員激活獲取未規劃客戶和配送中心事件；

（2）JSP向CustomAction發出請求，獲取未規劃的客戶列表；

圖2 系統架構圖

（3-4）CustomAction向CustomService、CustomService向CustomDAO發送消息，獲取未規劃的客戶列表；

（5-7）返回客戶列表；

（8）JSP向DepotAction發出請求，獲取配送中心列表；

（9-10）DepotAction向DepotService、Depot-Service向DepotDAO發送消息，獲取未規劃的客戶列表；

（11-13）返回配送中心列表。

2. 規劃路徑

（1）業務管理員激活規劃路徑事件；

（2）JSP向RouteAction發出請求，規劃路徑；

（3）RouteAction向RouteService發出請求，規劃路徑；

（4）RouteService向MapSystem獲取客戶、配送中心間的距離；

（5）返回距離矩陣；

（6）RouteService向RoutePlanningSystem發送消息，規劃路徑；

（7）RoutePlanningSystem返回規劃好的路徑；

（8）RouteService向RouteDAO發送消息，持久化得到的路徑；

（9）返回持久化成功信息；

（10）RouteService向MapSystem發出請求，在地圖上畫出路徑；

（11-13）返回畫好路徑的地圖。

3. 確定方案

（1）業務管理員選擇一組路徑作為最終方案；

（2）JSP向RouteAction發出請求，選擇最終方案；

（3-4）RouteAction向RouteService、Route-Sercive向RouteDAO發送消息，保存被選擇方案的ID；

（5-7）返回執行結果，流程結束。

規劃得到的路徑以天為單位序列化后保存為文件，并在數據庫中保存規劃的時間、實施方案的編號以及文件的位置。

本系統需要使用地圖系統展示地圖、寄件人和收件人地址以及配送路徑。為驗證本系統的設計和實現，本文選用了免費開放的Baidu地圖，對應圖3中的MapSystem。若改用其他地圖產品，修改Route-Service即可。

2.3 路徑規劃

在本系統中，路徑規劃作為一個子系統處理。路徑規劃子系統將配送路徑規劃看作一個多車場車輛路徑問題[6]：有個配送中心，每個配送中心擁有一定數量容量為的車輛。有個客戶需要貨物配送。客戶可以由任意配送中心的任意車輛服務，但只能被服務一次，服務結束后車輛必須返回原配送中心。本系統運用NSGA-III[13]算法，采用文獻[14]的虛擬車場、單染色體編碼方式和Plot解碼算子，在總路徑最短、車輛數最少、車輛負載差異最小3個目標上進行路徑規劃。路徑規劃后得到一組在3個目標上的均衡解[15]。圖4是路徑規劃的示意圖：有10個客戶和3個配送中心，假設有一個虛擬配送中心對客戶進行配送，根據上述的規劃目標得到路徑集合，最后將路徑劃分到3個配送中心，得到配送方案。具體算法如下：采用長度為的整型數組對染色體進行編碼。數組以客戶的編號作為數組的元素，每個編號出現且僅出現一次。記為一條長度為的染色體，[]為其中的第個元素。這種編碼的染色體可以通過將各個路徑中的客戶按路徑順序連接后得到。如圖4所示的路徑可以通過= {2, 7, 5, 1, 4, 8, 3, 10, 9, 6}表示。因而，一條染色體就是一個配送方案。由于沒有參雜車場節點，對任意給定的客戶集合，其染色體長度固定。然而，這種編碼方式需要額外的解碼技術將分割路徑并分配到配送中心，形成實際配送路線。

圖3 規劃路徑序列圖

圖4 路徑規劃示意圖

本系統采用文獻[8]的Plot算法對染色體進行解碼，算法如算法1所示。

在解碼前，首先在首位插入一個0節點。在Plot中，[-1]保存的是從車場開始到客戶[-1]為止路徑的總長度（Line 7）。[-1]是上一路徑的最后一個客戶節點。對應的是以客戶[]為第一個客戶、以客戶[]為最后一個客戶的路徑長度，是當前嘗試構造的路徑（Line 5）。這種嘗試直到不滿足約束或沒有客戶為止（Line 13）。Line 8中if為真，則構造一條以客戶[]作為第一個客戶節點，以客戶[]為最后一個客戶節點的路徑。此時意味著新路徑較原方案（對應[]）的路徑更短，或路徑等長但能使前一條路徑服務更多的客戶，即車輛容量的利用更充分。如果if為假，意味著原方案更優，并在下一次循環（Line 4 – Line 13）中嘗試構造以[+1]作為最后一個客戶節點的路徑。保存當前節點的路徑是從中哪一個客戶開始的（Line 9）。若[] =，說明客戶[]所在的路徑是從客戶[+1]開始的。因此，當算法結束時，從后向前讀取數組，就可以實現路徑的劃分。例如= {0, 2, 5, 1, 3, 4}，= {0, 0, 0, 1, 1, 2}。從后向前讀取數組，[5] = 2，即當前最后一個客戶[5]所在的路徑是從[2+1]開始，即得到路徑0-1-3-4-0，0為虛擬車場。繼續讀取，[2] = 0，即當前最后一個客戶[2]所在的路徑是從[0+1]開始的，得到路徑0-2-5-0。至此，解碼結束。

對解碼后得到的每一條路徑，嘗試在當前尚有空余車輛的配送中心中選擇令總路徑最短的配送中心替換虛擬車場。

基于高維多目標優化算法求解MDVRP的框架如算法2所示。本系統選擇的高維多目標優化算法為NSGA-III[13]，同時優化總路徑最短、車輛數最少、車輛負載差異最小3個目標。其中，車輛負載差異最小為方案中車輛最大負載與最小負載的差值。

算法一次運行能得到多套方案，由業務管理員作最終選擇。

路徑規劃子系統的類圖如圖5所示。Route-PlanningSystem作為一個邊界類實現與路徑規劃子系統的交互，它依賴于接口PlanningInterface。類MDVRP作為接口的實現，提供實際的路徑規劃服務，并根據上述的3個目標對每一套配送方案進行評價（evaluate()方法）。另一方面，類MDVRP依賴于接口Solution和Algorithm。類Plan作為Solution的實現，保存規劃得到的路徑方案和該方案對應的目標函數值（objs）。類Route保存方案中每一條具體的配送路徑，對應一輛車。類NSGAIII是Algorithm的實現，提供路徑方案的搜索（search()方法）。采用這種設計的原因是：上述的目標函數和搜索算法可能會隨著技術的發展和企業的要求而改變。但是以路經集合為解決方案、采用特定的搜索算法規劃路徑這兩點是不變的。接口Plan-ningInterface實現了路徑規劃子系統和快遞管理系統其他部分的解耦；接口Solution實現了路徑規劃服務和路徑集合的解耦；接口Algorithm實現了路徑規劃服務和搜索算法的解耦。如此，目標函數和搜索算法的更換會變得非常簡單。進一步地，還可以設計出多套目標函數和多個搜索算法供企業自行選擇。這滿足依賴倒置原則，體現了面向接口編程的思想[16]。

圖5 路徑規劃子系統類圖

其他用例以增刪改查為主，業務邏輯較為簡單，不再詳述。

3 系統實現

本系統在MyEclipse 2015上開發，各框架版本為Struts2 2.3，Spring 4.3，Hibernate 5.2，數據庫為MySQL 5.5。

3.1 登陸

系統為管理員、收件員和快遞員提供登陸服務，通過用戶名和密碼進行登陸。圖6是登陸界面，登陸后根據各自的身份使用相應的系統功能。

圖6 登錄界面

3.2 快遞管理

快遞管理涉及快遞登記、預約、查詢、修改快遞狀態等功能。

快遞登記主要由收件員負責。圖7是快遞登陸界面，在該界面中快遞登記需要記錄寄件人、收件人的相關信息，包括地址、聯系電話、快遞大小、重量等。當輸入地址時，根據輸入的信息，調用地圖系統，在地圖上顯示具體位置?？赏ㄟ^鼠標在地圖上對位置進行調整，確保地址和位置對應，為快遞員提供便利。

登記后的快遞會生成訂單號，通過訂單號可以查詢到快遞相關信息。圖8是快遞查詢界面，界面顯示訂單的基本信息以及當前狀態，包括：待攬件、待派送、已派送等。業務管理員可在該界面中刪除待攬件的訂單、修改訂單狀態，收件員和快遞員可以修改快遞的攬件和派送狀態。

圖7 快遞登記界面

圖8 快遞查詢界面

快遞預約為客戶提供快遞登記服務，登記界面與收件員的快遞登記頁面相同。

3.3 配送中心管理

本系統對一個區域內多個配送中心的配送業務進行整體規劃，在系統中可以對添加、啟用、禁用和刪除車場。圖9是配送中心的管理界面，只有用中的車場才會被用于路徑規劃，為客戶提供服務。車場的添加與快遞添加方式類似。

圖9 配送中心管理界面

3.4 規劃路徑

本系統采用多目標優化策略進行路徑規劃，得到多套規劃方案供業務管理員進行選擇。規劃后的路徑在地圖上進行顯示，同時輸出該方案路徑長度、車輛數、各車輛最大負載差等信息，供業務管理員選擇。點擊路徑上的途徑節點可以看到該節點對應的快遞信息。通過界面上的按鈕可以瀏覽各套方案并作出最終選擇。圖10是系統在多車場車輛路徑問題的模擬數據集上的實驗結果。

4 結論

本文設計并實現了一個快遞管理系統，本系統啟基于Struts2+Spring+Hibernate框架集合，提供快遞管理、配送中心管理和路徑規劃等功能。系統的路徑規劃功能是本系統的特色之處。該功能把路徑規劃看作多目標多車場車輛路徑問題問題，并運用NSGA-III進行求解。系統能產生多套路徑方案，供業務管理員根據實際情況進行選擇。在該設計方案中，通過接口的設計，規劃策略、地圖系統的更換簡單，進一步還可以修改為多套目標函數和多個搜索算法供企業自行選擇。通過在多車場車輛路徑問題上進行實驗，本系統的設計和實現是可行的。

本系統可用于城市內多個配送中心的配送方案生成，以及多車場車輛路徑問題理論研究的可視化平臺。

圖10 規劃路徑界面

[1] 李靜. 電商發展, 廣州可謂全國獨秀; 對比深圳, 廣州GDP優勢拉大[N]. 羊城晚報, 2015-10-29(A14). LI Jing. Electric business development in Guangzhou is the best of the nation. Compare with Shenzhen, the advantage of Guangzhou GDP is growing[N]. Yangcheng evening news, 2015-10-29(A14). (in Chinese)

[2] 陳韶男. 基于云計算的企業車輛監控管理平臺的設計[J]. 軟件, 2014, 35(8): 104-109. CHEN Shao-nan. Design of monitoring and management platform for vehicles based on cloud computing[J]. Software, 2014, 35(8): 104-109. (in Chinese)

[3] 靳文利, 張建. 電子商務對傳統企業的影響及對策[J]. 軟件, 2015, 36(6): 158-162. JIN Wen-li, ZHANG Jian. Influence of E-commerce on traditional enterprise and its solutions[J]. Software, 2015, 36(6): 158-162. (in Chinese)

[4] MONTOYA-TORRES J R, FRANCO J L, ISAZA S N, et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers & industrial engineering, 2015, 79: 115-129.

[5] 毛森茂, 瞿凱平, 陳藝璇, 等. 基于灰狼多目標算法的電網碳-能復合流優化調度[J]. 新型工業化, 2016, 6(9): 11-17. MAO Sen-mao, QU Kai-ping, CHEN Yi-xuan, et al. Grey wolf multi-objective optimizer for optimal carbon-energy combined-flow[J]. The journal of new industrialization, 2016, 6(9): 11-17. (in Chinese)

[6] CALVET L, FERRER A, GOMES M I, et al. Combining statistical learning with metaheuristics for the multi-depot vehicle routing problem with market segmentation[J]. Computers & industrial engineering, 2016, 94: 93-104.

[7] 張環, 翟曉一, 閆振飛. 基于B/S的藥房管理信息系統設計與實現[J]. 軟件, 2013, 34(5): 4-5. ZHANG Huan, ZHAI Xiao-yi, YAN Zhen-fei. The design and implementation of pharmacy information management system based on B/S structure[J]. Software, 2013, 34(5): 4-5. (in Chinese)

[8] 戚娜. 基于JSP的在線考試系統的設計與實現[J]. 電子設計工程, 2015, 23(19): 121-124.QI Na. The Design and implementation of online exam-ination system based on JSP[J]. Electronic design engin-- eering, 2015, 23(19): 121-124. (in Chinese)

[9] 王雪梅, 郭麗娜. 基于SSH的在線考試系統的設計與實現[J]. 軟件, 2015, 36(12): 132-136. WANG Xue-mei, GUO Li-na. Design and implementation of online examination system[J]. Software, 2015, 36(12): 132- 136. (in Chinese)

[10] 黃洋, 宋俊德, 宋美娜, 等. 基于本體與SSH架構的異構數據集成框架的研究[J]. 軟件, 2014, 35(11): 36-41.Huang Yang, SONG Jun-de, SONG Mei-na, et al. The research of ontology and SSH architecture-based heter-oge-neous data integration framework[J]. Software, 2014, 35(11): 36-41. (in Chinese)

[11] TECH M. Automation of talent acquisition process through job application support system-a case study[J]. International journal of computer science and network security, 2014, 14(8), 53-55.

[12] 楊愛麗. 基于JSP技術的體育用品管理系統設計與實現[J]. 自動化與儀器儀表, 2016, (11): 115-118. YANG Liai. Design and implementation of sports goods management system based on JSP technology[J]. Automation & instrumentation, 2016, (11): 115-118. (in Chinese)

[13] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nond-ominated sorting approach, part I: solving problems with box cons-traints[J]. IEEE transactions on evolutionary com-p-utation, 2014, 18(4): 577-601.

[14] 鄧欣. 基于遺傳算法的多車場車輛路徑問題研究[D]. 重慶: 重慶大學, 2007. GENG Xin. Research on multiple depot vehicle routing problem based on genetic algorithm[D]. Chongqing: Chon-gqing university, 2007. (in Chinese)

[15] DEB K. Multi-objective optimization[A]. BURKE E K, KENDALL G. Search methodologies: introductory tutorials in optimization and decision support techniques [C]. USA: Springer US, 2014. 403-449.

[16] 胡洋, 何勇, 顏夢, 等. 基于MFC全成形電腦橫機花型準備系統的設計[J]. 針織工業, 2016, (5): 22-26. HU Yang, HE Yong, YAN Meng, et al. MFC-based design of the pattern preparation system for fully-fashioned comp-uterdized flat knitting Machine. Knitting Industries, 2016, (5): 22-26. (in Chinese)

Express Delivery Management System Based on Multi-objective Optimization

BI Zhi-sheng, LIN Ze-yu

(School of Basic Science, Guangzhou Medical University, Guangzhou 511436, China)

Efficient pickup and delivery are the prerequisite for the survival and development of express delivery companies. In order to effectively manage the express and planning routes, use case diagrams are firstly used for the requirements analysis. After that, the system architecture is designed with Struts2, Spring and Hibernate frameworks. Then sequence diagrams and class diagrams are used for the implementation of the route planning use case. Finally, an express management system based on multi-objective optimization is implemented. The functions of express del-ivery management, distribution center management and route planning are provided by this system, which can produce multiple planning solutions for business managers to choose according to the actual situation. The experiments show that, the system is running well, the design and implementation of this system are feasible and effective.

Multi-objective optimization; Express delivery management; Struts2; Spring; Hibernate

TP311

A

10.3969/j.issn.1003-6970.2017.04.013

國家自然科學基金(61603106)；廣州市市屬高校科研項目(1201630320)；廣州醫科大學科學科研項目(L135042)

畢志升(1983-)，男，講師，廣州醫科大學基礎學院，主要研究方向為計算智能和數據挖掘，林澤宇(1995-)，男，本科，廣州醫科大學基礎學院，主要研究方向為計算智能和數據挖掘。

本文著錄格式：畢志升，林澤宇. 基于多目標優化的快遞管理系統[J]. 軟件，2017，38（4）：68-76