第二步：考虑到从配货中心出发的送货车辆，在送完所有的门店货物后，仍需要返回配货中心，故再需对生成的最小树采用中国邮递员线路的算法进行扩充。
在图7—2中，奇点有：V0，V1，V3，V4，V6，V7，V8，V9，V10，V12。故需增加边V3V5，重复边V0V1，V5V6，V4V9，V9V10，V7V12，V8V12，V9V12等7条，得图7—3。
图7—3种的粗线部分已给出了送货车量从配送中心出发，送货到10家门店后返回配货中心的具体路线。即可为：
V0—V1—V2—V3—V5—V6—V5—V4—V9—V10—V9—V12—V7—V12—V8—V12—V9—V4—V11—V1—V0。线路的总长度为251米。
V023V71016V110V111598258V12821107V8V9V26V315351810V4V13V524V10V6 图7—3
第三步：进一步优化行车路线，使其加重复边的长度之和小于不加重复边长度之和。检查图中所有的圈，此时要使用图中所有的边，即包含尚不在行车线路的边。 检查发现：圈V7—V8—V12—V7，加重复边的长度为10+7=17， 而不加重复边的长度为16。故要改进，去掉重复边V7V12，V8V12，而增加边V7V8。圈V6—V5—V4—V9—V10—V6中，加重复边的长度为18+21+10=49， 不加重复边的长度为10+24=34，故也要改进，去掉重复边V5V6，V4V9，V9V10。增加重复边V4V5，V6V10。即可得送货线路如下：
V0—V1—V2—V3—V5—V6—V10—V9—V12—V7—V8—V12—V9—V4—V5—V4—V11—V1—V0。线路的总长度减少为235米。见图7—4。总长度较前减少了16百米。
11
V023V71016V110V111598258V128217V8V91024V26V315351810V4V13V5V10V6 图7—4
第四步：检查有重复边的线路是否是多余的。即检查重复边的两端是否已有其他线路相连通，如有的话，可将重复边连同原边从线路图中删去。发现重复边V4V5的两端可通过其他线路相连，可将V4V5及重复边一起从线路图中删去。即可得送货线路如下：
V0—V1—V2—V3—V5—V6—V10—V9—V12—V7—V8—V12—V9—V4—V11—V1—V0。线路的总长度减少为215米。总长度较前减少了20百米。见图7—5。
V023V710167V110V11159258V12821V286V8V91024V315351810V4V13V5V10V6 图7—5
12
第五步：要综合考虑问题，在优化第三步时，同时考虑第四步有没有重复边是多余的。此例题发现：圈V0—V1—V2—V13—V0中，加重复边的长度为23， 不加重复边的长度为15+9+8=32，故不需要改进，但是，去掉重复边V0V1，增加重复边V1V2，V0V13，V13V2。则V1V2成为重复边，发现重复边V1V2的两端可通过其他线路相连，可将V1V2及重复边一起从线路图中删去。这样去掉重复边V0V1和V1V2，总和长度为31百米，增加V0V13和V13V2，总和长度为24百米，总长度较前减少了7百米。即可得送货线路如下： V0—V1—V11—V4—V9—V12—V7—V8—V12—V9—V10—V6—V5—V3—V2—V13—V0。线路的总长度减少为208米。见图7—6。
V023V710167V110V11158258V12821V86V29V315351810V4V91024V13V5V10V6 图7—6
（二）分送式配送运输线路优化
配送运输过程中影响运输的因素很多，如车流量的变化、道路状况、客户的分布状况和配送中心的选址、道路交通网、车辆额定载重量以及车辆运行限制等。线路设计就是整合影响运输的各因素，适时适当地利用现有的运输工具和道路状况，及时、安全、方便经济地将客户所需的不同物资准确送达客户手中，以便提供优良的物流服务。在运输线路设计中，需根据不同客户群的特点和要求，选择不同的线路设计方法，最终达到节省时间、运行距离和运行费用的目的。
分送式运输是指由一个供应点对多个客户的共同送货。其基本条件是所有客户的需求量总和不大于一辆车的额定载质量。送货时，由这一辆车装着所有客户的货物，沿着一条精心选择的最佳线路一次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，又节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。
例：图7—7所示为某配送中心的配送网络，图中P0点为配送中心，P1、P2、P3、P4、P5、P6、P7、P8、P9、P10为配送客户，共10位客户，括号内为配送货物吨数，线路上的数值为道路距离，单位为km。现配送中心有额定载重量分别为2吨和4吨两种厢式货车可供送货使用，试用节约法设计最佳送货路线。
13
0.461.4P5P425861.5P20.855P3491076754P0342P70.6P80.81044P10P10.70.6811731.5P669P90.5 图7—7
第一步：计算最短距离
首先计算网络结点之间的最短距离（可采用最短路求解法）。计算结果如表9—3所示。
表7—3
P0109788834107P1491418181314114P251014171213158P3591510111713P461311121815P5710121815P6681715P72P8119P910118P10 第二步：计算节约里程
根据最短距离结果，计算出各客户之间的节约行程，结果见表7—4。 表7—4
14
P115840000913P2117300048P310600001P41030000P591000P65410P75P825P9009P10 第三步：将节约里程进行分类， 对节约行程按从大到小的顺序排列，如表7—5所示。 表7—5 序号 1 2 3 4 4 6 6 6 9 9 11 12 路线 P1P2 P1P10 P2P3 P3P4 P4P5 P1P9 P5P6 P9P10 P1P3 P2P10 P2P4 P3P6 节约里程 15 13 11 10 10 9 9 9 8 8 7 6 序号 13 13 13 16 16 16 19 19 21 22 22 22 路线 P6P7 P7P8 P8P9 P1P4 P2P9 P6P8 P2P5 P4P6 P7P9 P3P10 P5P7 P6P9 节约里程 5 5 5 4 4 4 3 3 2 1 1 1
第四步：确定配送线路
按节约里程大小顺序，组成线路图。
1、初始方案：如图7—8所示，从配送中心P0分别向各个客户进行配送，对每一客户分别单独派车送货，共有10条配送线路，总行程为148公里，需2吨货车10辆。
15