基于貪心算法的物流配送系統的設計與實現

趙長鮮 方木云

摘? 要：物流行業的發展使得越來越多的物流系統涌現。針對目前物流系統在配送過程中存在路徑選擇問題，設計與實現了基于貪心算法的物流配送系統。該系統利用貪心算法自動選擇最短配送路徑，簡單快捷。使用eclipse作為開發環境，MySQL作為后臺數據庫，采用Spring、SpringMVC、MyBatis整合框架進行開發，實現了用戶管理、路線制定、訂單管理等功能。

關鍵詞：物流;貪心算法;SSM

中圖分類號：TP311? ? ?文獻標識碼：A

Abstract： The development of the logistics industry brings out increasing logistics systems.Aiming at the path selection problem in the process of distribution in current logistics systems，the study designs and implements a logistics distribution system based on greedy algorithm.The system uses greedy algorithm to automatically select the shortest delivery path，which is simple and fast. The system uses eclipse as the development environment，applies MySQL as the background database， and adopts Spring，Spring MVC and MyBatis as the integrated framework to implement the development，which successfully realizes the functions of user management，route formulation， order management，etc.

Keywords： logistics; greedy algorithm; SSM

1? ?引言（Introduction）

隨著科技的進步，物流行業的發展日新月異，越來越多的物流系統也隨之出現。這些物流系統都竭盡可能地為客戶提供優質的服務，提高客戶的滿意程度。與此同時物流行業也要盡可能地節約成本，提高自己的收益。物流配送系統針對不同權限用戶給予不同權限，妥善管理用戶信息的同時也能讓用戶查詢自己所需信息。針對不同配送點選擇不同配送路徑，有效提高公司運行效率和收益。也可以隨著用戶的增加或者配送點的擴大而及時更新數據。

從物流行業的根本需求出發，按照運輸時間最短、運輸距離最近和節約運輸成本的要求，設計了一個基于貪心算法的物流配送系統。該系統方便客戶下單，利用貪心算法來對配送路徑進行選擇，用最快的速度或者最短的時間到達配送點，方便快捷。

2? 貪心算法的簡介（Brief introduction to greedy algorithm）

貪心算法是把復雜的問題分解為多個簡易的部分且每個部分都是最優答案的問題。對于其中一個解而言，任意一個解都是對其他解的延伸，如此循環，直到獲得最終解[1]。

貪心算法總是作出在當前看來是最好的選擇，它并不從整體最優上加以考慮，貪心算法所作出的選擇只是在某種意義上的局部最優選擇[2]。貪心算法是解決較優路徑這一問題比較常用且比較優秀的一種方法。

傳統的物流配送系統并沒有對配送路徑進行優化或者選擇的優化算法較為一般。與傳統的蟻群算法、遺傳算法相比，貪心算法能更快地找到合適的配送路徑[3-7]。

3? ?系統設計（System design）

3.1? ?架構選擇

系統采用Spring、SpringMVC、MyBatis整合框架進行開發實現。

Spring：Spring是一個非侵入式的、分層的一站式輕量級開源框架。Spring的核心思想是IoC （Inversion of Control）和AOP （Aspect Oriented Programing）。Spring的特點是簡單、松耦合、可測試等。

SpringMVC：SpringMVC是Spring提供的一個輕量級Web框架。SpringMVC核心思想是Servlet。SpringMVC的特點是靈活性強、可適配、可定制等。

MyBatis：MyBatis是半自動映射的對象關系映射ORM （Object/Relational Mapping）框架。MyBatis是對jdbc的封裝，用簡單的注解或XML進行原始映射和配置。MyBatis適用于需要優化性能和復雜的項目[8，9]。

3.2? ?功能設計

基于貪心算法的物流配送管理系統功能主要體現在對訂單配送路徑的自動選擇上。當一個客戶或者管理員新建一個訂單時，需要對訂單的起始配送站和到達配送站進行選擇，然后由管理員進行審核。審核通過后會自動生成一條時間最短或者距離最短的配送路徑。客戶只能對自己的訂單進行查看，而管理員可以對所有的用戶，包括配送站管理員或者客戶進行管理，除此之外，管理員可以查看和修改所有的訂單，對訂單進行審核。對于用戶的權限，全部都是管理員進行分配的。系統還可以對配送站進行更新，可以新增配送站或者對已存在的配送站進行修改。

系統根據功能劃分可分為兩大模塊：

第一個模塊是基礎數據的管理模塊。對客戶的信息進行增、刪、改、查，包括新客戶的注冊，客戶個人信息的顯示和修改，客戶的新建，客戶的權限分配，以及所有客戶的基本信息的管理;系統所有菜單的管理，包括新建和修改。該模塊對所有的基礎信息進行管理。

第二個模塊是訂單管理模塊。該模塊首先對所有的配送站進行管理。可以對配送站進行添加或者修改，將各個配送站進行鏈接。訂單的管理包括新增訂單、管理訂單和查看訂單。

對于不同的用戶擁有不同的權限，保證了用戶信息的安全。對于系統的功能模塊如圖1所示。

4? ?數據庫設計（Database design）

系統使用Navicat Premium可視化工具對MySQL數據庫進行操作，建立了一個用于存放在系統運行中所有產生的以及所需的數據信息數據庫。

根據系統基礎數據的管理，以及訂單管理的功能進行設計，總結出數據庫設計方案。數據庫共包括七個表，包括菜單表、配送站表、配送站路線表、訂單表、訂單路線表、用戶表以及用戶菜單表。表1—表3展示了其中重要部分表字段設計。

5? ?系統功能實現（System function realization）

5.1? ?用戶管理

用戶分為管理員和客戶，不同的用戶擁有不同的權限。

管理員用戶擁有系統的所有權限，管理員登錄賬號以后進入系統會顯示系統所有菜單。

客戶所擁有的權限由系統管理員分配，客戶登錄賬號以后進入系統顯示的部分菜單是由系統管理員所授予的權限菜單。登錄界面如圖2所示。

5.2? ?配送站管理

配送站管理模塊對現有的所有配送站的詳細信息進行顯示以及管理。系統管理員可以通過配送站列表對配送站進行管理，通過新增配送站對配送站進行添加。新增配送站時需要填寫該配送站與每一個相鄰配送站的距離信息和時間信息。新增配送站界面如圖3所示。

5.3? ?訂單管理

訂單管理模塊是整個系統的核心模塊。系統管理員可以通過訂單管理模塊查看所有的訂單，顯示所有訂單的詳細信息，包括系統管理員自己新增的訂單，以及客戶新增的訂單。可以對訂單進行增加或者刪除，對新增的訂單進行審核，審核通過的訂單自動分配一條配送路徑，對已審核訂單所分配的路徑進行查看。訂單列表界面如圖4所示。

5.4? ?基于貪心算法的配送

貪心算法在物流配送系統中作用于路線的制定，給出每一個配送點到與其相鄰配送點所需要的時間或者所隔距離，通過貪心算法求出起始配送站到達結束配送站用時最短或者距離最近的路徑。將地圖畫出來就相當于一個帶權值的有向圖。

首先把物流系統所有配送站，以及配送站之間所隔距離和所花費時間記錄下來，即把圖的頂點數、邊數和距離保存下來。然后對集合進行遍歷，若存在路徑，則記錄下來，若不存在則為無窮大。從每一次的遍歷中選取權值最小的配送點加入最短距離配送站集合，并記錄該配送站的前驅配送站，保存在已經求到最短路徑的頂點集合。對其余的尚未求到最短路徑的配送站集合的值進行修改，若加進集合做中間值，從起始配送站到當前配送站的減小，則修改。重復以上步驟，直到遍歷完所有的配送點為止。

選擇一個起始配送站和一個結束配送站，自動生成一條時間最短和一條距離最短路徑，選擇所需路徑即可。時間最短路徑和距離最短路徑如圖5和圖6所示。

6? ?結論（Conclusion）

在實際應用中，物流配送過程中考慮的因素有配送距離以及配送時間。基于貪心算法的物流配送管理系統可以根據客戶的需求選擇相應的配送路徑，為客戶提供優質的服務的同時節省了運輸成本。

參考文獻（References）

[1] 來學偉.兩種不同貪心算法在求解TSP問題中的應用和比較[J].河北北方學院學報，2018（07）：34-37.

[2] 王曉東.計算機算法設計與分析[M].北京：電子工業出版社，2017：90-108.

[3] 鄭瑞卿.構造節約遺傳算法解決電子商務環境下的物流配送路徑優化問題研究[J].宜春學院學報，2018，40（12）：59-61.

[4] 郭寶恩.基于Spark的蟻群算法在物流配送路徑優化問題中的應用研究[J].信息與電腦，2018（03）：50-52.

[5] 李然.GIS下物流節點選址模型[J].電腦編程技巧與維護，2018（05）：85-86;111.

[6] 崔蓬.基于ThinkPHP的物流配送系統的設計與實現[J].軟件，2018，39（07）：194-198.

[7] 王力鋒，楊華玲.物流配送車輛最優網絡路徑選取仿真[J].計算機仿真，2018，35（05）：156-159;202.

[8] 黑馬程序員.Java EE企業級應用開發教程[M].北京：人民郵電出版社，2017.

[9] 李樹真.基于工業互聯網的SSM項目實戰[M].天津：南開大學出版社，2018.