基于有向图规划的城乡物流配送路径优化研究

物流业可以加快实体物资流动，能够衡量地区/城市经济发展、综合竞争力，但是在经济结构调整背景下，物流业的发展严重制约着区域经济的发展[1]。因此，我国政府不断加大城乡物流扶持力度，增强城乡经济与物流之间的联系，促进城乡一体化发展，以此来缩小城市高速发展造成的城乡差距[2]。城乡一体化发展是促进城乡产业、政策、市场信息等多方面发展的政策，在这一政策的作用下，可以提升农村消费市场发展速度[3]。但是，传统物流却受到乡村交通、网络设施等因素的限制，导致配送水平降低、成本增加，影响城乡一体化发展效率[4]。因此，亟需寻找城乡物流配送方法，优化现有物流配送路径，提高城乡物流配送效率。

国内外十分重视城乡物流配送路径研究，通过探索城乡物流配送模式、协调机制、物流网络运作流程以及物流配送存在的问题，提出粒子群算法、构造式启发式算法、新型遗传算法、混合遗传算法、车辆选择和K度中心算法、节约里程法等物流配送路径优化方法[5]。文献[6]引入驴与走私者算法建立路径优化模型，为物流配送车辆提供更多稳定的路径选项。文献[7]考虑变路网环境下多温冷链配送路径方法，构建配送成本最小的数学优化模型，利用模拟退火算法对该模型进行求解，得到路径优化结果。文献[8]通过建立城市物流配送路径规划的目标函数，采用蚁群算法找到最优城市物流配送路径规划方案。上述方法优化后的城乡物流配送路径存在路径利用率和需求点满意度低、配送成本高的问题，为此提出基于有向图规划的城乡物流配送路径优化方法。

在此次研究中，将城乡物流配送路径转化为合理安排配送路线问题，即为一个配送中心的M辆车通往N个需求点设计合理路线的过程。为此，假设合理安排配送路线问题中，存在如下已知条件：

条件一：车辆的载重为G，且每辆车的载重相等；

条件二：将需求点需求量记为X，且N个需求点的需求量K不等，而配送中心供给力Z是一个定值，存在K

条件三：每一辆车从配送中心前往各需求点的费用均为$0j，其中，j表示第j个需求点；由第j个需求点转换到第i个需求点之间的费用为$ij。

根据上述三条已知条件，将任意一辆车记为k，任意一个需求点记为i或j，且i≠j，当i=0时，i表示配送中心，所设定车辆分配任务过程和单车配送路径选择过程如下式所示：

式（1）中，Pki表示第k辆车的配送任务；Lijk表示第k辆车完成Pki的配送路径[9]。根据式（1）所示的任务分配过程和对应任务的配送路径选择过程，设计的城乡物流配送路径问题表达式如式（2）所示。

式（2）中，Nk表示车辆k需要配送的需求点集合；f(Nk)表示满足Nk配送约束条件的路径长度；P表示物流配送任务分派问题；L表示任务路线优化问题。

根据式（2），设定的P、L约束条件如式（3）所示。

式（3）中，$表示车辆配送费用[10],Pki表示给第k辆车到第i个需求点物流配送任务，Pkj表示给第k辆车到第j个需求点任务路线优化问题。

基于式（3）约束下的式（2）城乡物流配送路径问题，建立城乡物流配送路径优化模型。

根据式（3）约束下的式（2）城乡物流配送路径问题，提出如下假设：

假设一：配送中心与各需求点的位置固定，两点间的路径均属于直线距离；

假设二：配送中心是车辆配送任务的起点和终点，车辆一次性承载货物可以满足任意一个需求点的需求货物量；

假设三：车辆装载货物是按照批次装载的，因此，同一条配送路线上的需求点只能被同一辆车配送货物；

假设四：M辆车的最远运输距离和最大卸货量一致，并且不存在车辆超载配送；

假设五：车辆需要在需求点时间窗内完成货物配送，否则会增加货物配送成本；

假设六：配送中心可以满足N个需求点货物需求量，具有足够的货物配送能力。

依据上述内容设定的6个假设，建立的城乡物流配送路径优化模型如式（4）所示。

式（4）中，F1表示客户满意度目标函数；s(tkj)表示时间窗函数；tkj表示第k辆车到达第j个需求点的时间；F2表示城乡间车辆路径运行成本目标函数；mi表示配送中心为各个需求点配送货物时使用的车辆数；dij表示需求点i与需求点j之间的距离；Qij表示一天内车辆需要运输的总货物量；F3表示里程利用率目标函数；d表示车辆行驶距离；d0j表示配送中心到需求点j的距离。如式（4）所示的城乡物流配送路径优化模型，设定如下约束条件：

式（5）中，Y1表示车辆派送货物服务客户约束；Y2表示同一需求点进出车辆属于同一辆配送车约束。在式（5）的约束条件下，针对式（4）所示的城乡物流配送路径模型进行最短路径求解，最终得到的城乡物流配送最短路径，即为城乡物流配送路径优化结果。

在式（5）的约束条件下，采用有向图规划式（4）所示的城乡物流配送路径模型中存在的最短路径，实现模型求解。在此次所建立的模型上，覆盖一个有向图，其定义如下：

定义一：将城乡物流配送区域记为有向图规划区域，需求点和配送中心位置用有向图的顶点V表示；配送中心向需求点配送货物的路径用有向图边E表示，则=(V,E)。

定义二：有向图边E上的权重表示车辆配送货物持续时间，顶点V表示有向图上需要完成的事件。

根据上述两条定义，可知有向图中存在N个事件，即需求点数量，则式（4）所示的模型中的路径解为：

式（6）中，B(0),B(1),…,B(l),表示长度不等的路径；l表示路径数量；h表示路径长度，其取值范围在0≤h≤N之间；B(0)[i,j]表示两个需求点间不大于h的最短路径长度；B(1)[i,j]表示两个需求点之间的最短路径；w表示边E上的权重。

按照式（6）所示模型路径求解过程，循环求解模型中的路径，直至得到不同需求点之间的最短路径。此时，每条最短路径的最早发生时间T为：

式（7）中，T(j)表示需求点i的前一个需求点j的最早配送时间，则其得到的T(N)即为完成所有需求点货物配送的最早时间。

根据式（6）和式（7）得到的需求点最短配送路径和最早配送时间，获取该范围内的顶点(V)，则有：

式（8）中，K(V)表示最短路径中存在的相邻节点；V'表示从V中选出的顶点；u表示节点重要系数。

根据式（8）选取的节点，即为求解式（4）后得到最优路径上的节点，将这些节点相连接，在有向图上形成的边，即为优化后的城乡物流配送路径。

选择基于模拟退火算法的路径优化方法和基于驴与走私者的路径优化方法作为此次实验的对比方法，选择某区域城乡物流作为此次实验研究对象，验证此次研究的基于有向图规划的城乡物流配送路径优化方法。

此次实验选择的城乡物流区域属于一站式服务物流，与城市超市、商家、116个乡镇均存在物流配送合作。为了降低实验难度，此次研究将从选择的实验区域中，选取10个城市配送点和6个农村配送点，作为此次实验研究对象。

基于此次实验选择的城乡物流配送点按照地图上的实际位置，以配送中心为原点，建立二维坐标系(X,O,Y)，得到16个配送点位置，如图1所示。

根据图1所示的位置图，设置的中心点与配送点距离、配送点需求量和供给力、时间窗参数，如表1所示。

基于图1所示的配送点和配送中心位置，以及表1所示的配送中心及需求点参数，将每件货物处理成本设置为0.3元。从该区域的城乡物流配送车中，选择装载量为3 t、行驶距离为700 km的配送车辆，作为此次实验配送货物车辆。该车辆在配送货物过程中，装卸货物速度为25 min/t，平均行驶速度为50 km/h，产生的固定成本为70元，每千米的配送成本为3元；当其提前到达需求点时，会产生20元/h的等待成本；当配送车辆晚于需求点最迟配送时间时，同样会产生20元/h的等待成本。

根据此次实验确定的城乡需求点、配送中心位置，以及城乡物流配送相关参数，其初始路径方案如图2所示。

如图2所示的初始配送路径，总共规划了配送中心→城市7→城市6→城市5→农村5→配送中心、配送中心→城市3→城市4→城市2→农村6、配送中心→城市9→城市10→农村2→农村3→配送中心、配送中心→城市1→城市8→城市10→农村4→农村1→配送中心四条线路。其走路径1车辆的运行成本为551.39元，路径2车辆的运行成本为671.04元，路径3车辆的运行成本为915.51元，路径4车辆的运行成本为1 580.4元，车辆运行总成本为3 718.34元。依据图2所示的城乡物流配送初始方案，采用此次实验选择的三组路径优化方法，分别优化图1所示的城乡物流配送路径，其路径优化结果如下。

三组路径方法优化图2所示的初始配送路径后，得到的城乡物流配送路径如图3所示。

从图3中可以看出，基于模拟退火算法的路径优化方法应用后，优化成了配送中心→城市1→城市7→城市5→城市2→农村6→农村5→配送中心、配送中心→城市3→城市4→城市9→城市8→农村1→配送中心、配送中心→城市6→城市10→农村4→农村2→农村3→配送中心三条路径；基于驴与走私者的路径优化方法应用后，优化成了配送中心→城市2→城市5→城市6→城市7→城市8→城市1→农村2→农村5→配送中心、配送中心→城市4→城市3→农村4→农村3→配送中心、配送中心→城市9→城市10→农村1→农村6→配送中心三条路径；研究方法应用后，优化成了配送中心→城市2→城市4→城市6→城市5→农村5→农村6→农村3→农村2→配送中心、配送中心→城市3→城市7→城市8→城市9→城市10→城市1→农村4→农村1→配送中心两条路径。可见，三组路径优化方法，均在原本路径基础上，优化了配送路径数量。

为了进一步验证此次实验选择的三组优化方法，将根据图3所示的优化路径，计算三组优化方法运输成本、里程利用率和需求点用户满意度的目标函数值，进一步验证此次研究的路径优化方法。

三组优化方法运输成本、里程利用率和需求点用户满意度的目标函数值计算结果，如表2所示。

从表2中可以看出，基于模拟退火算法的优化方法在初始配送路径方案基础上，将配送成本降低了1 637.88元；基于驴与走私者的优化方法在初始配送路径方案基础上，将配送成本降低了1 500.84元；研究方法在初始配送路径方案基础上，将配送成本降低了2 168.83元，与其他两种方法相比，配送路径总成本显著下降。此外，平均里程利用率和需求点满意度明显高于两组对比方法。由此可见，此次研究方法可以提高初始配送路径利用率和需求点满意度，降低配送路径配送成本。

此次研究充分利用有向图规划算法求解城乡物流配送路径优化模型，以此得到配送成本低、路径里程利用率和需求点满意度高的配送路径。但是，此次研究未曾考虑调货等问题。因此在今后的研究中，还需深入研究城乡物流配送路径中存在的调货等问题，进一步提高路径优化方法的实用性。