现代物流企业车辆优化调度研究综述.doc

现代物流企业车辆优化调度研究综述
王旸
摘要：物流配送车辆优化调度问题（Vehicle Routing Problem，简称 VRP）是一类具有广泛应用的强NP难题，本文综合国内外多种参考文献， 阐述了该问题的定义，分类以及研究现状，综述了VRP问题的研究现状以及在不同情况下主要算法，并对所述的几种算法的优缺点做出了先关分析，最后就目前该问题的研究发展情况做了简要分析和进一步的展望。

引言
对于现代物流企业，如何合理的调度运输工具，优化运输线路，降低物流成本，是物流管理的一个核心问题，直接影响和决定物流企业的核心竞争力。同时，车辆优化调度问题的研究对于社会发展也具有重要意义。因此本文基于这个原因才对车辆调度问题进行研究。

1.VRP问题研究背景
1.1 VRP问题分类
针对物流配送车辆优化调度问题,有的学者是根据问题的空间特性和时间特性的相对重要性来划分的(Bodin 1983)。一般认为,当不考虑时间要求,仅根据空间位置安排线路时称车辆路线安排问题(vehicle Rout访9 Problem,简记VRP);考虑时间要求安排路线时称为车辆调度问题(vehicle schedul加9 Problem,简记目前研究的车辆优化调度问题都是以上分类中的一种或几种的综合,对于此类问题的
求解可分为三大类:精确求解、启发式算法、智能算法。精确算法指可求出最优解的算法,精确算法主要有:分支界定法、割平面法、网络流算法、动态规划法。精确算法的计算量一般随着问题规模的增大呈指数增长,因此在实际中其应用范围很有限。启发式算法并不追求问题的最优解,而是强调问题解的满意性,只要决策者认为所得到的解能够较好的满足要求就可以了。目前已经提出的启发式算法很多,分类也相当多,主要有:构造算法,不完全优化算法,改进算法等。而智能算法(有的也叫网络启发式算法)包含遗传算法、蚁群算法、神经网络方法和模拟退火算法等。同时考虑空间位置和时间要求的称为混合问题(简记VRP&VSP),也有不区分两者的,如有具体约束则加上定语,如将有时间要求的车辆调度问题称为VRP(vehicle Routing Problem withTime。windows)等。将货运车辆优化调度问题分了两大类:一是非满载车辆优化调度问题;二是满载车辆优化调度问题。
1.2 VRP问题研究现状
目前研究的车辆优化调度问题都是以上分类中的一种或几种的综合,对于此类问题的求解可分为三大类:精确求解、启发式算法、智能算法。精确算法指可求出最优解的算法,精确算法主要有:分支界定法、割平面法、网络流算法、动态规划法。精确算法的计算量一般随着问题规模的增大呈指数增长,因此在实际中其应用范围很有限。启发式算法并不追求问题的最优解,而是强调问题解的满意性,只要决策者认为所得到的解能够较好的满足要求就可以了。目前已经提出的启发式算法很多,分类也相当多,主要有:构造算法,不完全优化算法,改进算法等。而智能算法(有的也叫网络启发式算法)包含遗传算法、蚁群算法、神经网络方法和模拟退火算法等。
2．VRP问题主要算法及分析
一：精确算法
1分支定界法
2割平面法
3动态规划法
二：启发式算法
1节约算法
2邻接算法
3插入算法
4扫除算法
三：现代启发式
1禁忌搜索算法
2遗传算法
3模拟退火算法
4蚁群算法