单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 物流配送车辆路径问题,2.1,问题的描述及各组成部分特点,2.2,车辆路径问题的分类,2.3,车辆路径问题的研究现状和发展趋势,1,2.1,问题的描述及各组成部分特点,配送活动中的配送车辆行驶线路优化确定问题，是近二十多年来国际运筹学界的研究热点之一。,运筹学界将此类问题统称之为车辆路径问题,（,Vehicle Routing Problem,VRP,），,或车辆调度问题,（,Vehicle Scheduling Problem,VSP）。,一般描述是：对一系列给定的客户点，确定配送车辆行驶路线，使其从配送中心出发，有序地对它们进行服务，并在满足一定的约束条件下（如车辆载重量、客户需求量、服务时间限制等），使总运输成本达到最小（如使用车辆数最少、车辆行驶总距离最短等）。,一般把最小化车辆使用数作为第一优化目标，而最小化车辆行驶距离作为第二优化目标。,2,车辆路径问题的特点,1.,道路网,（,road network,）,弧表示路段，点表示道路交叉点、配送中心和客户。,弧的权,c,ij,表示其距离或行驶时间。,3,2.,客户,（,customer）,用图上的小圆点表示；,需运送或收取的货物量（需求量）,d,i,(,或,d,i,和,p,i,),；,要求提供服务的时间段，即时间窗（,time window）,在客户点所花费的服务时间,s,i,；,能用于服务该客户的车辆集合。,3.,配送中心（车场）,（,distribution center，depot）,用图上的小方点表示；,车辆行驶路线开始并终止于配送中心或某一个客户点；,其,特征由所配备的车辆种类和数量、以及所能处理的货物总量来描述。,4,4.,车辆,（,vehicle）,车辆是自备还是外租，完成任务后是否返回；,车辆的装载能力;,车辆使用费;,可用于进行货物装卸的设备.,5.,驾驶员,（,driver）,给驾驶员安排取送货任务时，必须符合工作时间方面的有关规定。,6.,路径编排中的限制条件,车辆的当前负载不能超过车辆的装载量；,客户只要求送货、取货、或取送货兼有；,在客户所要求的时间窗和驾驶员的工作时间内提供服务；,访问客户的顺序要求。,5,7.,行驶距离和行驶时间,必须知道客户点与客户点之间，配送中心与客户点之间的行驶距离和行驶时间。,8.,目标,（,objectives）,最小化总运输成本，其大小取决于所需要的车辆数（或线路数）、总行驶距离（时间）；,最小化与客户的不完全服务等有关的惩罚值；,均衡各线路上的行驶时间和车辆载重量。,6,2.2 车辆路径问题的分类,根据配送车辆完成配送任务后是否必须返回原出发点以及返回的形式，可将问题分为,闭合式,和,开放式,两大类。,在不需严格区分的场合，统称,VRP。,7,当车辆完成运输任务后必须返回原出发点时（即车辆的行驶路线是闭合式的），称之为,闭合式车辆路径问题,（,Closed VRP）,，,通常简称为车辆路径问题,（,VRP）。,8,当不要求车辆完成任务后返回原出发点，或者是若要求返回原出发点，则沿原去程路线返回时（即车辆的行驶路线是开放式的），称之为,开放式车辆路径问题,（,Open VRP，OVRP）,。,9,根据所包含的约束条件，问题又可进一步分类。以闭合式,VRP,为例，可归纳如下：,DCVRP,路程长度,VRPPD,装载能力 取送作业,CVRP,VRPPDTW,时间窗,VRPTW,回程运输,VRPBTW,VRPB,10,2.2.1 带装载能力的,VRP（Capacitated VRP，CVRP）,问题的特点,是,VRP,中的最基本型式。,所有客户都属于要送货的或要取货的，其需求量预先知道，且不能被分割。,车辆类型相同且都停放在一个配送中心。,对车辆只有装载能力限制。,问题的目标是最小化服务所有客户的总费用（即所需要的车辆数及其车辆行驶距离或行驶时间）。,问题的描述（可描述为如下的图论问题）,11,设,G,=(,V,A,),为一个完备图，其中,V,=0,n,为顶点集，,A,是弧集。顶点,i,=1,n,表示客户，而顶点0表示配送中心。有时配送中心用顶点,n,+1,来表示。,每条弧对应着一个非负的费用,c,ij,，,表示从点,i,到点,j,的行驶费用,。,在一些测试算例中，顶点与给定坐标的平面上的点相对应，且弧的费用,c,ij,被定义为对应于顶点,i,和,j,的两点间的欧氏距离。,y,j,j,(,x,j,y,j,),y,i,i,(,x,i,y,i,),x,j,x,i,12,在配送中心备有相同类型的车辆，每辆的装载能力为,C,。,每一条线路上的送货任务只由一辆车承担。,每个客户,i,有一个已知的需要送往交付的非负需求量,d,i,，,假设,d,i,C,。,服务所有客户至少所需要的车辆数,13,CVRP,是求一个具有最小总费用的由,K,条简单回路组成的集合（每个回路对应于一条配送车辆行驶线路），并满足,(1),每个回路从配送中心出发并返回配送中心；,(2),每个客户点只在一条回路上；,(3),一条回路上各客户点的需求量之和不超过车辆装载能力,C,。,总费用一般包括所使用的车辆数（即回路数）和车辆行驶费用两项。通常都认为，多用一辆车所带来的固定费用的增加，总是超过其因总行驶距离缩短所带来的节省，因此，一般把最小化车辆使用数作为第一优化目标，最小化行驶费用作为第二目标。,14,当备有的车辆类型不是同一种时，即有不同的装载能力,C,k,，,k,=1,K,，,则就为经常考虑的另一种变形。,CVRP,是,NP-,难的，并且是旅行商问题,（,TSP）,的一般化,。,在,TSP,中，要求确定一条经过图,G,中所有顶点的、费用最小的回路（哈密顿回路），当,CVRP,中的,C,d,i,和,K,=1,时就为此情形。,15,2.2.2 带路程长度的,VRP（Distance-Constrained and Capacitated VRP，DCVRP）,特点,既有车辆装载能力限制，又有最大路程长度限制。,描述,每条弧对应着一个非负的长度,t,ij,，,一般地，费用矩阵与长度矩阵相一致，即,c,ij,=,t,ij,。,每条线路上各弧的总长度不能超过线路的最大长度,L,。,当弧的长度代表的是行驶时间时，每个客户,i,就对应着一个服务时间,s,i,，,表示车辆必须在该客户点停留的时间长度。,16,2.2.3 带时间窗的,VRP（VRP with time windows，VRPTW）,除了车辆装载能力约束外，每个客户,i,都有一个与之相联系的要求提供服务的时间区间,a,i,b,i,。,1.,带,硬,时间窗的,VRP,（VRP with,hard,time windows,VRPHTW,）。,在不需要严格区分的场合，一般就称为带时间窗的,VRP。,特点,客户的服务必须在相应的时间窗内开始，车辆在客户点的服务时间长度为,s,i,。,当车辆提前到达客户点时，必须等待到时刻,a,i,才可开始服务。不允许在,b,i,之后到达并开始服务。,17,对于配送中心，设服务时间,s,0,=0，,时间窗,a,0,b,0,。,应注意的是，时间窗的要求导致每条线路,具有隐含的方向性，,以及,线路长度的限制,，最大线路长度为,L,=,b,0,。,描述,VRPHTW,是求一个具有最小总费用的由,K,条简单回路组成的集合，并满足,（1）、（2）、（3）,同,CVRP；,（4）,对每个客户,i,，,服务在时间窗,a,i,b,i,内开始，车辆的停留时间长度为,s,i,。,当,a,i,=0,b,i,=+,时,，,VRPHTW,就为,CVRP。,18,2.,带,软,时间窗的,VRP （VRP with,soft,time windows,VRPSTW,）,时间窗要求是软的，即允许服务的开始时间有所偏离时间窗（早于,a,i,或晚于,b,i,），,但要根据所带来的不方便程度支付一定的惩罚。可定义惩罚函数来计算。,若某个客户的时间窗不能被违反（硬的），则有偏离时应支付的惩罚设为无穷大。可见,VRPHTW,实际上是,VRPSTW,的一种特殊情形。,由于允许以支付惩罚偏离时间窗，与,VRPHTW,相比，,VRPSTW,往往会在所需要的车辆数、或各线路总距离和总行驶时间方面获得较大的节省。,19,2.2.4 带回程运输的,VRP,（VRP with backhauls，VRPB）,特点,客户集：去程客户，,L,=1,2,n,回程客户，,B,=,n,+1,n,+,m,先服务去程客户，后服务回程客户。,描述,求一个具有最小总费用的由,K,条简单回路组成的集合，并满足,（1）、（2）,同,CVRP；,（3）,一条回路上各去程客户点和回程客户点的需求量之和分别不超过车辆装载能力,C,；,（4）,所有去程客户必须先于回程客户得到服务,。,20,扩展,带回程运输和时间窗的,VRP（VRP with backhauls and time windows,VRPBTW）,21,2.2.5 带取送货的,VRP （VRP with pickup and delivery，VRPPD）,特点,客户,i,对应着两个量：,d,i,，,送往客户,i,的货物数量,p,i,，,从客户,i,收取的货物数量,O,i,表示需送往客户,i,的货物的始发点，,D,i,表示待取货物的终到点。,在每个客户点，规定先卸后装。,描述,求一个具有最小总费用的由,K,条简单回路组成的集合，并满足,（1）、（2）,同,CVRP；,（3）,车辆的当前负载必须保持非负且,C,；,22,（4）,当,O,i,不是配送中心时，它必须与客户,i,在同一线路上且先于客户,i,得到服务；,（5）,当,D,i,不是配送中心时，它必须与客户,i,在同一线路上且后于客户,i,得到服务。,扩展,带取送货和时间窗的,VRP（VRP with pickup and delivery and time windows,VRPPDTW）。,23,2.3,车辆路径问题的研究现状和发展趋势,Dantzig,和,Ramser,于1959年首先对,VRP,进行了研究。他们描述了一个将汽油送往各加油站的实际问题，并提出了相应的数学规划模型及其求解算法。,1964年，,Clarke,和,Wright,提出一种对,Dantzig,-,Ramser,方法进行改进的较有效的启发式算法,Clarke-Wright,节约算法。,在这两篇开创性的论文发表后，,VRP,很快引起学术界和实际工作者的极大重视，成为近二十多年来运筹学领域的研究热点之一。,特别是物流配送活动中的配送车辆行驶路径问题，是近年来,VRP,的重点研究对象和应用领域。,24,1983年，,Bodin,等人在长达140多页的对,VRP,的研究进展进行综述的文章中，就列举了699篇相关的参考文献。,1995年出版的,Handbooks in Operations Research and Management Science,中，第八卷就是专门讨论车辆路径问题的。,2002年，,Paolo,Toth,和,Daniele Vigo,在其出版的著作,The Vehicle Routing Problem,中，对,VRP,的最新研究进展和发展趋势进行了比较全面的分析。,与国际上相比，国内对,VRP,的研究相对较少，最近几年才陆续有一些相关的研究成果发表。,通过各国研究人员的共同努力，现已提出了许多用于求解不同类型的,VRP,的最优解和近优解的模型及其精确算法和启发式算法。,25,2.3.1 车辆路径问题的模型,CVRP,的三下标车辆流模型。,定义变量,26,模型,27,2.3.2,VRP,的计算复杂性和求解算法,对,VRP,求解算法的研究一直是重点和难点。,现已证明，几乎所有类型的,VRP,均为,NP-,难问题。,VRP,之所以引起学术界的极大重视，除了它具有广泛的应用背景外，是因为相当难解，从而富有挑战性。,目前,已提出了许多求解,VRP,的