物流配送优化(第二章)75957.pptx

上传人:muj****520 文档编号:87226182 上传时间:2023-04-16 格式:PPTX 页数:32 大小:142.20KB
返回 下载 相关 举报
物流配送优化(第二章)75957.pptx_第1页
第1页 / 共32页
物流配送优化(第二章)75957.pptx_第2页
第2页 / 共32页
点击查看更多>>
资源描述

《物流配送优化(第二章)75957.pptx》由会员分享,可在线阅读,更多相关《物流配送优化(第二章)75957.pptx(32页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章 物流配送车辆路径问题n n2.1问题的描述及各组成部分特点n n2.2车辆路径问题的分类 n n2.3车辆路径问题的研究现状和发展趋势 12.1 问题的描述及各组成部分特点1.配送活动中的配送车辆行驶线路优化确定问题,配送活动中的配送车辆行驶线路优化确定问题,是近二十多年来国际运筹学界的研究热点之一。是近二十多年来国际运筹学界的研究热点之一。2.运筹学界将此类问题统称之为车辆路径问题运筹学界将此类问题统称之为车辆路径问题(VehicleRoutingProblem,VehicleRoutingProblem,VRPVRP),),或车辆调度或车辆调度问题问题(VehicleSchedul

2、ingProblem,VSPVehicleSchedulingProblem,VSP)。)。3.一般描述是:对一系列给定的客户点,确定配送一般描述是:对一系列给定的客户点,确定配送车辆行驶路线,使其从配送中心出发,有序地对车辆行驶路线,使其从配送中心出发,有序地对它们进行服务,并在满足一定的约束条件下(如它们进行服务,并在满足一定的约束条件下(如车辆载重量、客户需求量、服务时间限制等),车辆载重量、客户需求量、服务时间限制等),使总运输成本达到最小(如使用车辆数最少、车使总运输成本达到最小(如使用车辆数最少、车辆行驶总距离最短等)。辆行驶总距离最短等)。4.一般把最小化车辆使用数作为第一优化目

3、标,而一般把最小化车辆使用数作为第一优化目标,而最小化车辆行驶距离作为第二优化目标。最小化车辆行驶距离作为第二优化目标。2n n车辆路径问题的特点1.1.道路网道路网(roadnetworkroadnetwork)弧表示路段,点表示道路交叉点、配送中心和弧表示路段,点表示道路交叉点、配送中心和客户。客户。弧的权弧的权c cij ij表示其距离或行驶时间。表示其距离或行驶时间。32.2.客户客户(customercustomer)用图上的小圆点表示;用图上的小圆点表示;需运送或收取的货物量(需求量)需运送或收取的货物量(需求量)d di i(或或d di i和和p pi i);要求提供服务的时间

4、段,即时间窗(要求提供服务的时间段,即时间窗(timetimewindowwindow)在客户点所花费的服务时间在客户点所花费的服务时间s si i;能用于服务该客户的车辆集合。能用于服务该客户的车辆集合。3.3.配送中心(车场)配送中心(车场)(distributioncenterdistributioncenter,depotdepot)用图上的小方点表示;用图上的小方点表示;车辆行驶路线开始并终止于配送中心或某一个客车辆行驶路线开始并终止于配送中心或某一个客户点;户点;其其特征由所配备的车辆种类和数量、以及所能处特征由所配备的车辆种类和数量、以及所能处理的货物总量来描述。理的货物总量来描

5、述。44.4.车辆车辆(vehiclevehicle)车辆是自备还是外租,完成任务后是否返回;车辆是自备还是外租,完成任务后是否返回;车辆的装载能力车辆的装载能力;车辆使用费车辆使用费;可用于进行货物装卸的设备可用于进行货物装卸的设备.5.5.驾驶员驾驶员(driverdriver)给驾驶员安排取送货任务时,必须符合工作时间给驾驶员安排取送货任务时,必须符合工作时间方面的有关规定。方面的有关规定。6.6.路径编排中的限制条件路径编排中的限制条件 车辆的当前负载不能超过车辆的装载量;车辆的当前负载不能超过车辆的装载量;客户只要求送货、取货、或取送货兼有;客户只要求送货、取货、或取送货兼有;在客户

6、所要求的时间窗和驾驶员的工作时间内提在客户所要求的时间窗和驾驶员的工作时间内提供服务;供服务;访问客户的顺序要求。访问客户的顺序要求。57.7.行驶距离和行驶时间行驶距离和行驶时间必须知道客户点与客户点之间,配送中心与客户必须知道客户点与客户点之间,配送中心与客户点之间的行驶距离和行驶时间。点之间的行驶距离和行驶时间。8.8.目标目标(objectivesobjectives)最小化总运输成本,其大小取决于所需要的车辆最小化总运输成本,其大小取决于所需要的车辆数(或线路数)、总行驶距离(时间);数(或线路数)、总行驶距离(时间);最小化与客户的不完全服务等有关的惩罚值;最小化与客户的不完全服务

7、等有关的惩罚值;均衡各线路上的行驶时间和车辆载重量。均衡各线路上的行驶时间和车辆载重量。62.2 车辆路径问题的分类n n根据配送车辆完成配送任务后是否必须返回原出发点以及返回的形式,可将问题分为闭合式和开放式两大类。n n在不需严格区分的场合,统称VRP。7n n当车辆完成运输任务后必须返回原出发点时(即车辆的行驶路线是闭合式的),称之为闭合式车辆路径问题(ClosedVRP),通常简称为车辆路径问题(VRP)。8n n当不要求车辆完成任务后返回原出发点,或者是若要求返回原出发点,则沿原去程路线返回时(即车辆的行驶路线是开放式的),称之为开放式车辆路径问题(OpenVRP,OVRP)。9n

8、n根据所包含的约束条件,问题又可进一步分类。以闭合式VRP为例,可归纳如下:DCVRPDCVRP路程长度路程长度VRPPDVRPPD 装载能力装载能力 取送作业取送作业 CVRPCVRPVRPPDTWVRPPDTW 时间窗时间窗VRPTWVRPTW 回程运输回程运输 VRPBTWVRPBTWVRPBVRPB102.2.1 带装载能力的VRP(CapacitatedVRP,CVRP)n n问题的特点是是VRPVRP中的最基本型式。中的最基本型式。所有客户都属于要送货的或要取货的,其需求量所有客户都属于要送货的或要取货的,其需求量预先知道,且不能被分割。预先知道,且不能被分割。车辆类型相同且都停放

9、在一个配送中心。车辆类型相同且都停放在一个配送中心。对车辆只有装载能力限制。对车辆只有装载能力限制。问题的目标是最小化服务所有客户的总费用(即问题的目标是最小化服务所有客户的总费用(即所需要的车辆数及其车辆行驶距离或行驶时间)。所需要的车辆数及其车辆行驶距离或行驶时间)。n n问题的描述(可描述为如下的图论问题)11设设G G=(=(V V,A A)为一个完备图,其中为一个完备图,其中V V=0,=0,n n 为顶点为顶点集,集,A A是弧集。顶点是弧集。顶点i i=1,=1,n n表示客户,而顶点表示客户,而顶点0 0表表示配送中心。有时配送中心用顶点示配送中心。有时配送中心用顶点n n+1

10、+1来表示。来表示。每条弧对应着一个非负的费用每条弧对应着一个非负的费用c cij ij,表示从点表示从点i i到点到点j j的的行驶费用行驶费用。在一些测试算例中,顶点与给定坐标的平面上的点在一些测试算例中,顶点与给定坐标的平面上的点相对应,且弧的费用相对应,且弧的费用c cij ij被定义为对应于顶点被定义为对应于顶点i i和和j j的两的两点间的欧氏距离。点间的欧氏距离。y yj j j j(x xj j,y,yj j)y yi i i i(x xi i,y,yi i)x xj j x xi i12在配送中心备有相同类型的车辆,每辆的装载在配送中心备有相同类型的车辆,每辆的装载能力为能力

11、为C C。每一条线路上的送货任务只由一辆。每一条线路上的送货任务只由一辆车承担。车承担。每个客户每个客户 i i 有一个已知的需要送往交付的非负有一个已知的需要送往交付的非负需求量需求量d di i,假设假设d di i C C。服务所有客户至少所需服务所有客户至少所需要的车辆数要的车辆数 13CVRPCVRP是是求求一一个个具具有有最最小小总总费费用用的的由由K K条条简简单单回回路路组组成成的的集集合合(每每个个回回路路对对应应于于一一条条配配送送车车辆辆行行驶驶线线路路),并满足,并满足(1)(1)每个回路从配送中心出发并返回配送中心;每个回路从配送中心出发并返回配送中心;(2)(2)每

12、个客户点只在一条回路上;每个客户点只在一条回路上;(3)(3)一一条条回回路路上上各各客客户户点点的的需需求求量量之之和和不不超超过过车车辆装载能力辆装载能力C C。总费用一般包括所使用的车辆数(即回路数)和车总费用一般包括所使用的车辆数(即回路数)和车辆行驶费用两项。通常都认为,多用一辆车所带来辆行驶费用两项。通常都认为,多用一辆车所带来的固定费用的增加,总是超过其因总行驶距离缩短的固定费用的增加,总是超过其因总行驶距离缩短所带来的节省,因此,一般把最小化车辆使用数作所带来的节省,因此,一般把最小化车辆使用数作为第一优化目标,最小化行驶费用作为第二目标。为第一优化目标,最小化行驶费用作为第二

13、目标。14当备有的车辆类型不是同一种时,即有不同的装当备有的车辆类型不是同一种时,即有不同的装载能力载能力C Ck k,k k=1,=1,K K,则就为经常考虑的另一种则就为经常考虑的另一种变形。变形。CVRPCVRP是是NP-NP-难的,并且是旅行商问题难的,并且是旅行商问题(TSPTSP)的的一般化一般化。在在TSPTSP中,要求确定一条经过图中,要求确定一条经过图G G中所有中所有顶点的、费用最小的回路(哈密顿回路),当顶点的、费用最小的回路(哈密顿回路),当CVRPCVRP中的中的C Cd di i和和K K=1=1时就为此情形。时就为此情形。152.2.2 带路程长度的VRP(Dis

14、tance-ConstrainedandCapacitatedVRP,DCVRP)n n特点既有车辆装载能力限制,又有最大路程长度限制。既有车辆装载能力限制,又有最大路程长度限制。n n描述每条弧对应着一个非负的长度每条弧对应着一个非负的长度t tij ij,一般地,费用一般地,费用矩阵与长度矩阵相一致,即矩阵与长度矩阵相一致,即c cij ij=t tij ij。每条线路上各弧的总长度不能超过线路的最大长每条线路上各弧的总长度不能超过线路的最大长度度L L。当弧的长度代表的是行驶时间时,每个客户当弧的长度代表的是行驶时间时,每个客户i i就就对应着一个服务时间对应着一个服务时间s si i,

15、表示车辆必须在该客户表示车辆必须在该客户点停留的时间长度。点停留的时间长度。162.2.3 带时间窗的VRP(VRPwithtimewindows,VRPTW)除了车辆装载能力约束外,每个客户除了车辆装载能力约束外,每个客户i i 都有一个与都有一个与之相联系的要求提供服务的时间区间之相联系的要求提供服务的时间区间 a ai i,b bi i。1.带硬时间窗的VRP(VRPwithhardtimewindows,VRPHTW)。在不需要严格区分的场合,一般就称为带时间窗的VRP。n n特点客户的服务必须在相应的时间窗内开始,车辆在客户的服务必须在相应的时间窗内开始,车辆在客户点的服务时间长度为

16、客户点的服务时间长度为s si i。当车辆提前到达客户点时,必须等待到时刻当车辆提前到达客户点时,必须等待到时刻a ai i才可才可开始服务。不允许在开始服务。不允许在b bi i之后到达并开始服务。之后到达并开始服务。17对于配送中心,设服务时间对于配送中心,设服务时间s s0 0=0=0,时间窗时间窗 a a0 0,b b0 0。应注意的是,时间窗的要求导致每条线路应注意的是,时间窗的要求导致每条线路具有隐具有隐含的方向性,含的方向性,以及以及线路长度的限制线路长度的限制,最大线路长,最大线路长度为度为L L=b b0 0。描述VRPHTWVRPHTW是求一个具有最小总费用的由是求一个具有

17、最小总费用的由K K条简单条简单回路组成的集合,并满足回路组成的集合,并满足(1 1)、()、(2 2)、()、(3 3)同同CVRPCVRP;(4 4)对每个客户对每个客户i i,服务在时间窗服务在时间窗 a ai i,b bi i 内开始,内开始,车辆的停留时间长度为车辆的停留时间长度为s si i。当当a ai i=0,=0,b bi i=+=+时时,VRPHTWVRPHTW就为就为CVRPCVRP。182.带软时间窗的VRP(VRPwithsofttimewindows,VRPSTW)时间窗要求是软的,即允许服务的开始时间有所时间窗要求是软的,即允许服务的开始时间有所偏离时间窗(早于偏

18、离时间窗(早于a ai i或晚于或晚于b bi i),),但要根据所带来但要根据所带来的不方便程度支付一定的惩罚。可定义惩罚函数的不方便程度支付一定的惩罚。可定义惩罚函数来计算。来计算。若某个客户的时间窗不能被违反(硬的),则有若某个客户的时间窗不能被违反(硬的),则有偏离时应支付的惩罚设为无穷大。可见偏离时应支付的惩罚设为无穷大。可见VRPHTWVRPHTW实际上是实际上是VRPSTWVRPSTW的一种特殊情形。的一种特殊情形。由于允许以支付惩罚偏离时间窗,与由于允许以支付惩罚偏离时间窗,与VRPHTWVRPHTW相相比,比,VRPSTWVRPSTW往往会在所需要的车辆数、或各线往往会在所需

19、要的车辆数、或各线路总距离和总行驶时间方面获得较大的节省。路总距离和总行驶时间方面获得较大的节省。192.2.4 带回程运输的VRP(VRPwithbackhauls,VRPB)n n特点客户集:去程客户,客户集:去程客户,L L=1,2,=1,2,n n 回程客户,回程客户,B B=n n+1,+1,n n+m m 先服务去程客户,后服务回程客户。先服务去程客户,后服务回程客户。描述求一个具有最小总费用的由求一个具有最小总费用的由K K条简单回路组成的集条简单回路组成的集合,并满足合,并满足(1 1)、()、(2 2)同同CVRPCVRP;(3 3)一条回路上各去程客户点和回程客户点的需求一

20、条回路上各去程客户点和回程客户点的需求量之和分别不超过车辆装载能力量之和分别不超过车辆装载能力C C;(4 4)所有去程客户必须先于回程客户得到服务所有去程客户必须先于回程客户得到服务。20n n扩展带回程运输和时间窗的带回程运输和时间窗的VRPVRP(VRPwithVRPwithbackhaulsandtimewindows,VRPBTWbackhaulsandtimewindows,VRPBTW)212.2.5 带取送货的VRP(VRPwithpickupanddelivery,VRPPD)n n特点客户客户i i对应着两个量:对应着两个量:d di i,送往客户送往客户i i的货物数量的

21、货物数量 p pi i,从客户从客户i i收取的货物数量收取的货物数量O Oi i表示需送往客户表示需送往客户i i的货物的始发点,的货物的始发点,D Di i表示待取货物的终到点。表示待取货物的终到点。在每个客户点,规定先卸后装。在每个客户点,规定先卸后装。描述求一个具有最小总费用的由求一个具有最小总费用的由K K条简单回路组成的条简单回路组成的集合,并满足集合,并满足(1 1)、()、(2 2)同同CVRPCVRP;(3 3)车辆的当前负载必须保持非负且车辆的当前负载必须保持非负且 C C;22(4 4)当当O Oi i不是配送中心时,它必须与客户不是配送中心时,它必须与客户i i在同一在

22、同一线路上且先于客户线路上且先于客户i i得到服务;得到服务;(5 5)当当D Di i不是配送中心时,它必须与客户不是配送中心时,它必须与客户i i在同一在同一线路上且后于客户线路上且后于客户i i得到服务。得到服务。n n扩展带取送货和时间窗的带取送货和时间窗的VRPVRP(VRPwithpickupandVRPwithpickupanddeliveryandtimewindows,VRPPDTWdeliveryandtimewindows,VRPPDTW)。)。232.3车辆路径问题的研究现状和发展趋势DantzigDantzig和和RamserRamser于于19591959年首先对年

23、首先对VRPVRP进行了研究。进行了研究。他们描述了一个将汽油送往各加油站的实际问题,他们描述了一个将汽油送往各加油站的实际问题,并提出了相应的数学规划模型及其求解算法。并提出了相应的数学规划模型及其求解算法。19641964年,年,ClarkeClarke和和WrightWright提出一种对提出一种对Dantzig-Dantzig-RamserRamser方法进行改进的较有效的启发式算法方法进行改进的较有效的启发式算法Clarke-WrightClarke-Wright节约算法。节约算法。在这两篇开创性的论文发表后,在这两篇开创性的论文发表后,VRPVRP很快引起学很快引起学术界和实际工作

24、者的极大重视,成为近二十多年术界和实际工作者的极大重视,成为近二十多年来运筹学领域的研究热点之一。来运筹学领域的研究热点之一。特别是物流配送特别是物流配送活动中的配送车辆行驶路径问题,是近年来活动中的配送车辆行驶路径问题,是近年来VRPVRP的重点研究对象和应用领域。的重点研究对象和应用领域。2419831983年,年,BodinBodin等人在长达等人在长达140140多页的对多页的对VRPVRP的研究的研究进展进行综述的文章中,就列举了进展进行综述的文章中,就列举了699699篇相关的参篇相关的参考文献。考文献。19951995年出版的年出版的HandbooksinOperationsRe

25、searchHandbooksinOperationsResearchandManagementScienceandManagementScience 中,第八卷就是专门讨中,第八卷就是专门讨论车辆路径问题的。论车辆路径问题的。20022002年,年,PaoloTothPaoloToth和和DanieleVigoDanieleVigo在其出版的著作在其出版的著作TheVehicleRoutingProblemTheVehicleRoutingProblem中,对中,对VRPVRP的最新的最新研究进展和发展趋势进行了比较全面的分析。研究进展和发展趋势进行了比较全面的分析。与国际上相比,国内对与国

26、际上相比,国内对VRPVRP的研究相对较少,最近的研究相对较少,最近几年才陆续有一些相关的研究成果发表。几年才陆续有一些相关的研究成果发表。通过各国研究人员的共同努力,现已提出了许多用通过各国研究人员的共同努力,现已提出了许多用于求解不同类型的于求解不同类型的VRPVRP的最优解和近优解的模型及的最优解和近优解的模型及其精确算法和启发式算法。其精确算法和启发式算法。252.3.1 车辆路径问题的模型n nCVRP的三下标车辆流模型。定义变量定义变量26模型模型272.3.2VRP的计算复杂性和求解算法对对VRPVRP求解算法的研究一直是重点和难点。求解算法的研究一直是重点和难点。现已证明,几乎

27、所有类型的现已证明,几乎所有类型的VRPVRP均为均为NP-NP-难问题。难问题。VRPVRP之所以引起学术界的极大重视,除了它具有之所以引起学术界的极大重视,除了它具有广泛的应用背景外,是因为相当难解,从而富有广泛的应用背景外,是因为相当难解,从而富有挑战性。挑战性。目前目前已提出了许多求解已提出了许多求解VRPVRP的算法,的算法,究其实质,究其实质,可可分为分为精确算法精确算法和和启发式算法启发式算法两大类。两大类。28n n精确算法 指可求出其最优解的算法,且一般要求问题能用指可求出其最优解的算法,且一般要求问题能用相应的数学模型表示。相应的数学模型表示。目前用于求解目前用于求解VRP

28、VRP的精确算法主要有的精确算法主要有 分支定界法分支定界法(Branch-and-BoundAlgorithmBranch-and-BoundAlgorithm)分支切面法分支切面法(Branch-and-CutAlgorithmBranch-and-CutAlgorithm)割平面法割平面法(CuttingPlaneMethodCuttingPlaneMethod)因因VRPVRP是是NPNP-难问题,其精确算法的计算量随问难问题,其精确算法的计算量随问题规模的增大呈指数增长,在实际中的应用范围题规模的增大呈指数增长,在实际中的应用范围有限。但在对相应的启发式算法的质量评估等理有限。但在对

29、相应的启发式算法的质量评估等理论研究工作中却很有意义。论研究工作中却很有意义。从实际应用的角度来说,公认的明智做法是设计从实际应用的角度来说,公认的明智做法是设计相应的启发式算法来求出问题的近优解。相应的启发式算法来求出问题的近优解。29n n启发式算法是基于直观或经验构造的算法,一般不要求非得将是基于直观或经验构造的算法,一般不要求非得将问题表述为某种标准的数学模型;在可接受的计算问题表述为某种标准的数学模型;在可接受的计算量内求出问题的满意解,但不能保证最优。量内求出问题的满意解,但不能保证最优。1960-19901960-1990年间,所提出的求解年间,所提出的求解VRPVRP的启发式算

30、法的启发式算法都是基于都是基于经典的启发式方法经典的启发式方法的思想。的思想。19901990年以来,随着年以来,随着通用启发式算法通用启发式算法(meta-meta-heuristicsheuristics)的)的出现,如模拟退火出现,如模拟退火(SA)(SA)、禁忌搜索、禁忌搜索(TS)(TS)、遗传算法、遗传算法(GA)(GA)等,研究运用这些算法来构造等,研究运用这些算法来构造求解求解VRPVRP的算法已成为主流和当前的研究热点,并的算法已成为主流和当前的研究热点,并已取得了许多令人鼓舞的成果。已取得了许多令人鼓舞的成果。求出的解高出最优解(或已知最好解):求出的解高出最优解(或已知最

31、好解):基于基于经典启发式方法:经典启发式方法:2-10%2-10%;基于基于通用启发式方法:通用启发式方法:0.5%0.5%30n n发展趋势为了使现代启发式算法能在商业软件中得到应用,为了使现代启发式算法能在商业软件中得到应用,开发更快、更简单、更健壮的算法已成为一种趋开发更快、更简单、更健壮的算法已成为一种趋势,尽管这将在解的质量方面带来一些小损失。势,尽管这将在解的质量方面带来一些小损失。在算法测试与比较方面,研究人员目前已取得一在算法测试与比较方面,研究人员目前已取得一个共识:必须使用公开的标准测试算例个共识:必须使用公开的标准测试算例(benchmarkinstancesbenchmarkinstances)对所提出的算法进行测试。对所提出的算法进行测试。这样,其测试结果才具有可比性和说服力。这样,其测试结果才具有可比性和说服力。31

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 考试试题 > 一级建造

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁