福勒批发公司案例之运输路径规划研究.pptVIP

福勒批发公司案例 之运输路径规划研究 案例简介 福勒批发公司是一家大型酿酒厂啤酒和葡萄酒的地区性特许经销商，罗伊· 福勒是该公司的老板。罗伊面临的主要问题是如何有效地将啤酒和葡萄酒产品运送到客户所在地。 对于预售客户，企业有机会优化运输路线的设计。这些客户订购的货物 被放在单独的卡车上，与那些佣金客户的订货分开，设计送货路线时可以根据实际需要制订计划。 案例简介 由一个仓库提供21个不同地点客户的需求。 有几个客户对送货时间有特殊要求，例如第12号客户只能在08:00AM-08:30AM内送货； 公司有5辆卡车，目前有5条运输线路。 案例最后提出的问题主要是针对给定的条件，如何优化运输线路，优化车辆的调度，实现用最低的成本来完成客户的配送要求。 仓库与各客户分布图 起讫点相同的路径规划 此案例是典型的起讫点相同的路径规划问题。 总运输成本C主要由两部分组成： 运输总里程成本CL，此例中每英里 0.90 美元； 司机的总报酬CP，此例中每小时付司机 13 美元。 要使总运输成本C最小，在此例中卡车平均时速一定的情况下，只需要求出总运输里程最小的方案即为总运输成本最小的方案。 起讫点相同的路径规划数学模型 问题可以描述为：从某个仓库用多台配送车辆向多个客户送货，每个客户的位置和货物需求量一定，各配送车辆的载重量一定，各司机每天的工作时间上限一定，要求合理安排车辆配送路线，使目标函数得到优化。 同时须满足以下条件： 每条配送路径上各客户的需求量之和不超过配送车辆的载重量； 每条配送路线所花费的时间不超过司机的最长驾驶时间； 必须满足每个客户的需求，该客户的需求货物只能由一辆车一次性配送。 起讫点相同的路径规划 为了解决此类问题，人们已经提出不少方法，经典的通常有以下两种： 扫描法（The Sweep Method） 节约法（The Saving Method） 此外，还有一种使用模糊聚类分析加上动态规划的方法，得出的解决方案往往会比以上两种方法更加优化。 扫描法（The Sweep Method） 扫描法求解过程分为两步：第一步是分派车辆服务的站点；第二步是决定行车路线。因为整个过程分成两步，所以对诸如在途总运行时间和时间窗口等时间问题处理得不好。 扫描法求解过程： 自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑：如果在某线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力（先使用最大的车辆）。如果超过，就剔出最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。 排定各路线上每个站点的顺序使行车距离最短。排序使可以使用“水滴”法或求解“流动推销员”问题的任何算法。 扫描法求解结果 线路名称 出发时间 途径站点顺序 第一条运输线路 7：45 12，15，1，14，5 第二条运输线路 7：33 2，3，4 第三条运输线路 7：22 6，16，17，8，9 第四条运输线路 8：00 11，20，18，21，19 第五条运输线路 7：39 7，13，10 我们可以看到，用扫描法求出的结果正好就是案例中福勒公司目前正在采用的运输方案。（我认为案例中第3条线路印刷有误，1应该为6） 经过计算，此方案5条路线共行驶375.29978英里，5位司机工作时间总和为34.8253小时，一天的运输成本为790.75626美元。 扫描法求解结果 扫描法求出的5条线路图 节约法简介 该方法首先假设每一个站点都有一辆虚拟的卡车提供服务，随后返回仓库。这时的路线里程是最长的。下一步，将两个站点合并到同一条行车路线上，减少一辆运输车，相应的缩短路线里程。在决定哪些站点要合并到一条路线时，需要计算合并前后节约的运输距离。 设仓库为点O，两点A和B合并所节约的距离为S＝2Doa+2Dob-(Doa＋Dbo+Dab)=Doa+Dob-Dab．对每对站点都进行这样的计算，并选择节约距离最多的一对站点进行合并在一起。 然后在综合考虑各种限制条件，得出各条线路的规划方案。 模糊聚类分析法 聚类分析又称点群分析、群分析等，是按照研究对象在性质上的亲疏关系进行分类的一种多元统计方法，它能够反映样本之间的内在组合关系。现实中的分类问题大多伴随模糊性，类与类之间并无清晰的界限，在聚类分析中引进模糊技术更为合理，也就是模糊聚类分析。 此方法应用模糊聚类分析对需求站点进行分类，确定企业自营物流的需求点和物流外包的需求点，通过建立车辆调度的数学模型，使用动态规划的方法确定各类中的行车最优路线。 模糊聚类分析法数学模型 设仓库有K台配送车辆，每台车辆的载重量为 Qk(k=1,