趙長鮮 方木云

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

關(guān)鍵詞：物流;貪心算法;SSM

中圖分類號：TP311? ? ?文獻(xiàn)標(biāo)識碼：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）

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

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

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

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

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

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

3? ?系統(tǒng)設(shè)計（System design）

3.1? ?架構(gòu)選擇

系統(tǒng)采用Spring、SpringMVC、MyBatis整合框架進(jìn)行開發(fā)實現(xiàn)。

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

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

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

3.2? ?功能設(shè)計

基于貪心算法的物流配送管理系統(tǒng)功能主要體現(xiàn)在對訂單配送路徑的自動選擇上。當(dāng)一個客戶或者管理員新建一個訂單時，需要對訂單的起始配送站和到達(dá)配送站進(jìn)行選擇，然后由管理員進(jìn)行審核。審核通過后會自動生成一條時間最短或者距離最短的配送路徑?？蛻糁荒軐ψ约旱挠唵芜M(jìn)行查看，而管理員可以對所有的用戶，包括配送站管理員或者客戶進(jìn)行管理，除此之外，管理員可以查看和修改所有的訂單，對訂單進(jìn)行審核。對于用戶的權(quán)限，全部都是管理員進(jìn)行分配的。系統(tǒng)還可以對配送站進(jìn)行更新，可以新增配送站或者對已存在的配送站進(jìn)行修改。

系統(tǒng)根據(jù)功能劃分可分為兩大模塊：

第一個模塊是基礎(chǔ)數(shù)據(jù)的管理模塊。對客戶的信息進(jìn)行增、刪、改、查，包括新客戶的注冊，客戶個人信息的顯示和修改，客戶的新建，客戶的權(quán)限分配，以及所有客戶的基本信息的管理;系統(tǒng)所有菜單的管理，包括新建和修改。該模塊對所有的基礎(chǔ)信息進(jìn)行管理。

第二個模塊是訂單管理模塊。該模塊首先對所有的配送站進(jìn)行管理?？梢詫ε渌驼具M(jìn)行添加或者修改，將各個配送站進(jìn)行鏈接。訂單的管理包括新增訂單、管理訂單和查看訂單。

對于不同的用戶擁有不同的權(quán)限，保證了用戶信息的安全。對于系統(tǒng)的功能模塊如圖1所示。

4? ?數(shù)據(jù)庫設(shè)計（Database design）

系統(tǒng)使用Navicat Premium可視化工具對MySQL數(shù)據(jù)庫進(jìn)行操作，建立了一個用于存放在系統(tǒng)運行中所有產(chǎn)生的以及所需的數(shù)據(jù)信息數(shù)據(jù)庫。

根據(jù)系統(tǒng)基礎(chǔ)數(shù)據(jù)的管理，以及訂單管理的功能進(jìn)行設(shè)計，總結(jié)出數(shù)據(jù)庫設(shè)計方案。數(shù)據(jù)庫共包括七個表，包括菜單表、配送站表、配送站路線表、訂單表、訂單路線表、用戶表以及用戶菜單表。表1—表3展示了其中重要部分表字段設(shè)計。

5? ?系統(tǒng)功能實現(xiàn)（System function realization）

5.1? ?用戶管理

用戶分為管理員和客戶，不同的用戶擁有不同的權(quán)限。

管理員用戶擁有系統(tǒng)的所有權(quán)限，管理員登錄賬號以后進(jìn)入系統(tǒng)會顯示系統(tǒng)所有菜單。

客戶所擁有的權(quán)限由系統(tǒng)管理員分配，客戶登錄賬號以后進(jìn)入系統(tǒng)顯示的部分菜單是由系統(tǒng)管理員所授予的權(quán)限菜單。登錄界面如圖2所示。

5.2? ?配送站管理

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

5.3? ?訂單管理

訂單管理模塊是整個系統(tǒng)的核心模塊。系統(tǒng)管理員可以通過訂單管理模塊查看所有的訂單，顯示所有訂單的詳細(xì)信息，包括系統(tǒng)管理員自己新增的訂單，以及客戶新增的訂單?？梢詫τ唵芜M(jìn)行增加或者刪除，對新增的訂單進(jìn)行審核，審核通過的訂單自動分配一條配送路徑，對已審核訂單所分配的路徑進(jìn)行查看。訂單列表界面如圖4所示。

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

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

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

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

6? ?結(jié)論（Conclusion）

在實際應(yīng)用中，物流配送過程中考慮的因素有配送距離以及配送時間?；谪澬乃惴ǖ奈锪髋渌凸芾硐到y(tǒng)可以根據(jù)客戶的需求選擇相應(yīng)的配送路徑，為客戶提供優(yōu)質(zhì)的服務(wù)的同時節(jié)省了運輸成本。

參考文獻(xiàn)（References）

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

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

[3] 鄭瑞卿.構(gòu)造節(jié)約遺傳算法解決電子商務(wù)環(huán)境下的物流配送路徑優(yōu)化問題研究[J].宜春學(xué)院學(xué)報，2018，40（12）：59-61.

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

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

[6] 崔蓬.基于ThinkPHP的物流配送系統(tǒng)的設(shè)計與實現(xiàn)[J].軟件，2018，39（07）：194-198.

[7] 王力鋒，楊華玲.物流配送車輛最優(yōu)網(wǎng)絡(luò)路徑選取仿真[J].計算機(jī)仿真，2018，35（05）：156-159;202.

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

[9] 李樹真.基于工業(yè)互聯(lián)網(wǎng)的SSM項目實戰(zhàn)[M].天津：南開大學(xué)出版社，2018.