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

《基于节约算法的车辆调度优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、约束，求解出总路径最短的车辆运输线路。2模型假设1.车辆行驶中始终做匀速直线运动，即在任何区段车速都相同。2.公路系统畅通无阻，不考虑中途发生故障堵车等情况。3.不考虑司机短时间休息之类的人为因素。4.各路径发车频度相同。5.将车辆装卸时间认为是车辆总运输时间的一部分。6.货运地中之一为物流装配中心，全部车辆从物流装配中心出发，最后回到装配中心。143符号说明车辆拥有的容量表示点到点的距离点和点连接后的线路上总运量已知任务i的货运量点和点连接在一条线路上的距离节约值表示配送中心4模型的理论基础本文中的物流配送路径优化问题可以描述为:从配送中心(物流

4、据点)用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，并且某些需求点的需求量超过一辆货车的最大额载。要求根据货车的载重和行驶距离合理安排车辆路线，使总运距最短。(1)因为所送货物总重量超过一辆货车的额载，所以需要若干辆货车一起送货。(2)每辆车一次可以给几个需求点送货，从配送中心出发到返回称之为一条行驶路径。(3)运输成本的含义可以是车辆行驶距离、费用和时间等，本文用行驶距离来表示运输成本。145模型建立建立如下模型：有一个物流配送中心，拥有多台容量为q的车辆，现在有m项货物运输任务需要完成，以1，2，⋯⋯，m表示，

5、已知任务的货运量为(=1，2，⋯⋯，m)，且，求满足货运需求的费用最小的车辆运输线路。为构造数学模型方便，将物流配送中心编号为0，任务编号为1，2，⋯⋯，m，任务及物流配送中心均以点(=0，1，2，⋯⋯，m)来表示。定义变量如下：则分送式配送车辆优化调度问题一般数学模型如下：模型中，表示从点到点的运输成本，它的含义可以是距离、费用、时间等；为车辆容量；为支路消去约束，即消去构成不完整线路的解。14图1支路示意图如图1所示，两条支路均满足分配约束，但没有构成一条完整的线路，因此不是问题的解。在实际问题中，分送式配送问题，其车辆路线选择不仅要受到车辆容

6、量限制，而且有时还会受到运行距离、运行时间、不同区段的车速以及运行途中的障碍物、司机的短时间休息等因素影响。现在假设一条线路上允许的最大的运行距离为l，则有约束条件：将该约束条件加到上述模型中，于是得到带有运行距离约束的配送车辆优化调度模型。146模型求解6.1节约算法6.1.1算法原理算法基于节约法的基本思想。设P0为配送中心，分别向用户和送货。P0到和的距离分别为和，两个用户Pi、之间的距离为，送货方案只有两种，即配送中心r'o向用户Pi、P；分别送货和配送中心向用户Pi、P；同时送货，如图2所示。比较两种配送方案：图2节约法方案方案(b)配送

7、线路为：，配送距离为：；方案(b)配送线路为：，配送距离为：。显然,我们用表示路线节约值，即方案(b)比方案(a)节约的配送路程：即是将点和点连接在一条线路上的距离节约值，值越大，说明把和连接在一起时总路程减少越多。旅行商问题的c-w节约算法就是基于这种最大节约值准则，首先对两点进行比较，把不在线路上的点插入线路，已在线路中的点合并为一集合14，直到所有点都被安排到线路中。对于分送式配送问题，在连接点对时需要考虑车辆的容量约束和运行路程约束，即一条线路上各任务的货运量之和应不大于车辆的容量和车辆运行路程不大于额定路程。6.1.2算法步骤根据前述求解

8、原理，给出具体求解步骤如下:step1：计算，令；step2：在内按从大到小的顺序排列；step3：若，则终止，否则对第一