四运输路线选择和优化.pptx
《四运输路线选择和优化.pptx》由会员分享,可在线阅读,更多相关《四运输路线选择和优化.pptx(74页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、问题一 如何制定合理的行车路线?要制定合理的运输路线,就是要找到运输工具在公路网最佳路线。什么是最佳路线?在满足客户的运输服务同时,尽可能地缩短运输时间和运输距离,减少运输工具和作业人员,从而使运输成本降低。怎么去寻找最佳路线?第1页/共74页怎么去寻找最佳路线?车辆路线安排问题(VRP,Vehicle Routing Problem)是指对物流配送的车辆进行优化调度。该问题一般可以描述如下:对一系列装货点或(和)卸货点,组织适当合理的行车路线,使车辆有序地通过他们,在满足一定的约束条件下(如货物需求量、发送量、交发货时间、车辆容量、数目限制、车辆行驶里程、时间限制等)下,达到一定的目标(如最
2、短路程、最小费用、最短时间、最少车辆等)。该问题涉及了多辆交通工具的服务对象的选择和路径(服务顺序)确定两方面的问题。第2页/共74页怎么去寻找最佳路线?一般需要考虑以下几个方面的问题:(1 1)仓库:仓库的级数,每级仓库的数量、地点和规模。(2 2)车辆:车辆的型号和数量,每种车辆的容积和运作费用,出发时间和返回时间,司机休息时间,最大的里程和时间限制。(3 3)时间窗口:由于各处的工作时间不同,每个站点每天只允许在特定的时间内取货和/或送货。(4 4)顾客:顾客需求,装载、卸载,所处的地理位置,分离需求,优先等级。(5 5)道路信息:车流密度,道路交通费用,距离或时间属性。(6 6)货物信
3、息:货物的种类多少,兼容性,货物的保鲜。(7 7)运输规章:工人每天的工作时间,车辆的周期维护。第3页/共74页运输路线选择问题归纳为三种类型运输路线选择问题归纳为三种类型一个起点,一个终点,起点终点不重合称为最短路问题。最短路径法一个起点,一个终点,起点终点重合多个起点,多个终点起点和终点重合的路径问题一般被称为“流动推销员”问题。图上作业法n n经验法第4页/共74页最短路径法一个起点,一个终点,起点终点不重合Dijkstra在1959年提出了按路径长度的递增次序,逐步产生最短路径的Dijkstra算法。该算法可以用于求解任意指定两点之间的最短路径,也可以用于求解指定点到其余所有节点之间的
4、最短路径。第5页/共74页例:某运输公司签订了一项运输合同,要把某运输公司签订了一项运输合同,要把A A市的一批货市的一批货物运送到物运送到J J市,该公司根据这两个城市之间可选择的行市,该公司根据这两个城市之间可选择的行车路线的地图绘制了如图所示的公路网络。图中,圆圈车路线的地图绘制了如图所示的公路网络。图中,圆圈也称节点,代表起点、目的地和与行车路线相交的其他也称节点,代表起点、目的地和与行车路线相交的其他城市。链代表两个结点之间的公路,每一条公路都标明城市。链代表两个结点之间的公路,每一条公路都标明运输里程。运输里程。可以看出,从A市出发到达B市,可以有很多条路线可以选择。但是如何选择运
5、输路线,才能使总路程的长度最短?这就是运输规划中的最短路问题。第6页/共74页第7页/共74页最短路径法1 1、找出第N N个距起点最近的节点,对N=1N=1,2 2,3 3,4 4,重复此过程,直到找出最近的节点为终点。2、在前面的迭代过程中找出(n-1n-1)个距起点最近的节点,这些节点和起点统称为已解的节点,其余的称为未解节点。(开始时只有起点是已解的节点)3、每个已解的节点直接和一个或多个未解的节点相连接,其中连接距离最短的点就是候选点。4、将每个已解节点与其候选点之间的距离累加到该已解节点与起点之间最短路径的距离上,所得出的总距离最短的候选点就是第n个最近的节点,其最短路径就是得出该
6、距离的路径。第8页/共74页最短路径法的计算步骤表第9页/共74页因此,从上表所示过程可知,从A到J的最短路线距离为384。最短路线为A-B-E-I-J第10页/共74页练习 某运输公司要把A市的一批货物运送到B市,该公司根据这两个城市之间可选择的行车路线的地图绘制了如图所示的公路网络。图中,圆圈也称节点,代表起点、目的地和与行车路线相交的其他城市。链代表两个结点之间的公路,每一条公路都标明运输里程。请找出A市到B市最短路径。A市B市第11页/共74页一个起点,一个终点,起点终点重合 物流管理人员经常会遇到起点和终点相同的路径规划问题。例如,从某仓库送货到零售店然后返回的路线;从零售店到客户地
7、点配送的路线规划。起点和终点重合的路径问题一般被称为“流动推销员”问题(TSP,Traveling Salesman Problem),是运筹学、图论和组合优化中的典型问题。TSP问题一般描述如下:一个旅行者从出发地出发,经过所有要到达的城市后,返回到出发地,要求合理安排其旅行路线,使得总旅行距离(或旅行费用、旅行时间等)最短。人们已经提出不少方法来解决这类问题。第12页/共74页一个起点,一个终点,起点终点重合扫描法(临时客户、临时线路的送货计划)节约法(固定客户,固定线路)第13页/共74页路线设计中的扫描法很简单,即使问题规模很大,也可以通过手工计算得出结果。扫描法可阐述如下:(1 1)
8、在地图或方格图中确定所有站点(含仓库)的位置。)在地图或方格图中确定所有站点(含仓库)的位置。(2 2)自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方)自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑:如果在某线路上增加该站向旋转该直线直到与某站点相交。考虑:如果在某线路上增加该站点,是否会超过车辆的载货能力?如果没有,继续旋转直线,直到点,是否会超过车辆的载货能力?如果没有,继续旋转直线,直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力(先使用最大的车辆)。如果超过,就剔除最后
9、的那个站点,并确(先使用最大的车辆)。如果超过,就剔除最后的那个站点,并确定路线。随后,从不包含在上一条路线中的站点开始,继续旋转直定路线。随后,从不包含在上一条路线中的站点开始,继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。(3 3)排定各路线上每个站点的顺序使行车距离最短。排序时可以)排定各路线上每个站点的顺序使行车距离最短。排序时可以使用使用“水滴水滴”法法。扫描法第14页/共74页例:某公司用厢式货车从货主处取货,图(a)是一天的取货量,单位是件。厢式货车的载货量是10000件。完成所有取货任务需一天时间。
10、公司需要多少条运输路线(即多少部车),每条路线上应该经过哪些站点,每条路线上的站点怎样排序。首先,向北画一条直线,进行逆时针方向“扫描”。这些都是随机决定的。逆时针旋转该直线,直到装载的货物能装上一辆载重10000件的卡车,同时又不超载。一旦所有的站点都分派有车辆,就可以利用“水滴”法安排经过各站点的顺序,图(b)是所列出的最终的路线设计。(a)(b)扫描法设计行车路线缺点:在划分站点群时,没有考虑在途总运行时间、各站点的取货/送货时间等。第15页/共74页2节约法节约法的目标是使所有车辆的行驶总里程最短,并且为所有站点提供服务的卡车数量最少。第16页/共74页d0,AdA,0d0,BdB,0
11、ABO仓库dA,Bd0,AdB,0a)初始路线里程=d=do,Ao,A+d+dA,oA,o+d+do,Bo,B+d+dB,oB,ob)两个站点合并后的路线里=d=do,Ao,A+d+dA,BA,B+d+dB,oB,o节约法示意图该方法先假设每一个站点都有一辆虚拟的车辆提供服务,随后返回仓库,如图(a)所示,这时的路线里程最长。下一步,将两个站点合并到同一条行车路线上(b),减少一辆运输车,相应地缩短路线里程,得到节约距离为dOA+dAO+dOB+dBO(dOA+dAB+dBO)=dAO+dOBdAB第17页/共74页节约法 1、考虑节约路程最多的两个站点,如果合并后能够满足各种约束条件,如:载
12、货能力、时间限制、路程条件等,则合并;否则考虑节约路程次多的站点;2、重复1,直到完成路线设计。优点:在划分站点群和制订路线规划时可以考虑各种约束因素。第18页/共74页某一配送中心p0向10个客户pj(j=1,2,10)配送货物,其配送网络如图所示。图中括号内的数字表示客户的需求量(T),线路上的数字表示两节点之间的距离。配送中心有2t和4t两种车辆可供使用,每次运输距离不大于30km,试制定最优的配送方案。(0.5T)第19页/共74页第一步:计算最短距离。根据配送网络中的已知条件,计算配送中心与客户及客户之间的最短距离 第20页/共74页第二步:计算节约里程 第21页/共74页第二步:计
13、算节约里程第22页/共74页第三步:将节约里程进行分类,按从大到小的顺序排列,得表第23页/共74页第三步:将节约里程进行分类,按从大到小的顺序排列,得表 第24页/共74页第四步:确定配送线路(1)初始方案:对每一客户分别单独派车送货,结果如图 初始方案:配送线路10条配送距离:S0:148km配送车辆:2t10第25页/共74页修正方案1:按节约里程由达到小的顺序,连接p1和p2,p1和p10,p2和p3,得修正方案1,如图 P1p215p10.7tp21.5tP1p1013p100.6tP2p311p30.8t修正方案1配送线路:7条配送距离:S1:109km配送车辆:2t6+4t1第2
14、6页/共74页修正方案2:在剩余的Sij中,最大的是S34和S45,此时p4和p5都有可能并入线路A中,但考虑到线路距离问题,连接p4和p5形成一个新的线路B,接下来最大的Sij是S19和S56,由于此时p1已属于线路A,若将p9并入线路A,车辆会超载,故只将p6点并入线路B,得修正方案2修正方案2配送线路:5条配送距离:S3:90km配送车辆:2t3+4t2 第27页/共74页修正方案3:再继续按Sij由大到小排出S910、S13、S210、S24、S36,由于与其相应的用户均已包含在已完成的线路里,故不予考虑。把S67对应p7点并入线路B中,得修正方案3 修正方案3配送线路:4条配送距离:
15、S4:85km配送车辆:2t2+4t2第28页/共74页最终方案:剩下的是S78,考虑到配送距离的平衡和载重量的限制,不将p8点并入到线路B中,而是连接p8 和 p9,组成新的线路C,得到最终方案,如图 最终方案配送线路:3条配送距离:S4:80km配送车辆:2t1+4t2第29页/共74页练习求节约里程的线路设计,假定该公司有2T和4T车,每次运行距离不超过60KM。第30页/共74页节约里程法需考虑的因素和注意事项(1)适用于顾客需求稳定的配送中心(2)各配送路线的负荷要尽量均衡(3)要充分考虑道路运输状况(4)要预测需求的变化以及发展趋势(5)考虑交通的状况(6)利用计算机软件求解优化第
16、31页/共74页实践中存在的问题在进行运输的车辆调度时,如果每次都按上述方法计算一番,费时费力不说,得出来的结果还不一定适用,因为在纸上或电脑上演算的结果是一种理论上的、理想的线路,而在运输的货物的品种、数量、客户的分布及路况的变化等,随时都可能成为制约因素,如果硬要把计算结果当成指令下达,耽误事不说,还非闹出笑话甚至矛盾不可。我们的学生的绝大部分不具备运用数学工具分析的能力。第32页/共74页但它可以在工作中做到了解:本企业的客户情况、货物的集散渠道、经营辐射范围、自有设备设施的能力、状况;了解与本企业发生关系的各物流结点(集货点、分货点、接货点、收货点)的分布及路线、路型、路况。采用直观判
17、断法就是在直观可见的配送网络图上,判断出最优运输路线。怎样做?第33页/共74页直观判断法1 1、必须有一份配送企业所在位置及业务辐射范围的地理简图,在简图上,把所有客户位置明显标示出来;2 2、从配送起点至所有客户的运行线路都必须经过实际踏勘,对路型(如是否为封闭路、快速路、单向行驶路等)、路况(如路面质量、道路宽窄、是否多车种混行等)、路标(如各种指示标志、交通指示灯的设置等)、各路线高峰时间段、货车准行时间等等所有相关信息都必须掌握,并在简图上尽可能详细地标示出来;3 3、必须有畅通的信息沟通渠道,保持与客户的及时联系,掌握客户的需求,制定出切实可行的配送主计划、日计划和应对突发需求的柔
18、性化特殊配送计划,以达到有章可循、忙中有序的作业秩序;4 4、对货物、客户、车辆、人员、路线、地点、时间深人了解的基础上,加以分析、整理;第34页/共74页直观判断法5 5、只要把配送任务单交给司机并在简图上找出最短运行线路既可与“经验调度法”配合使用,则效果更佳。在下达运输指令时,应该给司机一定的临机处置权,因为配送功能的各要素随时都可能发生意想不到的变化,这就要求司机能够根据变化的情况随机处置,否则就会造成不良后果。如果有条件,在运输车辆上配置GPS系统,则是最理想的,那样,指挥调度就会更灵活、更有效、更便捷。第35页/共74页经验法(1)将相互接近的各站点的货物尽可能安排同一辆车运输。卡
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运输 路线 选择 优化
限制150内