基于节约算法的车辆调度优化

1、基于节约算法的车辆调度优化 李天昊 邵子楠 宋曲摘要本文建立了单车型满载车辆的分送优化模型，并基于节约算法进行了求解。首先对于问题进行分析，确定模型的方向将是以各需求点的最小需求量为约束，以总运输路径最短为目标。影响运输路径的因素有车辆的载重与车辆的行驶距离。基于这些分析建立模型。以节约算法的基本思想为基础，对模型进行具体求解。最后给出了本处理方法的优缺点分析。关键词：车辆；最短路程；节约算法；分配调度目录1问题提出22模型假设23 符号说明34模型的理论基础35模型建立46模型求解66.1节约算法66.1.1算法原理66.1.2 算法步骤76.2求解结果77.优缺点分析14参考文献141问题

2、提出物流被称为“第三利润源泉”，引起了越来越多的重视，成为当前“最重要的竞争领域”。配送是物流中的一个重要核心环节，是货物从物流结点送达收货人的过程，它实现了生产者与消费者的相互联系。而在物流配送中，车辆运输占有不可或缺的地位，因此车辆运输的优化是非常关键的一环。对运输车辆进行的优化调度，不仅可以提高经济效益，还可以促进物流的科学化。通过对车辆配送的合理调度，可以实现最短路径、最少时间、最少车辆、最低费用等目标。本文所探究的问题是单车型满载车辆的分送优化制度，我们以路径最短为目标，以各需求点的最小需求量为约束，求解出总路径最短的车辆运输线路。2模型假设1. 车辆行驶中始终做匀速直线运动，即在任

3、何区段车速都相同。2. 公路系统畅通无阻，不考虑中途发生故障堵车等情况。3. 不考虑司机短时间休息之类的人为因素。4. 各路径发车频度相同。5. 将车辆装卸时间认为是车辆总运输时间的一部分。6. 货运地中之一为物流装配中心，全部车辆从物流装配中心出发，最后回到装配中心。3 符号说明 车辆拥有的容量 表示点到点的距离 点和点连接后的线路上总运量 已知任务i的货运量 点和点连接在一条线路上的距离节约值 表示配送中心4模型的理论基础本文中的物流配送路径优化问题可以描述为:从配送中心(物流据点)用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，并且某些需求点的需求量超过一

4、辆货车的最大额载。要求根据货车的载重和行驶距离合理安排车辆路线，使总运距最短。(1)因为所送货物总重量超过一辆货车的额载，所以需要若干辆货车一起送货。(2)每辆车一次可以给几个需求点送货，从配送中心出发到返回称之为一条行驶路径。(3)运输成本的含义可以是车辆行驶距离、费用和时间等，本文用行驶距离来表示运输成本。5模型建立建立如下模型：有一个物流配送中心，拥有多台容量为q的车辆，现在有m项货物运输任务需要完成，以1，2，m表示，已知任务的货运量为 (=1，2， ，m)，且，求满足货运需求的费用最小的车辆运输线路。为构造数学模型方便，将物流配送中心编号为0，任务编号为1，2， ，m，任务及物流配送

5、中心均以点 (=0，1，2，m)来表示。定义变量如下：则分送式配送车辆优化调度问题一般数学模型如下：模型中， 表示从点到点的运输成本，它的含义可以是距离、费用、时间等；为车辆容量；为支路消去约束，即消去构成不完整线路的解。图1 支路示意图如图1所示，两条支路均满足分配约束，但没有构成一条完整的线路，因此不是问题的解。在实际问题中，分送式配送问题，其车辆路线选择不仅要受到车辆容量限制，而且有时还会受到运行距离、运行时间、不同区段的车速以及运行途中的障碍物、司机的短时间休息等因素影响。现在假设一条线路上允许的最大的运行距离为l，则有约束条件：将该约束条件加到上述模型中，于是得到带有运行距离约束的配

6、送车辆优化调度模型。6模型求解6.1节约算法6.1.1算法原理算法基于节约法的基本思想。设P0为配送中心，分别向用户 和 送货。P0到 和 的距离分别为 和， 两个用户Pi、 之间的距离为 ，送货方案只有两种，即配送中心ro向用户Pi、P；分别送货和配送中心向用户Pi、P；同时送货，如图2所示。比较两种配送方案：图2 节约法方案方案(b)配送线路为：，配送距离为：；方案(b)配送线路为：，配送距离为：。显然,我们用表示路线节约值，即方案(b)比方案(a)节约的配送路程 ：即是将点和点连接在一条线路上的距离节约值，值越大，说明把和连接在一起时总路程减少越多。旅行商问题的c-w节约算法就是基于这种

7、最大节约值准则，首先对两点进行比较，把不在线路上的点插入线路，已在线路中的点合并为一集合 ，直到所有点都被 安排到线路中。对于分送式配送问题，在连接点对时需 要考虑车辆的容量约束和运行路程约束，即一条线路上 各任务的货运量之和应不大于车辆的容量和车辆运行路 程不大于额定路程。 6.1.2 算法步骤 根据前述求解原理，给出具体求解步骤如下:s t e p 1 ：计算，令；s t e p 2 ：在内按从大到小的顺序排列；s t e p 3 ： 若，则终止，否则对第一项，考察对应的，若满足下述条件之一：( 1 )点和点均不在已构成的线路上；( 2 )点或点在已构成的线路上，但不是线路内点；( 3 )

8、点和点位于已构成的不同线路上，均不是内点，且个是起点，一个是终点。则转下步， 否则转s t e p 7。s t e p 4 ：考察点和点连接后的线路上总运量，若，则转下步，否则转s t e p 7 。s t e p 5 ：考察点和点连接后的线路上总路程 L， 若 L l，则转下步，否则转 s t e p 7 。s t e p 6 ：连接点和点。s t e p 7 ：令，转s t e p 3。6.2求解结果某物流公司现在需要制定六个货运站A、B、C、D、E、F之间的四条路线的往来运输业务。已知各条路线的起点、终点城市之间的运行时间及每个小时的运输次数见下表。又知每辆货车每次装卸的时间各需1小时，

9、每辆货车的载货量为154吨,货车运行的平均速度28.则该物流公司应如何配备货车，才能满足要求。路线起点货运站终点货运站每小时运输量(吨)1ED4602BC3003AF1504DB150距离(公里)ABCDEFA02856392196196B28084364224224C56840420140140D3923644200476560E196224140476084F196224140560840把C地分为C1和C2，D分为D1、D2和D3，如表1，则符合上面所建模型的条件：，由此列出表2表1 各货运站的货物需求量客户ABC1C2D1D2D3EF需求量01501501501531531540150

10、表2 物流配送中心及各货运站之间的距离PjDPiPABC1C2D1D2D3EFP00285656392392392196196A00285656392392392196196B282808484364364364224224C156568400420420420140140C256568400420420420140140D1392392364420420000476560D2392392364420420000476560D3392392364420420000476560E196196224140140476476476084F196196224140140560560560840所耗时间

11、分为运输时间和装卸时间，运输时间由求出，列出表3如下。表3 物流配送中心及各货运站之间所耗时间PjDPiPABC1C2D1D2D3EFP0012214141477+2A0012214141477+2B1103+23+213+213+213+288C1223+20015151555C2223+20015151555D1141413+2151500017+220D2141413+2151500017+220D3141413+2151500017+220E7785517+217+217+203F7+27+285520202030约束条件为每小时运输量，为便于计算，用各连线所耗时间乘以其各自实际距离，

12、得出各货运站之间的假想距离，列出表4如下。表4 物流配送中心及各货运站之间的假想距离PjDPiPABC1C2D1D2D3EFP002811211254885488548813721764A002811211254885488548813721764B2828042042054605460546017921792C111211242000630063006300700700C211211242000630063006300700700D154885488546063006300000904411200D254885488546063006300000904411200D3548854885460

13、63006300000904411200E1372137217927007009044904490440252F1764176417927007001120011200112002520首先计算各点对间连接的距离节约值：例如，连接点A和B时，有：类似地，可得到连接其他各点对时的距离节约值，按从大到小的顺序示于表5中。表5 点对间连接的距离节约值序号路线节约值序号路线节约值1EF28849BF02C1F117618BC1-2802C2F117618BC2-2804C1E78420BE-3924C2E78421C1D1-7006BD15621C1D2-7006BD25621C1D3-7006BD3

14、5621C2D1-7009AB021C2D2-7009AC1021C2D3-7009AC2027D1E-21849AD1027D2E-21849AD2027D3E-21849AD3030D1F-39489AE030D2F-39489AF030D3F-3948根据表5所示的的顺序，逐项考察对应的线路，点对之间的连接过程如表6所示。表6 点对间的连接过程线路连接否EF0+150qC2F150+150qC1E150+0qC2E150+0qBD2150+153qBD3150+154qAB0+150qAC10+150qAC20+150qAD10+153qAD20+153qAD30+154qAE0+0qAF0+150qBC1150+150qBC2150+150qBE150+0qC1D2150+153qC1D3150+154qC2D1150+153qC2D2150+153qC2D3150+154qD1E153+0qD2E153+0qD3E154+0qD2F153+150qD3F154+150q由表6可得最终配送线路为：线路1：P-A-F-P线路2：P-B-E-C-P线路3：P-E-D-P线路4：P-D-E-B-P按照所得的最终配送线路，可以使此物流公司所有货车行驶路程最短，可以减少消耗的费用。7.优缺点分析以旅行商问题的Cw节约算法为基础，构造了连接点对时对线路上各需求点的最小需求量约