车辆调度问题研究现状及展望

《车辆调度问题研究现状及展望》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、车辆调度问题研究现状及展望//.paper.edu-1-车辆调度问题研究现状及展望1李妍峰12，李军1，赵达11.西南交通大学经济管理学院，四川成都（610031）2.四川师范大学草堂校区，四川成都（610072）摘要：本文针对车辆调度问题(VRP)的研究现状，对车辆路径问题进行了描述，将该问题分为静态VRP和动态VRP两大类，分析了这两类VRP问题的特征并分别进行了分类。总结了近年来有关学者在建立模型及算法求解上的研究成果，最后展望了该领域未来的发展方向。关键词：车辆路径问题，静态VRP，动态VRP中图分类号：

2、F253.40引言车辆调度问题是运筹学与组合优化领域的研究热点。有效的调度车辆，不仅可以提高物流工作效率，而且能够为及时生产模式的企业提供运输上的保障，从而实现物流管理科学化。由于该问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问题，研究该问题具有很重要的理论意义和实际意义。1VRP问题描述及其分类VRP问题一般可定义为：对一系列的装货点或卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(货物需求量、发送量、车辆容量限制、行驶里程限制、时间限制)下，达到一定的目标(路程最短、

3、时间最小、费用最省、车辆数目最少等)。由于该问题研究范围非常广，根据其网络性能大致可以分为两类：一类为静态VRP(StaticVRP,SVRP)，一类为动态VRP(dynamicVRP,DVRP)。1.1静态VRP问题描述SVRP问题是VRP中较简单的一类问题，是大部分研究者研究的热点。该问题具有一个很重要的特征：在安排初始路线时，和路线相关的所有信息已知，并且在安排路线以后其相关信息始终保持改变[1]。以下列举了一些常见的SVRP问题。1)仅考虑车辆容量限制的VRP(CVRP)，该问题是一类最基本的VRP问题。

4、同类型的车辆从车场出发，向顾客派送实物，最后返回车场。目标函数为最小化总运输费用。2)带时间窗的VRP(VRPTW)，该问题是CVRP的延伸。若车辆必须在一定时段内服务顾客，为硬时间窗；若车辆可不在该时间窗内服务顾客，但须被惩罚，为软时间窗。3)带有回收的VRP(VRPwithbackhauls)，该问题也是CVRP的延伸。顾客被分为linehaul顾客和backhual顾客两类，车辆须派货给前者，须从后者集货。4)带有集派的VRP(VRPPD)。每一顾客对同一实物有一需求量和一供应量。若需求量小于供应量，则车辆

5、需要从该顾客收集实物；反之车辆需要派送实物给该顾客。除此以外，还有许多其它CVRP的延伸问题，如顾客有优先权，考虑卸货时间、装卸时间、等待时间等，甚至综合了以上不同的特征。这些问题的相关信息均已知且保持不变。1本课题得到国家自然科学基金资助项目(70271022)、高等学校博士学科点专项科研基金(20030613016)、教育部新世纪优秀人才支持计划项目(NCET-04-0886)和四川省教育厅青年基金项目(20058><#004699'>B025)的资助。//.paper.edu-2-1.2动态VRP问题描述相

6、对于SVRP，DVRP更贴近实际，但问题也变得更加复杂。对SVRP而言，相关信息不会发生变化，但在实际过程中，由于交通流量、天气变化、交通事故等因素的影响，行驶速度总在不断变化，从而导致各个路段上的运行时间也发生相应变化。对于该情况，传统SVRP的理论和方法已无法解决，对DVRP的研究已成为迫切需要。所谓DVRP，是指在安排初始路线时，并不是和路线相关的所有信息都为已知，并且初始路线安排以后，其相关信息可能发生改变[1]。DVRP研究范围较广，需求不确定、动态网络、服务车辆不确定、提供数据有偏差等都属于DVRP的

7、研究范畴[2]。从网络性能角度，DVRP可以分为以下三种类型：1)时间依赖型VRP(TDVRP)。对于该问题，路段(i，j)的运行时间依赖于i节点的出发时间。目前动态VRP的研究主要集中在这种类型。一般时间依赖函数处理为分段函数或单调函数。该类问题也有一些延伸，如带时间窗或动态随机需求，问题将变得更加复杂。2)概率VRP(PVRP)。车辆运行时间以离散或连续概率发生变化。在这种网络中可用期望运行时间代替路径运行时间，再进行问题的求解。目前对该问题在最短路中研究比较多，一般是求得存在长度不超过给定值的路线概率及所给

8、出路线为最短路的概率等[2]。3)时间依赖且概率变化的VRP。车辆运行时间为一离散或连续时间的随机过程，非常接近实际交通网络。该类型同样在最短路中研究比较多，尚未引入VRP领域。2VRP问题算法描述由于VRP问题具有很重要的理论意义和实际意义，在运筹学、人工智能、决策支持系统等著名杂志上都有很多相关的研究，其中很重要的一个研究方向就是关于如何求解VRP问题。2.1静态VR