求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?

admin2019-07-20  42

问题 求解四个城市旅行推销员问题,其距离矩阵如下表所示,当推销员从1城出发,经过每个城市仅一次,最后回到1城,问按怎样的路线走可使总行程最短?

选项

答案由边界条件可知:f0(2,[*])=d12=8,0(3,[*])=d13=5,f0(4,[*])=df14=6, 当k=1时,即从1城开始,中间经过一个城市到达i城的最短距离是: f1(2,{3})=f0(3,[*])+d32=5+9=14, f1(2,{4})=f0(4,[*])+d42=6+7=13, f1(3,{2})=8+8=16,f1(3,{4})=6+8=14, f1(4,{2})=8+5=16,f1(4,{3})=5+5=10, 当k=2时,即从1城开始,中间经过两个城市(它们的顺序随便)到达i城的最短距离是: f2(2,{3,4})=min[f1(3,{4})+d32,f1(4,{3})+d42]=min[14+9,10+7]=17, 所以p2(2,{3,4})=4, f1(3,{2,4})=min[13+8,13+8]=2l, 所以p1(3,{2,4})=2或4, f2(4,{2,3})=min[14+5,16+5]=19, 所以P2(4,{2,3})=2,故k=3时,即从1城开始,中间经过三个城市(顺序随便)回到1城的最短距离是: f1(1,{2,3,4})=min[f2(2,{3,4})+d21,f2(3,{2,4})+d31,f2(4,{2,3})+d41] =min[17+6,21+7,19+9]=23 所以p3(1,{2,3,4})=2. 由此可知,推销员的最短旅行路线是1—3—4—2—1,最短距离为23.

解析
转载请注明原文地址:https://kaotiyun.com/show/qvVx777K
本试题收录于: 物流数学题库理工类分类
0

最新回复(0)