车辆路径问题的概述自己翻译的.ppt

《车辆路径问题的概述自己翻译的.ppt》由会员分享，可在线阅读，更多相关《车辆路径问题的概述自己翻译的.ppt（34页珍藏版）》请在三一办公上搜索。

1、车辆路径问题的概述,保罗托斯丹尼尔维戈,引 言:,过去几十年里基于行动研究和数学编程技术,优化软件包已经越来越多的被利用来有效管理供货服务分销系统。有很多现实生活中的实例,无论是在北美和欧洲,有广泛的调查数据显示在使用电脑程序分配过程中会产生大量的规划储蓄，通常占整个全球运输成本的5%到20%。很容易看到这些储蓄对全球经济系统的影响是十分重要的。事实上,运输过程中涉及到的所有阶段的生产和分销系统，代表一个相关组件货物的最终成本的10%到20%。由于计算机技术的发展，再加之日益一体化的信息系统生产和商业流程，我们可以从硬件和软件上具备使用运筹学技术的条件。,在本书中,我们只考虑分销仓库和最终用户

2、(客户)之间存在的问题,。这些问题通常称为车辆路径问题(VRPs)或车辆调度问题。这提出了解决车辆调度问题的模型和算法，在书中详细介绍了可以有效地使用不仅对解决方案的交付等方面的问题或集合货物,但解决实际应用中出现的不同交通运输系统。,另外一个同样重要的成功原因是近些年建模技术和算法实现工具的发展，事实上,该模型考虑到帐户所有出现在实际应用程序中的特征分布和在实际的计算时代中计算计算法所能找到的最好的解决方案。,这种类型的典型应用,例如,固体垃圾收集、清扫街道,校车路由、拨号叫车服务系统、运输残疾人、路由的销售人员和维修单位。,货物的分配服务 是在给定的时间范围内,一组客户通过一组工具,位于一

3、个或多个仓库,由一个组人员(司机)通过使用一个适当的公路网络来执行行动。特别要指出一个VRP的解决方案要求确定一组路线,每个行动通过一个单一的车辆,开始和结束都在自己的仓库,这样所有的顾客需求都是可以实现,所有的操作约束是符合要求的,并且可以使得全球运输成本最小化。在本节中,我们描述的典型特性路由和调度问题,考虑他们的主要组件(道路网络,客户、仓库、车辆和司机),和不同的操作约束,可以对行走在建筑群里的路线,和可能的目标来实现优化过程。,描述方式：通常是通过图形来描述,其中，弧线代表道路的部分，其顶点对应于道路结和仓库以及客户的位置。弧线(相应的图表)可以是定向的或是无向的,这取决于他们是否可

4、以分别在一个方向(例如,因为存在的单行道,典型的城市或高速公路网络)或在两个方向上遍历。每个电弧是相关联的一个成本,由它的长度，历时时间代表,这可能由车辆类型或是在这期间哪条电弧是可以遍历的决定他们。,道路网络（用于运输货物）,Typical characteristics of customers are：vertex of the road graph in which the customer is located;amount of goods(demand),possibly of different types,which must be delivered orcollected

5、 at the customer;periods of the day(time windows)during which the customer can be served(forinstance,because of specific periods during which the customer is open or the locationcan be reached,due to traffic limitations);times required to deliver or collect the goods at the customer location(unloadi

6、ng orloading times,respectively),possibly dependent on the vehicle type;and subset of the available vehicles that can be used to serve the customer(for instance,because of possible access limitations or loading and unloading requirements).,有时,它可能不会完全满足每个客户的需求。在这些情况下,交付或收集的数量会减少,或一个子集的客户可以被留下无人看管。处理这

7、些情况,根据不同的奖惩优先级，可以指派给客户不同的解决方案。,执行路线：,是指为客户提供服务的始发点和结束点在一个或多个仓库，并且这些仓库是位于在顶点的道路图。每个仓库的特点是车辆的数量和类型是相关联的,并且可以处理全球的货物。,在一些实际应用程序,在仓库客户是一个先验的分区,车辆必须在每个路线的最后回到他们自己的仓库里。在这些情况下，在这些情况下,整个VRP可以分解成几个独立的问题,每一个关联到一个不同的仓库。货物运输是由使用的车辆组成，大小可以是固定的或可以被界定根据客户的要求,Typical characteristics of the vehicles are:,home depot

8、of the vehicle,and the possibility to end service at a depot other than thehome one;capacity of the vehicle,expressed as the maximum weight,or volume,or number ofpallets,the vehicle can load;possible subdivision of the vehicle into compartments,each characterized by its capacityand by the types of g

9、oods that can be carried;devices available for the loading and unloading operations;subset of arcs of the road graph which can be traversed by the vehicle;and costs associated with utilization of the vehicle(per distance unit,per time unit,perroute,etc.).,司机操作车辆必须满足联盟合同和公司规定等几个约束(例如,在白天的工作时间、数量和持续工间

10、休息服务,最大持续开车时间,加班时间)。在下文中,限制强加给司机嵌入这些联系在一起的车辆。这个路线必须满足几个操作约束,这依赖于自然货物的运输,高质量的服务水平,和具有其自身特点的客户和车辆。一些典型的操作约束是以下几点:along each route,the current load of the associated vehicle cannot exceed the vehicle capacity;thecustomers served in a route can require only the delivery or the collection of goods,or bot

11、hpossibilities can exist;and customers can be served only within their time windows andthe working periods of the drivers associated with the vehicles visiting them.,优先约束:,优先约束可以对客户的顺序做一个路线参观。一种类型的优先约束要求一个给定的客户服务，在相同的一个给定路线服务其他客户子集中,客户必须去过(或以后要去)客户属于的相关子集。例如,所谓的皮卡和交货问题,其中该航线都可以执行收集和交付的货物和货物从传感器收集客户必

12、须被带到相应的交付客户同样的车辆。另一个类型的优先约束,如果不同类型的客户服务同样的路线,以何种顺序访问客户是固定的。这种情况出现,例如,对于所谓的VRP与Backhauls，再次在其中,路线可以执行两个集合和交付的货物,但限制相关的加载和卸载操作,难以重新加载的车辆沿路线运输,者意味着所有货物必须先进行集合。评估的全球路线成本,和检查约束的操作强加于他们,需要知识的旅行成本和旅行时间每对客户和客户之间的仓库的旅行时间和。,为此,原来的道路图(通常是非常稀少的)通常转换为完全图,完全图的顶点是道路图顶点所对应于客户和仓库。对于每一对顶点i和j的完全图,一个弧(i,j)定义成本Cij。旅行时间的

13、年度财政,与完全图相关各弧(i,j),计算旅行时间的总和的弧属于最短路径的i到j在路上图。在下面,而不是原始的道路图,我们考虑相关的完全图,可以直接或无向,这取决于相应属性的成本和旅行时间矩阵是不是分别对称,这些经常形成对比,目标可以被考虑车辆路径问题。,典型目标是：,minimization of the global transportation cost,dependent on the global distancetraveled(or on the global travel time)and on the fixed costs associated with the usedv

14、ehicles(and with the corresponding drivers);minimization of the number of vehicles(or drivers)required to serve all the customers;balancing of the routes,for travel time and vehicle load;minimization of the penalties associated with partial service of the customers;or any weighted combination of the

15、se objectives.,在某些应用程序中,每个车辆可以运行不止一个路线,或者途径路线时间可以持续超过1天。此外,必要的时候需要考虑随机问题,也就是说,对于这个问题只需要部分有关客户或成本(和旅行时间)相关的弧道路网络知识的要求。,超过40年以来已经过去,Ramser Dantzig VRP11在他们的论文中描述了一个真实的应用程序(关于交付汽油加油站),并提出和制定了的第一个数学规划和算法解决问题。几年后,克拉克和赖特9提出了一个有效启发式,改进了这个Dantzig-Ramser方法。以下两个具有开创性的论文,许多模型，精确算法和启发式算法建立了优化和近似解的VRP的不同版本。本章描述了

16、几种不同的，也是最重要和最有效的模型和算法是在。Desrochers,Lenstra,Savelsbergh13给出了一个分类方案。Laporte和Nobert32提出了一个广泛的调查,完全致力于用确切方法解决VRP,并在1980年代末给他们一个完整而详细，具有艺术气息的分析状态。,其他调查,覆盖精确算法,但通常主要致力于启发式方法,提出了通过Christofides,Mingozzi,托斯马尼安蒂7,36,博丹et al。4,Christofides5,Laporte30,费舍尔19,托斯和比戈第四十一条、第四十二条,和黄金et al。26。提出了一个带注释的书目Laporte31,和广泛的

17、参考书目提出了Laporte和奥斯曼33。一本关于这个题目的书是编辑金和阿萨德25。模型和算法解决所谓的电弧路由问题,即问题产生的变体当客户所在不是在顶点但沿弧线的道路网络,在最近的书描述编辑Dror14。这一特定的情况时产生的VRP只有一个车辆可以在仓库和没有额外的操作应用的约束,即众所周知的旅行推销员问题,是广泛的经典书籍中描述编辑Lawler et al。34。,问题定义和基本的符号:,在这一节中,我们给一个正式的定义,如图理论模型,基本的问题车辆的路由类。这些问题,它已收到最大的关注科学文献,详细讨论了这本书的前两部分。我们首先描述VRP生产,这是最简单、最具有研究意义的家庭成员,然后

18、我们介绍了距离约束VRP,VRP带时间窗的,VRP与Backhauls,VRP与选送。对于这些问题,提出了几个较小的变异和检查在文学和经常不同的问题给出了相同的名称。虽然在许多例解决方案的方法,特别是启发式的公司,可能会适应合并额外的特性,这种不确定性的问题定义通常会导致更多的混乱。因此,对于每个问题我们首先描述基本的版本,例如,一个在这本书是用相应的缩略词,然后我们将讨论不同的变体。在另外,我们让一个明确的区分对称和非对称的版本问题只是如果模型和解决方案的方法在文献提出的利用这种区别。,也在这一节中,我们将介绍所有相关的符号和术语在这本书。额外的标记和定义需要描述特定的变异和实用的VRP问题

19、给出相应的章节。图1.1总结了这一节中描述的主要问题,说明了它们的连接。在本图中,一个箭头将从A到B的问题问题意味着B是一个扩展。,生产和距离约束VRP,在CVRP,所有的客户对应于的交付问题和他的要求是确定性的,是要提前知道,不得分裂。车辆被强加的条件是要数量相等且在一个中央仓库,只有容量受限制。目标是为所有的客户实现最小化总成本(即,一个加权函数路线的数量及其长度或旅行时间)。,图 基本的问题和它们之间的联系VRP,CVRP的可以被描述为下面的图理论问题。让G=(V,A)是一个完整的图形,设置V=0,n是顶点组和一个是电弧。顶点i=1n,对应于客户,而顶点0对应,仓库有时候是与顶点n+1对

20、应,一个非负成本,Cij,伴随着每个弧(i,j)A和代表了旅行成本花去从顶点i到顶点j。通常i,不允许使用循环弧,(i,i),而是通过定义为如果G是一个有向图,成本矩阵c是不对称的,和相应的问题是CVRP称为非对称的(ACVRP)。否则,我们这个问题就是所谓的对称CVRP(SCVRP)电弧通常被设置为一组无向边,E。给定一个边缘eE,让 表示其端点的顶点。在下面我们表示边缘设置的无向图G的边缘时表示通过他们的端点(i,j),i,j V,当边表示通过单个索引E。,图形G必须是完整的，给定一个前向顶点i，让+(i)表示i，定义为组顶点j,弧（i，j）A，也就是说，顶点直接从i访问。类似的，让-表示

21、逆向顶点i,定义为组顶点（i,j）A,顶点直接从i访问。给定一个顶点组S V，让(S)和E(S)表示边缘e E，有一个或两个相同的端点S。在一些实际情况下,成本矩阵满足三角不等式,即:Cik+Ckj Cij(i,j,k V)给定坐标:V(i,j),每个(i,j)A,定义为欧氏距离,这两个点之间的顶点对应i和j。在这种情况下的成本矩阵对称且满足三角不等式，并由此产生的问题叫做欧几里德的scvrp。每个顾客i（i=1，n），关联到一个已知的非负需求Di，仓库的虚拟需求D0=0，给定一个顶点组S V，令D(S)=i sDi来表示总需求的设置。相同的车辆K,相同的容量C，假设Di C（i=1，n），令

22、K Kmin，Kmin的值可能通过求解与CVRP相关的装箱问题(BPP)来决定。set S V 0,表示r(S)需要的最小数量的车辆.r(V 0)=Kmin,r(S)为BPP 的下界。即：D(S)/C,然而就这些相应的原始成本而言，激烈的失真度量诱导此操作会产生很坏的上下界。请注意，当成本每个弧的图是平等的对成本的最短路径的终点，相应成本矩阵满足三角不等式。在某些情况下顶点的相关点给定了坐标和成本/年，为每个弧（i，j）属于A，定义为欧氏距离两点之间的对应顶点I和J.在这种情况下的成本矩阵对称且满足三角不等式，并由此产生的问题叫做欧几里得SCVRP。观察到经常进行舍入到最近的整数的实际价值，欧

23、几里得弧成本可能导致违反三角不等式，如果成本围捕，这就不会发生。,每个客户i（i=1.n），是与一个已知的非负需求，di是被交付和仓库虚拟需求d0=0。给定一个顶点集S包含于V，让 表示总需求的一套。一套的车辆K，每个容量C，可在仓库。保证我们认为可行性，di C为每个i=1,n。每辆车可能在最一条路线，我们假设是不小于公里的地方，是最低公里所需车辆的数量为所有客户。对知识价值的可能确定通过求解装箱问题（应用）与CVRP，要求日确定最低数量的垃圾箱，每个容量，需加载所有这个项目，每一个非负权重的di,i=1,n。虽然是NP-hard的应用强烈的情况下，数以百计的项目可以很有效地优化求解。,给定

24、一组，我们指的是r（S）的最低所需的车辆数目服务所有的客户在S,i.e.，即最优解的价值与项目相关的培训集合。注意r（V 0）=K(min)。通常r（5）取而代之的是平凡和下界。d(S)/C 该CVRP构成找到收集亩（每个相应的简单电路车辆路线）与最低成本，界定为总和的费用的弧所属的电路等。,（一）每个电路访问的顶点；（二）客户每一个顶点是访问了整整一个电路；（三）总和的要求的顶点访问的电路不超过车辆能力。在文献上被认为几种版本的CVRP。首先当数可用的车辆是一个Kmjn，它可能会留下一些车辆使用，从而在最电路必须确定。在这种情况下，固定成本是经常使用的车辆，以及额外的目的需要数量减少电路（即

25、使用的车辆）被添加到这需要最小总成本。另一个经常被认为是变种出现时现有的车辆是不同的，即有不同的能力Ck，k=1，K。最后路线，只含有一个客户可能不被允许。在下一节，我们讨论如何模型的基本CRVP能够适应这些额外的功能考虑。,该CRVP是已知的NP-hard(在强意义）和推广了著名的旅行商问题（TSP），要求确定一个最小电路简单访问所有顶点G（哈密顿回路）和时所产生的C的（v）和K=1。因此所有的松弛，提出了问题的有效期为CRVP。第一个版本CRVP我们考虑的是所谓的距离限制的车辆路径问题（DVRP），在每个路径的容量约束，取而代之的是一个最大长度（或时间）约束。特别是一个非负的长度，侧向ti

26、j（或te）是与每个arc（i，j）A一个（或边界eE），和总长度的圆弧各路线不能超过最大路径长度T。如果车辆的不同，然后最大路径长度Tk,k=1，K。此外当弧的长度代表的旅行时间，服务时间，Si，可能与每个客户的我，表示时间段的车辆必须停止在它的位置。另外该服务可以被添加到旅行时间弧，即通过定义，为每个arc（i，j），tij=ij+Si/2+Sj/2在那里原来是旅行时的arc（i，j）。一般来说，成本和长度矩阵一致，即i.e.cij=tij对所有（i，j）A（或ce=te对所有的eE）。因此，客观的问题是尽量减少总长度本路线或他们的时间，当服务时间包括在旅行时间的弧。在这种情况下的容量和最

27、大距离的限制目前被称为距离限制的CRVP（DCRVP）。准确和启发式算法CRVP和DCRVP的章节描述,VRP与时间窗:,有时间窗的车辆路径问题（VRPTW）是延伸的CRVP的能力施加的限制和每个客户我是与一个时间区间ai,bi，称为时间窗口。时间即时在该车辆离开仓库，旅行时间，风云，为每个arc（i，j）A（或te对每个eE）和一个额外的服务时间为每一个客户si。服务每个客户必须在相关的时间窗口，和车辆必须停在客户定位为第一时间的瞬间。此外在案件早期到达的位置i，车辆一般是可以等到时间瞬间ai，i.e.,直到服务可以开始。通常成本和走时矩阵一致，和时间窗口定义假设所有车辆离开仓库时即时0。此

28、外，观察时间窗要求诱导隐方向各路线的就算了原来的矩阵都是对称的。因此VRPTW通常是模仿作为一种非对称问题。VRPTW是为了找到一个集合k由恰电路简单最低成本，比如：（一）每个电路访问的顶点；（二）客户每一个顶点是访问了整整一个电路；（三）顶点的电路访问的需求的总和不超过车辆容量,C;（四）为每一个客户i,在服务开始的时间窗口ai,bi内，并且车辆停止时刻si。,VRP中的回程载运:,带回送的VRP（VRPB）是扩展CVRP时，客户的V 0被划分为两个子集。第一子集，L，包含n Linehaul customers，每一种都需要给定数量的产品以交付。第二子集，B，包含m的回程的客户，即一定量的

29、入境产品必须获得。客户被编号，使得L=1,.,n 和 fi=n+!,.,+m.在VRPB中，优先约束回程linehaul和客户之间存在：每当路由为两种类型的客户提供服务，所有的linehaul的客户必须在回程客户可能被服务之前被服务。一个被交付或视其类型而收集的非负需求dt，与每一个客户联系在一起，车厂与一个虚构需求JQ 0 联系在一起。当成本矩阵是不对称的，相关的问题被称为非对称带回送的VRP（AVRPB）。VRPB（和AVRPB也一样）找到恰好K的以最小的成本集合的简单回路，以及，如（一）各电路访问的车厂顶点;（二）每个客户的顶点是被访问的一个回路;（三）参观了一个电路的linehaul客

30、户和回程客户的总需求没有被满足，尤其是车辆的通行能力C;（四）如果有的话，在每个电路所有的linehaul的客户回程客户之前。电路只包含回程的客户一般都是不允许的。此外，观察其优先约束引入了一个隐含的方向的“混合”车辆路线，,如，访问干线运输和回程顶点。让KL和KB表示服务所有干线和回程的最小车辆数量。这些值可以用BPP与相应的客户的子集相关联的实例解决。为了确保可行性，我们假定K是不小于需要为所有客户服务的车辆的最小数目，即K maxA,KB。VRPB和AVRPB是NP-hard的强烈的责任感，因为他们概括基本的SCVRP和AC VRP的版本，当B=0时所产生。此外，所谓的，TSP带回送（T

31、SPB）是VRPB在 C maxd(L),d(Band K=1时的特殊情况。VRPB在现代时间窗的案例已经在文学中作为研究，文学被称为VRP带回送和时间窗（VRPBTW）。在第8章中用精确和启发式算法描述了VRPB及AVRPB。,VRP 带 取 送:,在VRP接送零担货物业务基本版中，每个客户i与两个数量d,and pt 相关，相当于在客户i中传送和交货同类商品的需求交付。有时，只有一个要求量J,=dt/?/被用于每个客户/，表示所述净送货和拾取器的需求之间的差异。对于每一个顾客i,Oi表示的顶点的起源是交付的需求，和DI表示拾取器需求的目的地的顶点。假设，在每个客户位置，交货之前进行传递被执

32、行，因此，在到达一个给定的位置之前的车辆的当前负荷的定义由最初的负荷减去所有已交付的需求，再加上所有已经交货的需求。VRPPD由发现完全以精确最小运费的K组成的简单回路的集合,比如：（一）各电路访问的车厂顶点;（二）每个客户的顶点被一个精确回路访问;（三）在该车辆沿回路的回路负载必须是非负的和可能永远不会超过车辆容量C;（四）为不同仓库的每个客户/,客户Of必须在同一回路客户/之前被服务;（五）为每一个客户i，客户Z）/，在不同的仓库，必须在同一回路客户i之后被服务。通常要求的原产地或目的地是常见的（例如，它们是与仓库，如在CVRP和VRPB）相关联，因此没有必要明确表明它们。这个问题被称为联立交货和传送的VRP（VRPSPD）。VRPPD和VRPSPD是NP-hard的强烈的责任感，因为他们概括当 Of=Dt=0 和 pi=0 对于每个i e V.时的CVRP，此外，所谓的接送零担货物业务（TSPPD）是VRPSPD 在其中K=1的特殊情况下，VRPPD是目前已研究了在文献中被称为的VRP接送零担货物业务和时间窗。精确和启发式在第9章中所描述，VRPPD的算法的一个扩展版本。,谢 谢 观 看,