Salesman Problem),是运筹学、图论和组
合优化中的典型问题。
•
TSP问题一般描述如下:一个旅行者从出
发地出发,经过所有要到达的城市后,返回到
出发地,要求合理安排其旅行路线,使得总旅
行距离(或旅行费用、旅行时间等)最短。人
们已经提出不少方法来解决这类问题。
第12页/共74页
一个起点,一个终点,起点终点重合
0
3
6
10 P5
0
0
0
3
9
P6
0
0
0
0
1
5
P7
0
0
0
0
0
4
5
P8
9
4
0
0
0
1
2
5
P9
13 8
1
0
0
0
0
0
9
P10
第22页/共74页
第三步:将节约里程进行分类,按从大到小的顺序排列, 得表
序号 1 2 3 4 4 6 6 6 9 9 11 12
路线
节约里程
序号 13 13 13 16 16 16 19 19 21 22 22 22
dAB
第17页/共74页
节约法
1、考虑节约路程最多的两个站点,如果合并后能够满足各种约束条件,如:载 货能力、时间限制、路程条件等,则合并;否则考虑节约路程次多的站点;
2、重复1,直到完成路线设计。 优点:在划分站点群和制订路线规划时可以考虑各种约束因素。
第18页/共74页
• 某一配送中心p0向10个客户pj( j=1,2,…,10)配送货物,其 配送网络如图所示。图中括号内的数字表示客户的需求量 (T),线路上的数字表示两节点之间的距离。配送中心有 2t和4t两种车辆可供使用,每次运输距离不大于30km,试 制定最优的配送方案。