基于貪心算法的物流配送系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

趙長(zhǎng)鮮 方木云

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

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

中圖分類號(hào)：TP311? ? ?文獻(xiàn)標(biāo)識(shí)碼：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ā)展日新月異，越來(lái)越多的物流系統(tǒng)也隨之出現(xiàn)。這些物流系統(tǒng)都竭盡可能地為客戶提供優(yōu)質(zhì)的服務(wù)，提高客戶的滿意程度。與此同時(shí)物流行業(yè)也要盡可能地節(jié)約成本，提高自己的收益。物流配送系統(tǒng)針對(duì)不同權(quán)限用戶給予不同權(quán)限，妥善管理用戶信息的同時(shí)也能讓用戶查詢自己所需信息。針對(duì)不同配送點(diǎn)選擇不同配送路徑，有效提高公司運(yùn)行效率和收益。也可以隨著用戶的增加或者配送點(diǎn)的擴(kuò)大而及時(shí)更新數(shù)據(jù)。

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

2? 貪心算法的簡(jiǎn)介（Brief introduction to greedy algorithm）

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

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

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

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

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

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

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

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

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

3.2? ?功能設(shè)計(jì)

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

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

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

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

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

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

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

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

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

5.1? ?用戶管理

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

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

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

5.2? ?配送站管理

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

5.3? ?訂單管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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