基于路网的动态配送系统软件开发与设计

侯一萌 刘士广

南京农业大学工学院，江苏 南京 210031

基于路网的动态配送系统软件开发与设计

侯一萌 刘士广

南京农业大学工学院，江苏 南京 210031

配送车辆优化调度问题是物流系统中的一个重要环节，本软件借助VB语言，在分析静态配送的基础上，针对不断变化的市场需求，建立动态的物流配送模型，在生成路网的平台上，通过研究物流配送货物过程中路径、车辆选择的问题，提出对物流配送最优路径的动态选择方案，提高物流配送效率，满足客户需求，更符合实际。

路网；Floyd算法；节约算法；车辆优化调度；动态配送

1.研究意义

现代物流已被公认为是企业在降低物质消耗，提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径[1]。所谓配送是指按客户的订货需求，在物流中心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动，是物流系统中的一个重要环节[2]。我国在20世纪80年代初就引进物流配送的概念，随着经济的发展，越来越多的人对物流配送有了全面的了解和认识，但在相当多的企业中，其观念还停留在成本中心、利润中心上，运输、仓储的现代化水平比较低，“只送不配”的现象造成物流配送无效作业环节的增多，车辆空驶严重，配送成本高，质量低，效率低下。

本软件在配送中心与客户之间进行物流活动前，得出最优配送方案，并对于车辆配送过程中可能随机出现新客户的情况进行配送路线和车辆的调整，使配送资源得到最大化的利用，减少配送时间和成本，避免车辆空驶现象，提高配送效率。

2.软件概述

配送车辆优化调度问题可以描述为：在一个存在供求关系的系统中，有若干台车辆，若干个配送中心，要求合理安排车辆的行车路线和出行时间，从而在给定的约束条件下，把客户需求的货物从配送中心送到客户，把客户供应的货物从客户取到配送中心，并使目标函数取得优化[3]。

由于现实生活中的配送车辆优化调度问题非常复杂，为了方便用Visual Basic语言进行编程，我们在以下约定条件下进行研究：

（1）从一个配送中心向多个客户送货；配送中心供应的货物能够满足所有客户的需求。

（2）每台配送车辆的最大载重量一定，不允许超载；每台配送车辆都从配送中心出发，向客户提供配送服务以后，最终返回配送中心。

（3）对于客户的要求将需求货物送到的时间无限制，即不带时间窗的配送调度问题。

（4）各个客户需求的货物可以装在同一辆配送车辆上，每个客户的货物需求量不超过配送车辆的最大载重量；每个客户的送货要求必须满足，且仅能有一辆车辆完成，不允许分批配送。

（5）配送中心与客户之间以及客户之间的距离已知；不考虑运输网络中的车辆流量的限制。

基于以上条件，在所开发的软件中输入节点数，可以生成具有相应节点数的随机路网；输入客户数，在已生成的路网的基础上相应地随机生成一个配送中心和若干客户点及每个客户点要求的货物量；计算机经过计算，得出具有一定载货量的车辆由配送中心出发，将货物配送至各个客户点的最佳路径。车辆在按此路径方案进行配送的过程中可能出现新的客户和客户需求，软件即可根据此信息调整车辆之后所走的路线，得到新的配送方案，从而达到动态配送，使配送资源利用最大化的目的，降低配送成本，提高配送效率。

3.配送车辆优化调度问题算法分析与选择

3.1 最短路径问题

最短路径问题通常指的是在网络中的每条边都有一个权值，寻找图（由结点和路径组成的）中两结点之间总权和最小的路径。最短路径问题可以分为单源最短路径问题和全局最短路径问题。单源最短路径包括以下几种问题：确定起点的最短路径问题；确定终点的最短路问题；确定起点终点的最短路问题。全局最短路问题则要求出图中所有的最短路径。

3.1.1 Floyd算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，时间复杂度为O(N^3)，空间复杂度为O(N^2)，用矩阵记录图，利用动态规划思想，设Di,j,k为从i到j的只以(1...k)集合中的节点为中间节点的最短路径的长度。若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1；若最短路径不经过点k，则Di,j,k = Di,j,k-1。因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 ,Di,j,k-1)。

3.1.2 Dijkstra算法

Dijkstra算法是解单源最短路径问题的一个贪心算法。设图共有n个不同的结点，则从源点出发到达其他各点的最短路径有n-1条，这n-1条最短路径之间存在大小关系。Dijkstra算法的基本策略是，按长度不减次序构造这n-1条最短路径，即先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，最后求出长度最大的最短路径[4]。

由于本软件生成的路网及客户点、客户需求量都是随机的，且生成的网络图没有负权边，在此情况下，为了使计算机更容易获得最优配送路线方案以及进行之后的动态调整，我们选取用于解决全局最短路径问题的Floyd算法来完成软件最短路径部分的编程。

3.2 配送车辆调度问题

3.2.1 节约算法解决初始配送路线问题

节约算法是由Clarke和Wright于1964年首次提出的，它的基本原理是首先把各点单独与源点0相连，构成1条仅含一个点的线路。总费用为从原点到各点的距离的费用的两倍。然后计算将点i和j连接在一条线路上费用的节约值，即：S(i,j)=c0i+ ci0+ c0j+cj0-(c0i+ cij + cj0)= c0i+ c0j -cij。S(i,j)越大，说明把i和i连接在一起时总路程减少越多。实际的路线优化就是根据节约值进行降序排列。

节约算法求解问题的步骤是：

第一步：求出最短距离矩阵。根据配送路网图中配送中心与客户之间以及客户之间的距离，应用Floyd算法计算出路网中各节点之间的最短距离，计入矩阵；

第二步：计算节约值s(i,j)。根据第一步中求得的最短距离矩阵，利用节约值计算公式求出各客户点的节约里程，令M={s(i,j)|s(i,j)>0}；

第三步：在M中对s(i,j)降序排列。

第四步：确定配送路线。根据节约值的大小顺序和节约算法的约束条件，逐渐组成配送路径图[5]。

节约算法运算速度快，尤其在小规模的配送优化中，节约算法的优化精度很高，可以很快得出结果。将节约算法运用在所开发的软件中，得出从配送中心出发最终回到配送中心的初始配送路线。

3.2.2 插入法进行路线的动态调整

由于软件需要实现动态调整路线的功能，即当车辆按照原路线行驶至客户点A时，出现新的客户点B及相应的需货量，可以调整车辆在A点之后的行驶路线，或者从配送中心重新调度，达到既能满足客户需求，又能有效利用资源、提高配送效率的最优化目的。

当有新客户点产生时，配送调整路线应从新客户点出发返回至配送中心，此时从一点出发返回至该点的节约算法不再适用。受节约算法的启发，我们采用插入法来解决这一问题。

以生成一个新客户点P为例。首先根据P点的需货量，判断目前货物重量是否超过单车载重，若超过，则从配送中心选择最佳路径重新调度车辆；若没有超过，则调用最短距离函数，依次求出初始路线在A点之后的所经过的各个节点1、2、3……n与新客户点P之间的最短距离，用ss(i,P)表示节点i与P之间的最短距离，令d(1)=ss(2,P)-ss(1,P)；d(2)=ss(3,P)-ss(2,P)……d(i)=ss(i+1,P)-ss(i,P)，找出使d(i)取值最小的下标j，可以将新客户P点插入节点j和节点j+1中间，完成配送路径的调整。

4.软件制作

软件运用Visual Basic语言进行界面制作和程序编译。在以上算法分析的基础上，依次进行生成路网、最短路径、随机生成客户及客户需货量、节约算法求解路径、插入法调整路径的编程工作，部分程序如下：

4.1 Floyd算法程序

图1

4.2 节约算法部分程序

图2

软件制作完成后，可以得到如下图效果：

图3

5.结语

本文设计开发的软件在物流企业进行货物配送的问题上建立了车辆优化调度的模型，提出最优的配送路径方案，并针对配送任务过程中可能出现新客户点的情况，对配送方案进行动态调整，达到资源的优化利用，提高物流配送效率。

由于本软件仅限于建立了动态配送优化调度的模型，且研究的约束条件不含带时间窗，可用于教学软件，但与复杂的现实情况相比仍有较大的差距。在此基础上，可以将时间窗等约束条件添加到算法中，模拟更多约束条件的车辆配送路线问题。同时，可以考虑将GIS系统应用到软件中，模拟与实际情况相符合的路网状况，是软件应用性更强。

[1]马力强.关于我国现代物流发展的思考[J].交通运输系统工程与信息,2000年第1期

[2]郎茂祥.配送车辆调度问题刍议.物流技术，2003年03期

[3]Golden B L,Assad A A , Ball M..Routing and Scheduling of Vehicles and Crews:The State of Art[J].Computers & Operations Research,1983,7(10):63～211

[4]吴华丽，吴进华，王玲玲，陈世童.2010国际信息技术与应用论坛论文集,2010年

[5]郑英，孟志青.基于节约算法的烟草物流配送路线优化.中国管理信息化, 2010年12月第13卷第23期

Based on Network Dynamic Distribution System Software Development and Design Hou Yimeng，Liu Shiguang

College of Engineering,Nanjing Agricultural University,Nanjing 210031,China

Logistics distribution vehicle scheduling problem of logistics is a key link in the system, the software developed by VB language, in the analysis of static distribution basis, in response to the changing market demand, establishing the dynamic model of logistics distribution in generation, network platform,through the research of logistics distribution vehicle routing, goods in the course of selection problem, put forward to the logistics distribution path optimization dynamic selection scheme, improve the efficiency of logistics distribution, to meet customer needs, more practical.

road network;floyd algorithm;saving algorithm;optimization of vehicle dispatching;dynamic distribution

10.3969/j.issn.1001-8972.2012.15.038