基于节约算法的车辆调度优化
李天昊 邵子楠 宋曲
摘要 本文建立了单车型满载车辆的分送优化模型，并基于节约算法进行了求解。首先对于问题进行分析，确定模型的方向将是以各需求点的最小需求量为约束，以总运输路径最短为目标。影响运输路径的因素有车辆的载重与车辆的行驶距离。基于这些分析建立模型。以节约算法的基本思想为基础，对模型进行具体求解。最后给出了本处理方法的优缺点分析。
关键词：车辆；最短路程；节约算法；分配调度 1
目录 1问题提出..................................................................................................................... 2 2模型假设..................................................................................................................... 2 3 符号说明.................................................................................................................... 3 4模型的理论基础......................................................................................................... 3 5模型建立..................................................................................................................... 4 6模型求解..................................................................................................................... 6 6.1节约算法 .......................................................................................................... 6 6.1.1算法原理 .......................................................................................... 6 6.1.2 算法步骤 ......................................................................................... 7 6.2求解结果 .......................................................................................................... 7
7.优缺点分析............................................................................................................... 13 参考文献 ...................................................................................................................... 14 2
1问题提出 物流被称为“第三利润源泉”，引起了越来越多的重视，成为当前“最重要的竞争领域”。 配送是物流中的一个重要核心环节，是货物从物流结点送达收货人的过程，它实现了生产者与消费者的相互联系。而在物流配送中，车辆运输占有不可或缺的地位，因此车辆运输的优化是非常关键的一环。 对运输车辆进行的优化调度，不仅可以提高经济效益，还可以促进物流的科学化。通过对车辆配送的合理调度，可以实现最短路径、最少时间、最少车辆、最低费用等目标。 本文所探究的问题是单车型满载车辆的分送优化制度，我们以路径最短为目标，以各需求点的最小需求量为约束，求解出总路径最短的车辆运输线路。
2模型假设 1. 车辆行驶中始终做匀速直线运动，即在任何区段车速都相同。 2. 公路系统畅通无阻，不考虑中途发生故障堵车等情况。 3. 不考虑司机短时间休息之类的人为因素。 4. 各路径发车频度相同。 5. 将车辆装卸时间认为是车辆总运输时间的一部分。 6. 货运地中之一为物流装配中心，全部车辆从物流装配中心出发，最后回到装配中心。 3
3 符号说明 q 车辆拥有的容量 id 表示点i到点j的距离 Q 点iP和点jP连接后的线路上总运量
ig 已知任务i的货运量 ijS 点iP和点jP连接在一条线路上的距离节约值
0P 表示配送中心
4模型的理论基础 本文中的物流配送路径优化问题可以描述为:从配送中心(物流据点)用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，并且某些需求点的需求量超过一辆货车的最大额载。要求根据货车的载重和行驶距离合理安排车辆路线，使总运距最短。 (1)因为所送货物总重量超过一辆货车的额载，所以需要若干辆货车一起送货。 (2)每辆车一次可以给几个需求点送货，从配送中心出发到返回称之为一条行驶路径。 (3)运输成本的含义可以是车辆行驶距离、费用和时间等，本文用行驶距离来表示运输成本。 4
5模型建立 建立如下模型：有一个物流配送中心，拥有多台容量为q的车辆，现在有m项货物运输任务需要完成，以1，2，⋯⋯，m表示，已知任务i的货运量为ig (i=1，2，⋯⋯ ，m)，且igq，求满足货运需求的费用最小的车辆运输线路。 为构造数学模型方便，将物流配送中心编号为0，任务编号为1，2，⋯ ⋯ ，m，任务及物流配送中心均以点i (i=0，1，2，⋯⋯，m)来表示。定义变量如下： 1i0,ijy，点的任务由k完成 ; 否则。
1kij 0,ijkx，车辆从点运行到点; 否则。
则分送式配送车辆优化调度问题一般数学模型如下：
min,1,1,2,...,,0,1,...,;..,0,1,...,;()01,0,1,...,;010,1,...,;ijijkijkikiikikijkkjiijkkjjijkijkkizCxgyqkyimxyjmkstxyimkXxSxijmkyimk
或， 或，
模型中， 表示从点i到点j的运输成本，它的含义可以是距离、费用、时间等；q为车辆容量；S为支路消去约束，即消去构成不完整线路的解。 5
图1 支路示意图 如图1所示，两条支路均满足分配约束，但没有构成一条完整的线路，因此不是问题的解。
在实际问题中，分送式配送问题，其车辆路线选择不仅要受到车辆容量限制，而且有时还会受到运行距离、运行时间、不同区段的车速以及运行途中的障碍物、司机的短时间休息等因素影响。 现在假设一条线路上允许的最大的运行距离为l，则有约束条件：
将该约束条件加到上述模型中，于是得到带有运行距离约束的配送车辆优化调度模型。 6
6模型求解 6.1节约算法 6.1.1算法原理 算法基于节约法的基本思想。设P0为配送中心，分别向用户 和 送货。P0到 和 的距离分别为 和， 两个用户Pi、 之间的距离为 ，送货方案只有两种，即配送中心r'o向用户Pi、P；分别送货和配送中心向用户Pi、P；同时送货，如图2所示。比较两种配送方案：
图2 节约法方案 方案(b)配送线路为：000ijPPPPP，配送距离为：0022aijddd； 方案(b)配送线路为：00ijPPPP，配送距离为：00bijijdddd。 显然abdd,我们用ijS表示路线节约值，即方案(b)比方案(a)节约的配送路程 ： 00ijijijSddd
即是将点iP和点jP连接在一条线路上的距离节约值，ijS值越大，说明把iP和
jP连接在一起时总路程减少越多。
旅行商问题的c-w节约算法就是基于这种最大节约值准则，首先对两点进行比较，把不在线路上的点插入线路，已在线路中的点合并为一集合 ，直到所有点都被 安排到线路中。对于分送式配送问题，在连接点对时需 要考虑车辆的容7
量约束和运行路程约束，即一条线路上 各任务的货运量之和应不大于车辆的容量和车辆运行路 程不大于额定路程。
6.1.2 算法步骤 根据前述求解原理，给出具体求解步骤如下:
s t e p 1 ：计算ijS，令0ijijMSS； s t e p 2 ：在M内按ijS从大到小的顺序排列； s t e p 3 ： 若M，则终止，否则对第一项ijS，考察对应的(,)ijPP，若满足下述条件之一： ( 1 )点iP和点iP均不在已构成的线路上； ( 2 )点iP或点iP在已构成的线路上，但不是线路内点； ( 3 )点iP和点iP位于已构成的不同线路上，均不是内点，且—个是起点，一个是终点。则转下步， 否则转s t e p 7。 s t e p 4 ：考察点iP和点iP连接后的线路上总运量Q，若Qq，则转下步，否则转s t e p 7 。 s t e p 5 ：考察点iP和点iP连接后的线路上总路程 L， 若 L ≤l，则转下步，否则转 s t e p 7 。 s t e p 6 ：连接点iP和点iP。 s t e p 7 ：令:ijMMS，转s t e p 3。 6.2求解结果 某物流公司现在需要制定六个货运站A、B、C、D、E、F之间的四条路线的往来运输业务。已知各条路线的起点、终点城市之间的运行时间及每个小时的运输次数见下表。又知每辆货车每次装卸的时间各需1小时，每辆货车的载货量为154吨,货车运行的平均速度28hkm.则该物流公司应如何配备货车，才能满足要求。 路线 起点货运站 终点货运站 每小时运输量(吨)
