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

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

关键词：车辆调度;路径优化;启发式算法

中图分类号：F253 文献标识码：A

Abstract： 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 deve☤loped countries. For that vehicle routing problem both relates 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 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 algorithm

0 引 言

随着人们对环境问题给予越来越多的关注，关于要求企业保护环境的法律条文相继增加。其中，减少废物的排放量和能源的消耗成为法律规定的两个重要内容。物流作为一个与环境关系密切的行业，车辆调度配送路径优化问题同时涉及能源消耗和废物的排放问题，因而其一直是国内外研究的热点。

综上所述，作为继原材料、劳动力以外的“第三利润源泉”，实现物流合理化具有重要的经济意义与现实意义。一方面，物流配送车辆路径优化有助于企业降低物流成本，提高运作效率，从而增加企业利润。另一方面，通过缓解交通压力，减少资源消耗和对环境的污染真正做到环保物流。

1 车辆调度问题描述

物流配送车辆路径优化问题最早是由线性规划之父Dantzig和Ramser[2]在1959年提出，该问题是交通运输管理、智能救灾调度指挥系统、网络作业调度管理系统、现代物流系统、物流网等应用、研究领域中的基本问题之一，也是最重要的调度问题之一。

配送车辆调度问题要解决的问题[3]是车辆从配送中心（这里的配送中心是个广义概念，指的是车辆的出发地，包括物流中心、配送中心、仓库、车场等）出发去完成一些配送任务，当各任务量较小（小于车辆容量）时，为了提高车辆的利用率，可安排一辆车执行几项运输任务。这时，如何安排车辆的路线，使得既满足各任务的需求并完成任务，而又使总成本最小（这里的总成本指的是一个广义概念，包括时间最少、运营费用最少等）涉及的就是配送车辆路径优化问题。

由以上各要素组成的VRP简单示意图如图1所示：

3 VRP的分类

4 VRP的基础理论

=c■x■+c■x■+…+c■x■;（3）约束条件：■;其中，“max（min）”是“maximize（minimize）”的缩写，含义为“最大化（最小化）”。

4.2 组合优化理论。组合优化（Combinatorial Optimization），又称离散优化，是运筹学的一个经典分支。它研究的是在离散的、有限的数学结构即问题的可行解集中，求满足约束条件的目标函数最大化（max）或最小化（min）。

组合优化问题的数学模型可描述为：

maxminfx

s.t.■

其中，fx为目标函数，gx为约束函数，x为决策变量，D表示有限个点组成的集合。一个组合优化问题可以简单地表示为三个参数D，F，f。其中D为决策变量定义域，F为可行解区域，满足F=x|x∈D， gx≥0，F中的任何一个元素称为该组合优化问题的可行解，f为目标函数，满足的可行解称为该组合优化问题的最优解[7]。组合优化的特点是可行解集合为有限点集，且有可行解一定有最优解。由直观可知，只要将D中的有限个点逐一判别是否满足条件函数gx的约束和比较各自所对应的目标值fx的大小，即可得到该问题的最优解。在现实生活中，大量优化问题就是从有限个状态中选取最好的一个，因而属于组合优化问题。

minZ=■■x■y■

s.t.■

5 VRP的优化算法

车辆运输调度问题的求解算法有很多种，但究其本质来讲，基本可分为最优化算法（Exact Algorithm）和启发式算法（Heuristic Algorithm）[9]。

5.1 最优化算法。最优化算法，也称为精确算法，是指能够通过有限的严谨计算和推理，运用整数规划、线性规划和非线性规划等数学规划技术或数据结构得到优化问题的最优解的算法。在物流车辆运输调度问题中，所谓最优化算法就是找到一组路径集合，使得其目标函数值比其它任何一组可行路径集合的目标函数值更好。

5.2 启发式算法。启发式算法是相对于最优化算法提出的，指通过对过去经验的归纳推理及实验分析来解决问题的方法，即基于直观推断或经验构造的算法。因此，启发式算法要求分析人员运用自己的感知和洞察力，从与研究问题有关且比较具体的模型及算法中寻求相互间的联系，从中得到启发，发现适合于解决该问题的思路和途径。

启发式算法指根据某种启发式的信息对已知的可行解进行改善，通过若干次的迭代获得相对满意的解。与精确算法相比，启发式算法得到的解不一定是最优解，但很有可能是近似解。同时，启发式算法实现起来相对简单，并且可以在相对短的时间内快速地找到满意解。为此研究人员主要把精力放在构造高质量的启发式算法上。目前专家已提出很多求解车辆运输调度问题的启发式算法，主要分为经典启发式算法和现代启发式算法两类。

车辆路径的启发式算法最早由Clarke和Wright提出的用于解决车辆数不固定的节约法（The Savings Method）[13]，Gillett和Miller提出的先分群再安排路线的扫描法（Sweep Method）[14]，Bramel和Simchi-Levi提出的基于选址问题转化的LBH算法[15]，Cullew，Jarvis和Ratliff提出的两段法[16]，Fisher和Jaikumar建立的先分组后安排路线的一般分配算法[17]，Christofides和Minggozzi等建立的不完全树搜索算法[18]，Pureza和Franca研究的禁忌搜索算法（Tabu Research，TS）[19]等。这些算法为求解车辆路径问题提供了有效的方法，但也存在着一系列问题。如节约法可以列出各点对时间的节约量，并按节约量从大到小构造路径，因此具有运算速度快的优点，但存在未组合点零乱、边缘点难于组合的缺点;扫描法属于非渐近优化;LBH算法则存在问题转化麻烦且选址问题本身难解等。

6 结束语

关于物流配送车辆优化调度研究的算法已广泛应用于生产和生活的各个方面，并已经取得了良好的经济效益。随着我国国民经济健康稳步地向前发展，尤其是在电子商务发展迅速的大背景下，现代物流业发展十分迅速，这些都对以运输为中心的物流配送活动提出了更高的要求。如何针对各种地形的条件和各行业物流配送运输的特点，结合不同的启发式算法进行优势互补和消除缺陷，设计出通用性好、运算速度快½、精度高的优良算法，这将是今后研究发展的方向。

参考文献：

[3] 李军，郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001.

[4] 陈震. VPN技术及其应用的研究[J]. 电脑知识与技术，2009（4）：798-799.

[5] 占书芳. 并行遗传算法在带软时间窗车辆路径问题中的应用研究[D]. 武汉：武汉理工大学（硕士学位论文），2006.

[6] 刘宝碇，赵瑞清，王纲. 不确定规划及应用[M]. 北京：清华大学出版社，2003.

[7] 郎茂祥. 配送车辆优化调度模型与算法[M]. 北京：电子工业出版社，2009.

[8] 刘东圆. 运输能力限制下的运输问题研究[D]. 北京：北京交通大学（硕士学位论文），2009.

[11] Kohl N.， Madsen O.. An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangean Relocation[J]. Operations Research， 1997，45：395-406.

-349.

[15] Bramel J.， Simchi-Levl D.. A Location Based Heuristic for General Routing Problems[J]. Operations Research， 1995，43：649

-660.

[18] Christofides N.， Minggozzi A.， Toth P.. The Vehicle Routing Problem[M]. Combinatorial Optimization. Chechester： Wiley， 1979：315-338.

[19] Pureza V. M.， Franca P. M.. Vehicle Routing Problems Via Tabu Search Metaheuristics[R]. Technical Report CRT-747， Centre de Recherchesurles Transports， Montreal， 1991.

[21] Holland J. H. Adaptation in Natural and Artificial System[M]. Cambridge. Massachusetts： MIT Press， 1975.

[24] Yang Xin-she. Nature-inspired Metaheuristic Algorithms[M]. Luniver Press， UK. 2008.