基于贪心算法的物流配送系统的设计与实现

赵长鲜 方木云

摘  要：物流行业的发展使得越来越多的物流系统涌现。针对目前物流系统在配送过程中存在路径选择问题，设计与实现了基于贪心算法的物流配送系统。该系统利用贪心算法自动选择最短配送路径，简单快捷。使用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.