实训项目六配送线路优化设计
配送中心p0向10个客户pj（j12…，10）配送货物，其配送网络如图所示。图中括号内的数字表示客户的需求量（T），线路上的数字表示两节点之间的距离。配送中心有2t和4t两种车辆可供使用，试制定最优的配送方案。
第一步：计算网络节点的最短途径，计算结果见下表。
网络节点的最短途径
单位：km
P0
P1
10
P1
P2
9
4
P2
P3
7
9
5
P3
P4
8
14
10
5
P4
P5
8
18
14
9
6
P5
P6
8
18
17
15
13
7
P6
P7
3
13
12
10
11
10
6
P7
P8
4
14
13
11
12
12
8
2
P8
P9
10
11
15
17
18
18
17
11
9
P9
P107
4
8
13
15
15
15
10
11
8
第二步：用户之间的节约里程，见下表。
用户之间的节约里程
单位：km
P1
P2
15
P2
P3
8
11
P3
P4
4
7
10
P4
P5
0
3
6
10
P5
P6
0
0
0
3
9
P6
P7
0
0
0
0
1
5
P7
P8
0
0
0
0
0
4
5
P8
P9
9
4
0
0
0
1
2
5
P9
P1013
8
1
0
0
0
0
0
9
P10
f第三步：对节约里程按大小顺序进行排列，结果见下表。
节约里程排序表
序号
连接点
节约里程
序号
1
p1p2
15
13
2
P1p10
13
14
3
P2p3
11
15
4
P3p4
10
16
5
P4p5
10
17
6
P1p9
9
18
7
P5p6
9
19
8
P9p10
9
20
9
P1p3
8
21
10
P2p10
8
22
11
P2p4
7
23
12
P3p5
6
24
单位：km连接点P6p7P7p8P8p9P1p4P2p9P6p8P2p5P4p6P7p9P3p10P5p7P6p9
节约里程555444332111
第四步：根据节约里程排序表和配送车辆载重量等约束条件，逐步求出最优配送路线，初始解：从P0向各个用户配送，共有10条线路，总的运行距离为160KM，需要2吨车10量。
二次解：按照节约里程的大小顺序连接P1P2P2P3P3P4P1P10，由于P1P3已经在一条配送线路中，因而不在连接P1P3。此时，配送线路共6条，需要4t车一辆，2t车五辆。总运行距离为66KM。配送线路一的运行距离为33KM，装载量为4t。图如下所示：
f三次解：连接P4P5P5P6P6P7P9P10，但因为P9加入配送线路一后，会超过车辆最大载重量4t，所以不连接，同理不连P4P5。此时，总的配送线路为4条，需要4t的车两辆，2t车两辆，总的配送距离为71KM。配送线路二的运行距离为24KM，载重量为35t。
四次解：连P7P8P8P9，但因为把P8并入线路二后，会超过车辆最大载重量4t，因此不连P7P8。此时，总的配送线路为3条，需要4t车两辆，2t车一辆，总的配送距离为80KM。配送线路三的运行距离为23KM，装载量为13t。图如下所示：
f第五步：综合上述步骤可得出最优解，最终形成三条配送线路，总的运行距离为80KM，需
要2t车一辆，4t车两辆。具体如下所述。图如下所r