内容发布更新时间 : 2024/5/19 1:59:50星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

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

作者：王海玲 卢允辉

来源：《数码设计》2019年第03期

龙源期刊网 http://www.qikan.com.cn

摘要：本文通过对于车辆调度现状建立了单车满载车辆的分送优化模型。首先对问题进行分析，将模型各个需求点的最小需求量作为约束，以总运输路径最短为目标，来确定车辆配送路线。并以节约算法的基本原理为基础，对模型进来具体求解优化。最后给出优化后的处理方法的优缺点分析，并且对解结果进行讨论和再优化。 关键词：车辆调度；节约算法；优化

中图分类号：F224 文献标识码：A 文章编号：1672-9129（2019）03-0006-05 Abstract： In this paper， the distribution optimization model of vehicle load vehicle is established. Firstly， the problem is analyzed， and the minimum demand of each demand point of the model is used as the constraint， and the route of vehicle distribution is determined by the shortest path of the total transportation path. The factors affecting the transportation path are the sum of the

龙源期刊网 http://www.qikan.com.cn

distribution of each demand point and the driving distance of the vehicle. Based on the analysis， the model is based on the basic principle of the saving algorithm. Finally， the advantages and disadvantages of the optimized processing method are analyzed， the results are discussed and optimized.

Keywords： Vehicle routing； C-W； Optimizing 引言

在物流系統中，时常会遇到车辆的路径规划问题，而求解方法有很多种，可分为最优化算法、动态求解算法和启发式算法三大类。C-W节约算法属于启发式算法。是一种被用来解决车辆数不固定情况下的车辆调度问题。该算法从起始出发按所需访问的所有点作出N-1条线路，计算合并任意两条路径后与之前未进行优化时的路径相比较，得出合并线路后所节约的路程量；然后再将节约的路程量按大小进行排序；最后依据排序结果以及附加的约束条件对合并后的路径进行判断线路是否合理，直到所有需要访问的点都被安排到线路当中。

本文根据对于车辆调度现状，建立了车辆的配送优化模型。通过计算，给出了优化后的处理方法对优缺点进行分析，最后对于求解结果进行讨论和再优化。 1 车辆调度问题概述

车辆调度问题最早是由Dantzig和Ramser于1959年提出来的[1]，并且许多现实生活中的的实际问题的理论都可以归结于这一问题。由于应用前景广阔，所以成为运筹学与组合优化领域的研究热点[2]。随着越来越多的专家学者对车辆调度问题的研究不断深入和发展，最近几十年来，不但获得了很多有意义的成果，并且使得车辆调度在当下现实生活中能更好的被节约算法所解决。

车辆运输调度问题一般定义为：对一系列装货点和卸货点规划适当的行车路线，使车辆有序地通过它们，满足一定的约束条件，如时间窗口约束、车辆容量限制、车辆行驶里程限制、司机最大工作时间限制等，达到一定的目标如：车辆行驶路程最短、运输费用最少、使用车辆数最少、服务质量最高等[3]。

对于车辆调度问题，许多学者根据不同的标准，从不同的角度出发对车辆调度问题进行了不同的分类：

按照车辆载货物的情况分，有满载问题（货运量不小于整车负荷量）和非满载问题（货运量小于车辆容量或者一辆车服务多位客户）

按照车辆类型分，有单车辆类型问题（使用的所有车辆相同）和多车辆类型的问题（执行任务的车辆的类型和负荷能力不完全相同）。