配送线路优化设计实训

1、实训 0501：配送线路优化设计实训实训目标：1、能根据给出的配送中心与单个客户之间的路线图及图中各节点之间的综合成本数值， 找到配送中心与单个客户之间的成本最小路线并计算出此路线成本的数值。2、能够在配送中心现有送货车辆能力及实际送货成本限定的前提下，规划出配送中心 往各个客户送货综合成本最低的送货网络路径图。实训内容：1、某配送中心与某单个客户之间成本最小路线规划及最小成本数值计算2、在配送中心现有车辆送货能力及车辆单趟送货成本有限定的前提下，为配送中 心向多个客户送货规划若干条送货线路，并使各条线路的总成本数最小。环境要求： 普通多媒体机房教室情境描述：实训第 1 部分情境： 某连锁超市

2、的配送中心位于城市边缘的郊区，但超市的一家门店位于 繁华的城市中心区， 因此负责送货路线规划的计划调度员要规划出配送中心到这个门店的送货成 本最低的路线。最初按交通图所示里程最短的线路进行送货，见下图：图中 O代表配送中心， A 代表门店， V1 V4代表要经过的关键节点 （如主要道路的交叉 路口、立体交叉互通枢纽等） ，连线边上的数值代表每一路段的里程，图中绿线连接的 O-V1-V4-A 为里程最短线路。但很快发现里程最短并不意味着成本最低， 因为里程最短这条路有一条新建的大桥 （图 中 V4点与 A 点之间黑色加粗部分）来回都要收取通行费，这条路是城区主干道且建成时间 较长通行条件较差，

3、越往城中心走道路拥堵越严重， 每趟送货产生的油耗、 车辆送货时间占 用、送货人员工作时间等综合成本超出了正常水平， 并且多次发生没按门店的要求时间送达 的情况。 因此计划调度员对每一条能从 O到 A 的线路都进行了实地勘察记录， 并综合考虑每 条送货线路的里程、时间、车辆耗损，得出了每条线路每一个路段的送货运行成本，汇总出 了一张从配送中心到此门店的送货路径数据图。 现在计划调度员要依据此图， 找出配送中心 与该门店之间送货成本最低路径。实训第 2部分情境： 该配送中心除为该门店送货外， 还为其他地区的 9 个门店送货， 按 照实训第 1 部分的方法， 计划调度员找到了配送中心到每个门店的成本

4、最低线路， 但配送中 心的送货资源有限， 不能为每个门店单独送货， 只能一辆车一趟为几个门店循环送货。 这样 从一个门店到另一个门店之间也要找到成本最低的线路，因此同样采用实训第 1 部分的方 法，找到了两两门店之间的成本最低线路并计算出了数值。现在， 计划调度员要规划从配送中心出发为各个门店循环送货后最终回到配送中心的送货路线总规划图并且总送货成本要最低。8798810O3710600)E1400)H800)F1500)B1500)I500)A700)D400)C800)G600)配送中心到各门店及两两门店之间的成本最低线路数值表OA10AB94BC795CD814105DE8181496E

5、F8181715137FG313121011116GH4141311121282HI10111517181817119IJ7481315151510118实训组织形式： 学生独立完成实训过程。实训资料：O代表配送中心， A 代表门店，1、配送中心与位于城中心门店之间的网络路线图，图中，连线V1V4代表要经过的关键节点（如主要道路的交叉路口、立体交叉互通枢纽等） 边上的数值代表每一路段送货运行的最低成本值。1V1V48337OA1124V2V32、配送中心的配送网络， 见下图。 图中 O点为配送中心， AJ 为要送货的门店， 共 10 个门店。括号内为配送货物重量（单位：公斤） ，线路边上的数字

6、为配送中心送货到各 门店的最低成本值。工作流程： 计算配送中心与某一个门店之间的最小成本线路计算配送中心到其它门店及两两门 店之间的最小成本线路数值 （此步骤采用与上一步骤相同的计算方法均可计算出来， 考虑实 训时间限制，计算过程从略，直接给出数据表）规划从配送中心出发（最后还要回到配送 中心），在货车载重及单趟送货总成本限制下单趟可送货门店最多的线路把计算出的各条 送货线路标示出来，形成一张送货路径规划图。实训步骤：1、 根据实训资料 1 给出的配送中心与城中心门店之间的网络路径图， 找出配送中心 （O 点）到这个门店（ A 点）之间成本最低线路并算出成本值。第一步：O点是原始已解节点，从配

7、送中心O点出发，可以走V1、V2 两个节点，由于OV13、OV1线路， V1 成为已解节点，见下图。OV211，因此选择走第二步：与 O、V1 两个已解节点相连的未解节点有V2、 V3、V4，可选择的送货路线为： O-V1-V4、O-V1-V3、O-V2，相应的送货成本值为：O-V1-V43+14O-V1-V33+710O-V211O-V1-V4 线路的成本最少，因此 V4 成为已解节点，见下图。第三步：与 O、V1、V4三个已解节点相连的未解节点有V2、V3、A，可选择的送货路线为： O-V1-V4-A 、O-V1-V4-V3 、 O-V1-V3、O-V2，相应的送货成本值为：O-V1-V4

8、-A3+1+812O-V1-V4-V3 3+1+3 7O-V1-V33+710O-V211O-V1-V4-V3 线路的成本最少，因此 V3 成为已解节点，见下图。1V18337OA1124V2V31第四步：与 O、V1、V4、V3 四个已解节点相连的未解节点有V2、 A ，可选择的送货路线为：O-V1-V4-V3-A 、O-V1-V4-V3-V2 、O-V1-V3-A、O-V1-V3-V2 、O-V2，相应的送货成本值为： O-V1-V4-V3-A 3+1+3+4 11O-V1-V4-V3-V2 3+1+3+18O-V1-V3-A3+7+414O-V1-V3-V2 3+7+1 11O-V211

9、O-V1-V4-V3-V2 线路的成本最少，因此 V2 成为已解节点，见下图。1V1V48337OA1124V2V31第五步：与 O、V1、 V4、 V3、V2 五个已解节点相连的未解节点只有A，可选择的送货路线为：O-V1-V4-V3-A 、 O-V1-V4-V3-V2-A 、O-V1-V3-A、O-V1-V3-V2-A 、 O-V2-A、O-V1-V4-A ， 相应的送货成本值为：O-V1-V4-V3-A 3+1+3+4 11O-V1-V4-V3-V2-A 3+1+3+1+210 O-V1-V3-A3+7+414O-V1-V3-V2-A 3+7+1+2 13 O-V2-A11+213O-V

10、1-V4-A3+1+812O-V1-V4-V3-V2-A 线路的成本最少， 因此这条线路是配送中心与该门店之间成本最低的 送货线路，线路的送货成本数值为 10，见下图。1V18337OA1124V2V31最后通过与实训情境中里程最短路线 O-V1-V4-A 的成本比较一下， 里程最短路线的成本为 12，成本最小路线 O-V1-V4-V3-V2-A 的成本为 10。2、 该配送中心除为该门店送货外， 还为其他地区的 9 个门店送货， 按照实训第 1 部分 的方法， 计划调度员找到了配送中心到每个门店的成本最低线路，但配送中心的送货资源有限， 不能为每个门店单独送货， 只能一辆车一趟为几个门店循环

11、送货。 这样从一个门店到另一个门店之间也要找到成本最低的线路。通过一段时间的努力， 计划调度员找到了配送中心到每个门店的成本最低线路及两两门店之间的成本最 低线路并计算出了数值。配送中心的现有送货限制为：只有额定载重分别为 2 吨 和 4 吨两种厢式货车可供送货 （即送货路线上各客户的货物总重小于 2 吨的使用 2 吨的车型， 超过 2 吨的用 4 吨的车型， 但送货路线上各门店的货物总重最多不超过 4 吨）考虑到达门店装卸后交付时间、送货路上时间、综合成本等因素，每辆车每 次送货的成本不能超过 30。步：配送中心到各门店及两两门店之间的成本最低线路数值表OA10AB94BC795CD8141

12、05DE8181496EF8181715137FG313121011116GH4141311121282HI10111517181817119IJ7481315151510118根据“配送中心到各门店及两两门店之间成本最低线路的数值表（见上表） ”和节约法的基 本原理，计算出两两门店之间的节约成本。计算方法是： i,j 是任意相邻两门店节点 Oi=a ， OJ=b， ij=c ，则 i j 节约的成本为： a+b-c 。例如： A， B 两点的节约成本为， OA+OB-AB 10+9-4 15。计算结果填入下表中。AB15BC811CD4710DE03310EF00039FG000015GH0

13、000045HI94000125IJ1381000009J4、根据上表中的出两两门店之间的节约成本计算结果，按节约成本大小顺序排列到下 表中。序号连接点节约里程序号连接点节约里程1AB1513FG52AJ1313GH53BC1113HI54CD1016AD44DE1016BI46AI916FH46EF919BE36IJ919DF39AC821GI29B J822C J111BD722EG112CE622FI15、有了以上计算数据后就可以对初始的送货路线进行优化了。下图是初始方案，从配 送中心分别向各个门店节点送货，共有 10 条送货路线，总成本数为 148，需载重 2 吨的货 车 10 辆。如

14、下图所示。6、按节约成本的大小顺序链接 A-B,A-J,B-C, 同时取消 OB、O-A 路线, 形成巡回路 线 , 如下图所示。这时配送路线共有 7 条，各条线路总成本为 109 ，需要载重 2 吨的货车 6 辆，4 吨的货车 1 辆。见下图 （图中绿色线条代表选中的线路， 红色线条代表取消的线路， 后续各图均同） 。由图可知 , 规划的配送路线 1 ，装载货物吨，成本为 27 。7、按节约成本大小顺序 , 应该是 但目前配送路线 1 已装载货物吨运行成本为（ 每条线路成本不超过 30 ） , 配送路线 1 不能再增加送货门店 组成配送线路 2, 如下图所示。 其装载重量为吨 , 成本 22

15、 。此时，共有配送线C-D 和有可能并到二次解线路 1 中 ,限制D-E,C-D27 公里，考虑到单车载重量和线路成本, 为此连接D-E,路 68、下面的节约成本大小顺序是A-I 、 E-F, 由于门店 A 己组合到配送线路 1 中，该线路不再增加新门店，故不连接 A-I; 连接 E-F 并入配送线路 2 中，并取消 O-E 线 路，此时配送线路共有 5 条 , 如下图所示。线路 2 的装载量为 吨 , 运行成本为29 。此时，共有配送线路 5 条，总运行成本为 90 ，需载重 2 吨的货车 3 辆 ,4 吨 的货车 2 辆。9、按节约成本顺序，接下来应该是I-J,A-C,B-J,B-D,C-E,但这些连接已包含在配送线路 1 或 2 中 , 不能再组合成新的线路。再下来是 F-G, 可组合在配送线路 2 中，如下图所示。 此时，线路 2 的装载量为 吨 , 运行成本为 30 , 这样共有 4 条线路总成本为 85 , 需载重 2 吨货车 2 辆 ,4 吨的货车 2 辆。10、接下来的节约成本顺序为 G-H, 由于受装载量及线路里程的限制，不再组合到线路 2 中，故连接 H-I 组成配送线路 3, 如下图所示