两层物资配送中心车辆调度问题研究 耿 雪1,2，段会川1,2 (1. 山东师范大学信息科学与工程学院，济南 250014；2. 山东省分布式计算机软件新技术重点实验室，济南 250014) 摘 要：在分析物流配送物资问题的基础上，提出一种基于两层物流配送中心的物资配送方法。供应方在配送物资时需经过两层配送中心到达需求方，否则将予以惩罚。在建立供应方、两层物流配送中心及需求方四层物流网络模型的基础上，采用Dijkstra算法求出从各供应点到各需求点的最短运输距离并将其转化在供需平衡表中，采用表上作业法和节约里程法相结合的算法求解四层物流网络模型。结合算例计算验证，该算法在保证运输总费用最少的同时可有效地减少配送过程中车辆调度的次数。 关键词：表上作业法；物资配送；物流网络模型；Dijkstra算法；节约里程算法；最小元素法
Research on Vehicle Schedule Problem of Two-layer Mterial Distribution Center
GENG Xue1,2, DUAN Hui-chuan1,2 (1. School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China; 2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology, Jinan 250014, China)
【Abstract】By analyzing the problem of logistics, this paper proposes a way of dispatching material on the basis of two-layer distribution center. When dispatching the materials, the side of supplier has to pass through two layers of distribution center to reach the side of demander, otherwise it will be punished. On the basis of establishing the model of four-layer logistics network, which includes the sides of supplier and demander, also two layers of distribution center, this paper uses the Dijkstra algorithm to obtain the shortest transport distance between the point of supplier point and the point of demander, and conversion into the balance chart of supply and demand, then it makes use of algorithm which combines the Tabular method and save-mileage method to solve the model of four-layer logistics network. Experimental results show that the algorithm can guarantee the least total cost of transportation. At the same time, it can effectively reduce the number of vehicle schedule in the process of delivery. 【Key words】Tabular method; material distribution; logistics network model; Dijkstra algorithm; saving mileage algorithm; minimum element method DOI: 10.3969/j.issn.1000-3428.2012.05.088
计 算 机 工 程 Computer Engineering 第38卷 第5期
Vol.38 No.5
2012年3月
March 2012
·开发研究与设计技术· 文章编号：1000—3428(2012)05—0285—03
文献标识码：A
中图分类号：TB114.1
1 概述 在物资配送过程中，面对强大的竞争压力，作为企业第三利润源的物流业在社会生产过程中的地位越来越重要。随着物流配送物资过程的复杂性，出现了多层物流配送中心的运输物流网络问题，车辆路径优化(Vehicle Routing Problem, VRP)是基于复杂物流网络运输问题研究的关键之处[1]。国外
学者对其进行的研究起步较早，常用启发式算法进行求解，如节约启发式、遗传算法等，国内学者对其进行的研究起步较晚，以C-W为基础的启发式算法对VRP进行了求解；也
运用遗传算法就VRP问题进行求解等。 运输问题[2]是线性规划的一类特殊问题，它可以解决物资的合理配送。因此，可以尝试将问题转化在近似供需平衡表中，运用表上作业法进行求解。运输问题存在着产销平衡、供大于求和供不应求的情况。对于产销不平衡的情况，可以通过增加虚拟产地(虚拟销地)转化为产销平衡的问题进行求解。本文基于产销平衡的运输问题，结合改进的表上作业法和节约里程算法，研究基于四层物流网络中如何将物资进行最优化调度。
2 物资配送模型的建立 2.1 物资配送模型 由于城市规模都比较大，物流配送车辆又受到交通拥挤的影响，如果每个供应点都只通过一级配送中心供应物资，
不仅造成很多较远的需求点难以及时得到物资，同时又造成了配送中心的紧张局势，导致整个服务水平降低，因此出现了多层物流配送中心。车辆运输物资的过程如图1所示[3]。
供应点1供应点2. . .供应点m供应点1供应点2. . .供应点n
物流中心
配送
配送配送配送 图1 物资配送模型 根据本文研究的内容，可将物资配送模型转换为四层物流网络模型，如图2所示。
图2 四层物流网络模型 作者简介：耿 雪(1987－)，女，硕士研究生，主研方向：优化调度，物流管理；段会川，教授 收稿日期：2011-08-24 E-mail：gengxuesdnu@163.com 286 计 算 机 工 程 2012年3月5日 该模型可以描述为供应方Ai的物资经过两层配送中心到达需求方Bj。设某产品有m个供应商A1,A2,…,Am，可供应物资a1,a2,…,am；另有n个需求方B1,B2,…,Bn，需求物资b1,b2,…,bn。用gij表示从供应点i到需求方j的供应量，用xij表示从供应点i到需求点j的路径和，若从Ai到Bj的单位运价为cij，这样就把问题转化为：在此网络求可行的调配方案，使得保证总的运价最小。 根据对物资配送问题的描述，为了更直观地说明在配送过程中要解决的问题，首先给出供需平衡表[4]，如图3所示。然后建立如下数学模型，如式(1)~式(3)所示，式(4)~式(6)表示需要满足的约束条件： 11min(2)ijijmnijCcXx==××=+∑∑ (1) min(1())()ijikkssjkjxLLLXLX=++−×+× (2) 01X⎧=⎨⎩物资经过二级配送中心到达需求方物资从一级配送中心直接到需求方 (3) 11qnskjsjMQ==∑∑≤ (4) 11mnijijab===∑∑ (5) 110,,ijnmijiijjjigggab====∑∑≥ (6) 其中，Lik表示从Ai到一级配送中心的距离；Lks表示从一级配送中心到二级配送中心的距离；Lkj表示从一级配送中心到需求点的距离；Lsj表示从二级配送中心到需求点的距离；xij表示从供应点i到需求点j的路径和；Mk表示车辆在第k条路径上的一次运载量；Q表示车辆的载重量。 在上述模型中，式(1)为目标函数，即要求配送总里程最短。任一供应方需经过2次配送中心到达需求方，供应方Ai的物资如果只经过一层配送中心到达需求方Bj，则相应的会有2个单位的费用惩罚；式(2)表示了从Ai经过二级配送中心到达Bj的距离之和；式(4)表示了第s个二级配送中心在第k条路径上的运载量不超过车辆的载重量；式(5)、式(6)保证了产销平衡。 B1 B2 … Bn 供应量 A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a2 … … … … … … Am Cm1 Cm2 … Cmn am 需求量 b1 b2 … bn 图3 供需平衡表 2.2 相关算法描述 2.2.1 Dijkstra算法 最短路径搜索算法旨在寻找图中两节点之间的最短路径。常用的路径算法有：Dijkstra算法，A star算法，SPFA算法，Bellman-Ford算法，Floyd-Warshall算法，Johnson算法。可以采用Dijkstra算法求得从某个源点到其余各顶点的最短路径[5]。 2.2.2 表上作业法 表上作业法[6]是求解运输问题的一种行之有效的方法，其求解工作在平衡运输表上进行。它是一种迭代法，迭代步骤如下： 步骤1 用最小元素法或西北角法找出一个初始解。 步骤2 运用闭回路法或位势法对所求的初始解进行最优性判别。若这个解不是最优解，就在运输表上对它进行调整改进，得出一个新解；再判别，再改进；直至得到运输问题的最优解。 2.2.3 节约里程算法 节约里程算法[7]的核心思想是依次将运输问题中的2个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。 如图4所示，物资从A、B分别运往DC，然后返回A、B，那么路程为2×(La+Lb)，车辆调度次数为4。若Lab<(La+ Lb)，则Lab+Lb+La<2×(La+Lb)，所以车辆可以从A-B-DC-A，这样不
仅可以节约路程，而且可以减少车辆调度次数[8]。
图4 节约里程算法样例 3 D-T-S算法 针对2.1节中建立的四层物流配送网络模型，提出了一种新的算法，将Dijkstra算法、表上作业法和节约里程算法相结合求解四层网络配送问题。步骤如下： 步骤1 运用Dijkstra算法求出从各供应点经过两层配送中心到达各需求点的最短路径，并将其转化在供需平衡表中。 步骤2 运用最小元素法求得运输问题的初始解，在物流配送物资过程中，在每一次配送过程中都保证单位运价最小化，从而经过若干步后可以完成物资配送过程。 步骤3 用闭回路法进行检验，构造每一个空格的闭回路，计算出各非基变量(对应空格)的检验数。若检验数大于或等于0，则可得问题的最优解；否则，需找出绝对值最大的负检验数格进行调整，经过调整后得到问题的最优解。 步骤4 在保证车辆运载能力的情况下，运用节约里程算法对运输问题中从二级配送中心到需求方的2个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。具体过程如图5所示。