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

福勒批发公司案例 之运输路径规划研究案例简介• 福勒批发公司是一家大型酿酒厂啤酒和葡萄酒 的地区性特许经销商，罗伊· 福勒是该公司的 老板罗伊面临的主要问题是如何有效地将啤 酒和葡萄酒产品运送到客户所在地 • 对于预售客户，企业有机会优化运输路线的设 计这些客户订购的货物 被放在单独的卡车 上，与那些佣金客户的订货分开，设计送货路 线时可以根据实际需要制订计划案例简介• 由一个仓库提供21个不同地点客户的需求 • 有几个客户对送货时间有特殊要求，例如第12 号客户只能在08:00AM-08:30AM内送货； • 公司有5辆卡车，目前有5条运输线路• 案例最后提出的问题主要是针对给定的条件， 如何优化运输线路，优化车辆的调度，实现用 最低的成本来完成客户的配送要求仓库与各客户分布图起讫点相同的路径规划• 此案例是典型的起讫点相同的路径规划问题• 总运输成本C主要由两部分组成： – 运输总里程成本CL，此例中每英里 0.90 美元； – 司机的总报酬CP，此例中每小时付司机 13 美元• 要使总运输成本C最小，在此例中卡车平均时速一定 的情况下，只需要求出总运输里程最小的方案即为 总运输成本最小的方案。

起讫点相同的路径规划数学模型• 问题可以描述为：从某个仓库用多台配送车辆向多 个客户送货，每个客户的位置和货物需求量一定， 各配送车辆的载重量一定，各司机每天的工作时间 上限一定，要求合理安排车辆配送路线，使目标函 数得到优化 • 同时须满足以下条件： – 每条配送路径上各客户的需求量之和不超过配送车辆的载 重量； – 每条配送路线所花费的时间不超过司机的最长驾驶时间； – 必须满足每个客户的需求，该客户的需求货物只能由一辆 车一次性配送起讫点相同的路径规划• 为了解决此类问题，人们已经提出不少方法，经典 的通常有以下两种： – 扫描法（The Sweep Method） – 节约法（The Saving Method）• 此外，还有一种使用模糊聚类分析加上动态规划的 方法，得出的解决方案往往会比以上两种方法更加 优化扫描法（The Sweep Method）• 扫描法求解过程分为两步：第一步是分派车辆服务的站点 ；第二步是决定行车路线因为整个过程分成两步，所以 对诸如在途总运行时间和时间窗口等时间问题处理得不好 • 扫描法求解过程： 1.自仓库始沿任一方向向外划一条直线沿顺时针或逆时针方 向旋转该直线直到与某站点相交。

考虑：如果在某线路上增 加该站点，是否会超过车辆的载货能力？如果没有，继续旋 转直线，直到与下一个站点相交再次计算累计货运量是否 超过车辆的运载能力（先使用最大的车辆）如果超过，就 剔出最后的那个站点，并确定路线随后，从不包含在上一 条路线中的站点开始，继续旋转直线以寻找新路线继续该 过程直到所有的站点都被安排到路线中 2.排定各路线上每个站点的顺序使行车距离最短排序使可以 使用“水滴”法或求解“流动推销员”问题的任何算法扫描法求解结果线路名称出发时间途径站点顺序第一条运输线路7：4512，15，1，14，5第二条运输线路7：332，3，4第三条运输线路7：226，16，17，8，9第四条运输线路8：0011，20，18，21，19第五条运输线路7：397，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,2,…,K)，需要向L 个客户送货，每个客户的货物需求量为qi (i=1,2,…,L)，需求站点i到j的运 距为dij ，物流中心到各客户的距离为d0i (i=1,2,…,L)。

再设 nk为第k台 车辆配送的客户数( nk=0表示未使用第k台车辆)，用集合Rk表示第k条路 径其中的元素rki 表示客户rki 在路径k中的顺序为i(不包括物流配送中心 )，并令rk0 =0表示物流中心 •以配送总里程最短为目标函数，建立车辆优化调度问题的数学模型为： （1）以需要访问的站点数作为阶段，状态变量为 sm， sm为车辆当前所在 的站点，Rk / sm 为车辆尚未到达的站点，其中 sm∈Rk （2）决策变量um 与sm 有关，是在sm 的状态下做出的选择，允许决策集 合为Rk /sm ， um形成的序列即为决策序列 （3）从第m个状态到达第m+1个状态的状态转移方程为（4）指标函数为从 sm出发，遍访 Rk中的每一个点回到仓库的最优路线求解过程• 使用MATLAB编程，聚类图如下图所示：求解过程• 根据上图，按照卡车运量可将21个客户分为为五 组，这种分类的相干系数为0.6731如下表所示第一条运输线路16，17，18，19，21第二条运输线路9，10，11，20第三条运输线路2，8，14，15第四条运输线路1，3，5，6，12第五条运输线路4，7，13求解过程• 将每条线路按照各自时间窗口的要求使用动态规 划求得其各条线路的途径站点顺序、出发时间和 最终回到仓库的时间如下表：线路名称出发时间途径站点顺序回仓库时间第一条运输线路7：5516，17，午餐，19，18，2115：59第二条运输线路7：2610，11，20，午餐，914：06第三条运输线路7：098，2，15，午餐，1414：30第四条运输线路7：4712，1，3，午餐，6，514：45第五条运输线路7：347，13，4，午餐13：16优化之后的5条线路图• 此方案5条路线共行驶295.29925英里，5位司机 工作时间总和为31.6453小时，一天的运输成本 为677.1582683美元。

• 而我们此前用扫描法得出的方案（即案例中目 前的方案）5条路线共行驶375.29978英里，5位 司机工作时间总和为34.8253小时，一天的运输 成本为790.75626美元 • 二者相比较，每天可节约113美元的成本，节约 将近15%可见在处理此类运输优化问题中， 模糊聚类分析法具有较大的优势，值得推广模糊聚类分析法求解结果谢谢！。