车辆调度算法研究及其应用文献综述

《车辆调度算法研究及其应用文献综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文献综述车辆调度算法研究及其应用一、前言部分车辆调度问题是现代物流系统优化中关键的一环，也是开展电子商务不可缺少的内容。对车辆调度优化理论与算法进行系统研究是构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础[1]。车辆调度问题是运筹学与组合优化领域的研究热点。有效的调度车辆，不仅可以提高物流工作效率，而且能够为及时生产模式的企业提供运输上的保障，从而实现物流管理科学化。由于该问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问题，研究该问题具有很重要的理论意义和实际意义

2、。1.VRP（VehicleRoutingProblem）问题描述及其分类VRP问题一般可定义为：对一系列的装货点或卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(货物需求量、发送量、车辆容量限制、行驶里程限制、时间限制)下，达到一定的目标(路程最短、时间最小、费用最省、车辆数目最少等)。由于该问题研究范围非常广，根据其网络性能大致可以分为两类：一类为静态VRP(StaticVRP,SVRP)，一类为动态VRP(dynamicVRP,DVRP)。(1)静态VRP问题描述SVRP问题是VRP

3、中较简单的一类问题，是大部分研究者研究的热点。该问题具有一个很重要的特征：在安排初始路线时，和路线相关的所有信息已知，并且在安排路线以后其相关信息始终保持改变[2]。以下列举了一些常见的SVRP问题:仅考虑车辆容量限制的VRP(CVRP)、带时间窗的VRP(VRPTW)、带有回收的VRP(VRPwithbackhauls)、带有集派的VRP(VRPPD)。除此以外，还有许多其它CVRP的延伸问题，如顾客有优先权，考虑卸货时间、装卸时间、等待时间等，甚至综合了以上不同的特征。这些问题的相关信息均已知且保持不变[3]

4、。(2)动态VRP问题描述所谓DVRP，是指在安排初始路线时，并不是和路线相关的所有信息都为已知，并且初始路线安排以后，其相关信息可能发生改变。DVRP研究范围较广，需求不确定、动态网络、服务车辆不确定、提供数据有偏差等都属于DVRP的研究范畴。从网络性能角度，DVRP可以分为以下三种类型：1)时间依赖型VRP(TDVRP)。2)概率VRP(PVRP)。车辆运行时间以离散或连续概率发生变化。在这种网络中可用期望运行时间代替路径运行时间，再进行问题的求解。目前对该问题在最短路中研究比较多，一般是求得存在长度不超过给

5、定值的路线概率及所给出路线为最短路的概率等[4]。3)时间依赖且概率变化的VRP。2.VRP问题算法描述(1)插入算法插入算法是指通过k步迭代时，将第k个节点插入到路线中。算法的关键在于确定在第k+1步可以被插入到路线中的点以及该点的最佳插入位置。因此，该算法由两个关键的部分组成。第一部分是节点选择阶段，即确定下一步被插入到路线中的顾客节点；第二部分是路径插入阶段，即确定所选择的顾客节点在路线中的最佳插入位置[5]。(2)节约算法节约算法是一类最为经典的构造型启发式算法之一，该算法最早由Clark和Wright于

6、1964年提出[6]，通常被简称为C-W算法。该算法的思想是：根据顾客点之间连接可以节省的距离（节约值）最大的原则，将不在线路上的顾客点依次插入到路线中，直到所有的点都被安排进路线为止。(3)最短路径算法用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法[7]。迪杰斯特拉提出的Dijkstra算法是最典型的最短路径算法[8]。(4)遗传算法遗传算法（Gen

7、eticAlgorithm，简称GA）是美国J.Holland和他的学生于1975年受生物进化论的启发而提出并建立发展起来的。其基本思想是借鉴大自然生物进化中“适者生存”的规律，通过对产生的解（“父代”）不断操作（包括复制、交叉、变异和竞争）以产生新的解（“子代”），如此反复迭代，最终收敛到“最适应环境”的个体，从而得到相对比较好的解[9]。综上所述，各种优化方法在一定情况下都有各自的优点，都有解决某一问题的优越性。最优化算法有一个共同的特点就是可以求得最优解，但不适应现在的复杂的车辆优化问题，尤其是对多配送点的

8、大型配送服务，相对求得最优解比较费时费力，且难以实现；而传统的启发式算法比最优化算法相对好些，但仍有不太适用于现在于现在实际遇到的问题，和现代启发式算法相比有些不足，但可以将各种算法结合使用，这样就更方便使用解决实际当中遇到的各种问题。求解VRP问题时，我们旨在得到一系列路线，车辆按照该路线来服务顾客，在满足顾客需求的同时，使得总的运输费用最小。在设计这些路线时，还要根据