基于多目标优化的快递管理系统
2017-06-05毕志升林泽宇
毕志升，林泽宇
基于多目标优化的快递管理系统
毕志升，林泽宇
（广州医科大学基础学院，广州 511436）
高效的配送是快递企业生存和发展的前提。为了有效管理快递和规划路径，首先，采用用例图进行了需求分析。接着，采用Struts2、Spring和Hibernate框架进行了系统架构设计。然后，采用序列图和类图对展示了路径规划功能的用例实现。最后，实现了一个基于多目标优化的快递管理系统。本系统提供快递管理、配送中心管理和路径规划等功能，能产生多套路径方案，供业务管理员根据实际情况进行选择。通过实验，本系统运行良好，系统的设计和实现是可行有效的。
多目标优化；快递管理；Struts2；Spring；Hibernate
0 引言
高效的配送是快递企业生存和发展的前提。在电子商务蓬勃发展的今天，仅仅一个城市快递企业每日需要配送的货物就数以百万计[1]。不合理的配送路径将为企业带来巨大的损失。利用计算机技术合理规划配送路径[2]，是快递企业实现快捷高效配送服务的必然选择[3]。然而，路径规划是一个复杂的多目标优化问题，既要考虑配送成本，又要考虑客户满意度，不同配送中心的货物吞吐量和快递员的工作量也需要均衡考虑。面对一个复杂的多目标问题，仅仅给出一套规划方案是不合适的[4]。从不同的角度考察配送问题，给出多套可行方案供企业选择，并在地图中直观地展示出来是一个理想的快递管理系统应当具备的功能。基于这个目的，本文提出一种基于多目标优化的快递管理系统的设计和实现。系统除了能实现收件、预约、查询等基本的快递管理功能，更重要的是运用了当前多目标优化在车辆路径问题上的最新成果，采用多目标优化技术[5]同时考察路径规划需要考虑的各项目标，优化从多个配送中心到客户的配送路径，为快递企业提供多个可选的路径方案并在地图上直观地展示。本系统可用于由一个集散中心向多个配送中心发货从而为一个区域提供配送服务的情况，以及多车场车辆路径问题[6]理论研究的可视化平台。
本文第1节对系统进行需求分析；第2节进行系统设计；第3节进行系统实现；第4节是本文结论。
1 需求分析
本系统的主要使用者主要包括客户、收件员、快递员和业务管理员。客户主要使用系统的预约收件和查询快递等功能。收件员主要使用系统的快递登记等功能。快递员主要使用系统的查询快递、查询配送路径和快递状态更新等功能。业务管理员主要使用快递管理和规划路径等功能。由于系统需要显示实际配送路径，为业务管理员规划、查询路径，快递员配送快递提供支持，需要使用外部地图系统。
采用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、DepotService向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、RouteSercive向RouteDAO发送消息，保存被选择方案的ID；
（5-7）返回执行结果，流程结束。
规划得到的路径以天为单位序列化后保存为文件，并在数据库中保存规划的时间、实施方案的编号以及文件的位置。
本系统需要使用地图系统展示地图、寄件人和收件人地址以及配送路径。为验证本系统的设计和实现，本文选用了免费开放的Baidu地图，对应图3中的MapSystem。若改用其他地图产品，修改RouteService即可。
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所示。RoutePlanningSystem作为一个边界类实现与路径规划子系统的交互，它依赖于接口PlanningInterface。类MDVRP作为接口的实现，提供实际的路径规划服务，并根据上述的3个目标对每一套配送方案进行评价（evaluate()方法）。另一方面，类MDVRP依赖于接口Solution和Algorithm。类Plan作为Solution的实现，保存规划得到的路径方案和该方案对应的目标函数值（objs）。类Route保存方案中每一条具体的配送路径，对应一辆车。类NSGAIII是Algorithm的实现，提供路径方案的搜索（search()方法）。采用这种设计的原因是：上述的目标函数和搜索算法可能会随着技术的发展和企业的要求而改变。但是以路经集合为解决方案、采用特定的搜索算法规划路径这两点是不变的。接口PlanningInterface实现了路径规划子系统和快递管理系统其他部分的解耦；接口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 examination 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 heterogeneous 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 nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE transactions on evolutionary computation, 2014, 18(4): 577-601.
[14] 邓欣. 基于遗传算法的多车场车辆路径问题研究[D]. 重庆: 重庆大学, 2007. GENG Xin. Research on multiple depot vehicle routing problem based on genetic algorithm[D]. Chongqing: Chongqing 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 computerdized 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 delivery 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
