物流配送车辆调度路径优化问题算法研究

1、物流配送车辆调度途径优化问题算法研究摘 要：近年来，我国物流运行总体平稳，物流需求规模保持较高增幅，物流业增加值平稳增长，但经济运行中的物流本钱与其他兴隆国家相比仍然较高。车辆调度配送途径优化问题同时涉及能源消耗和废物的排放问题，随着人们对环境问题给予越来越多的关注，因此其一直是国内外研究的热点。同时物流配送车辆调度问题在企业运营中起着重要的作用。文章首先简介了车辆调度问题，然后从研究的准确算法和启发式算法两方面较为详细地阐述了国内外有关车辆调度问题的研究现状，总结了研究中存在的问题，并对物流算法的开展进展了展望。关键词：车辆调度;途径优化;启发式算法中图分类号：F253 文献标识码：AAbs

2、tract： In recent years， domestic logistics is developing steady in a whole， the demand of logistics is also in a high amplification. The logistics industry is in a stable increase while the operating cost is still higher than that of developed countries. For that vehicle routing problem both relates

3、 to energy consumption and wastage emission， VRP is a research hotspot at home and abroad under the case that more and more attention are paid to environment protection. Vehicle scheduling holds an important position in enterprise operating. This article first gives a brief description of VRP， then

4、gives a detailed overview of existing algorithms including exact algorithm and heuristic algorithm from home and abroad. Based on the above in formation， this article makes a prospect of algorithms on logistics.Key words： vehicle scheduling; routing optimization; heuristic algorithm0 引 言随着人们对环境问题给予越

5、来越多的关注，关于要求企业保护环境的法律条文相继增加。其中，减少废物的排放量和能源的消耗成为法律规定的两个重要内容。物流作为一个与环境关系亲密的行业，车辆调度配送途径优化问题同时涉及能源消耗和废物的排放问题，因此其一直是国内外研究的热点。综上所述，作为继原材料、劳动力以外的“第三利润源泉，实现物流合理化具有重要的经济意义与现实意义。一方面，物流配送车辆途径优化有助于企业降低物流本钱，进步运作效率，从而增加企业利润。另一方面，通过缓解交通压力，减少资源消耗和对环境的污染真正做到环保物流。1 车辆调度问题描绘物流配送车辆途径优化问题最早是由线性规划之父Dantzig和Ramser2在1959年提出

6、，该问题是交通运输管理、智能救灾调度指挥系统、网络作业调度管理系统、现代物流系统、物流网等应用、研究领域中的根本问题之一，也是最重要的调度问题之一。配送车辆调度问题要解决的问题3是车辆从配送中心这里的配送中心是个广义概念，指的是车辆的出发地，包括物流中心、配送中心、仓库、车场等出发去完成一些配送任务，当各任务量较小小于车辆容量时，为了进步车辆的利用率，可安排一辆车执行几项运输任务。这时，如何安排车辆的道路，使得既满足各任务的需求并完成任务，而又使总本钱最小这里的总本钱指的是一个广义概念，包括时间最少、运营费用最少等涉及的就是配送车辆途径优化问题。由以上各要素组成的VRP简单示意图如图1所示：3

7、 VRP的分类4 VRP的根底理论=cx+cx+cx;3约束条件：;其中，“maxmin是“maximizeminimize的缩写，含义为“最大化最小化。4.2 组合优化理论。组合优化binatorial Optimization，又称离散优化，是运筹学的一个经典分支。它研究的是在离散的、有限的数学构造即问题的可行解集中，求满足约束条件的目的函数最大化max或最小化min。组合优化问题的数学模型可描绘为：maxminfxs.t.其中，fx为目的函数，gx为约束函数，x为决策变量，D表示有限个点组成的集合。一个组合优化问题可以简单地表示为三个参数D，F，f。其中D为决策变量定义域，F为可行解区域

8、，满足F=x|xD， gx0，F中的任何一个元素称为该组合优化问题的可行解，f为目的函数，满足的可行解称为该组合优化问题的最优解7。组合优化的特点是可行解集合为有限点集，且有可行解一定有最优解。由直观可知，只要将D中的有限个点逐一判别是否满足条件函数gx的约束和比较各自所对应的目的值fx的大小，即可得到该问题的最优解。在现实生活中，大量优化问题就是从有限个状态中选取最好的一个，因此属于组合优化问题。minZ=xys.t.5 VRP的优化算法车辆运输调度问题的求解算法有很多种，但究其本质来讲，根本可分为最优化算法Exact Algorithm和启发式算法Heuristic Algorithm9。

9、5.1 最优化算法。最优化算法，也称为准确算法，是指可以通过有限的严谨计算和推理，运用整数规划、线性规划和非线性规划等数学规划技术或数据构造得到优化问题的最优解的算法。在物流车辆运输调度问题中，所谓最优化算法就是找到一组途径集合，使得其目的函数值比其它任何一组可行途径集合的目的函数值更好。5.2 启发式算法。启发式算法是相对于最优化算法提出的，指通过对过去经历的归纳推理及实验分析来解决问题的方法，即基于直观推断或经历构造的算法。因此，启发式算法要求分析人员运用自己的感知和洞察力，从与研究问题有关且比较详细的模型及算法中寻求互相间的联络，从中得到启发，发现适宜于解决该问题的思路和途径。启发式算法

10、指根据某种启发式的信息对的可行解进展改善，通过假设干次的迭代获得相对满意的解。与准确算法相比，启发式算法得到的解不一定是最优解，但很有可能是近似解。同时，启发式算法实现起来相对简单，并且可以在相对短的时间内快速地找到满意解。为此研究人员主要把精力放在构造高质量的启发式算法上。目前专家已提出很多求解车辆运输调度问题的启发式算法，主要分为经典启发式算法和现代启发式算法两类。车辆途径的启发式算法最早由Clarke和Wright提出的用于解决车辆数不固定的节约法The Savings Method13，Gillett和Miller提出的先分群再安排道路的扫描法Sweep Method14，Bramel

11、和Simchi-Levi提出的基于选址问题转化的LBH算法15，Cullew，Jarvis和Ratliff提出的两段法16，Fisher和Jaikumar建立的先分组后安排道路的一般分配算法17，Christofides和Minggozzi等建立的不完全树搜索算法18，Pureza和Franca研究的禁忌搜索算法Tabu Research，TS19等。这些算法为求解车辆途径问题提供了有效的方法，但也存在着一系列问题。如节约法可以列出各点对时间的节约量，并按节约量从大到小构造途径，因此具有运算速度快的优点，但存在未组合点零乱、边缘点难于组合的缺点;扫描法属于非渐近优化;LBH算法那么存在问题转化

12、费事且选址问题本身难解等。6 完毕语关于物流配送车辆优化调度研究的算法已广泛应用于消费和生活的各个方面，并已经获得了良好的经济效益。随着我国国民经济安康稳步地向前开展，尤其是在电子商务开展迅速的大背景下，现代物流业开展非常迅速，这些都对以运输为中心的物流配送活动提出了更高的要求。如何针对各种地形的条件和各行业物流配送运输的特点，结合不同的启发式算法进展优势互补和消除缺陷，设计出通用性好、运算速度快、精度高的优良算法，这将是今后研究开展的方向。参考文献：3 李军，郭耀煌. 物流配送车辆优化调度理论与方法M. 北京：中国物资出版社，2001.4 陈震. VPN技术及其应用的研究J. 电脑知识与技术

13、，20224：798-799.5 占书芳. 并行遗传算法在带软时间窗车辆途径问题中的应用研究D. 武汉：武汉理工大学，2022.6 刘宝碇，赵瑞清，王纲. 不确定规划及应用M. 北京：清华大学出版社，2022.7 郎茂祥. 配送车辆优化调度模型与算法M. 北京：电子工业出版社，2022.8 刘东圆. 运输才能限制下的运输问题研究D. 北京：北京交通大学，2022.11 Kohl N.， Madsen O. An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangean

14、 RelocationJ. Operations Research， 1997，45：395-406.-349.15 Bramel J.， Simchi-Levl D. A Location Based Heuristic for General Routing ProblemsJ. Operations Research， 1995，43：649-660.18 Christofides N.， Minggozzi A.， Toth P. The Vehicle Routing ProblemM. binatorial Optimization. Chechester： Wiley， 1979：315-338.19 Pureza V. M.， Franca P. M. Vehicle Routing Problems Via Tabu Search MetaheuristicsR. Technical Report CRT-747， Centre de Recherchesurles Transports，