寻找 34个城市 中国旅行商问题 CTSP 最优解 ？--- 15708.9 km

FreddyMusic

由于坐标数值差异，计算的距离可能略有不同，但是图形和序列能反映优化的结果。

以下三种是已知的最优解，我想知道是否还有更优解 ？

但是在 34!/2 的解的空间很难说是否还有更优化的结果，

各位看看有何感想？

[ 本帖最后由 FreddyMusic 于 2008-3-25 10:10 编辑 ]

shamohu

坐标数据能放上来吗？

FreddyMusic

不好意思！刚才忘了。

附件是 Excel 含 34 个城市坐标！

我基于此计算！

FreddyMusic

还有我计算的函数是基于球坐标，假设地球为理想球体 直径为 6371.11 公里

pcqsl

I have found 2 better results  using Matlab program.

[ 本帖最后由 pcqsl 于 2008-3-18 18:59 编辑 ]

FreddyMusic

pcqsl，

谢谢你的实践。我对这图还在思考。
现在的最优解有点像是把我的图两种优势结合起来的。
我对此也存在疑惑。



但是这个图多少看上去有点像，很久以前被认为的最优解。



想跳回头的狼狗，现在的区别就是：前人是31个城市，我们是34个城市。
多的是重庆和港澳。造成部分路线的增加。

我在思考的两问题：
1. 现在优化的许多结果中，东北三省和南方大多城市，优化的路线基本相同。
  有争议和不同的是中国中部的一些城市。但是计算机如何有效的判断？

2. 我们现在做的是 TSP 问题，是一个 NP 完全问题。
  它从 a 城市开始， 兜一圈，最终回到 a 城市。
  最终结果是一个封闭的回路。

  如果（另一种题目和假设）
  我们从 a 城市开设，兜一圈 ，最终回到 b 城市，
  (也途径覆盖 34 个城市)。  最终结果是一个开放的回路或是一根折线。
  举例：如果从 新疆开始，到北京结束。
  这样会不会更短？是否有最短路径？

你怎么想？

[ 本帖最后由 FreddyMusic 于 2008-3-19 09:52 编辑 ]

pcqsl

I think your second problem is an NPC problem too.  The shortest route is always exist because there are only finite routes.   But to find it is difficult.

I do not use the knowledge of of the data.  
My program is based on the idea of using local optimal solution to approach global solution.  The local optimal solution is obtained by an optimization algorithm.  To get more accurate result, I use plenty of initial conditions.  The result is good in the probability sense.  Although the global solution is not guaranteed, this method could give a benchmark.

Let me talk a little about the algorithm of finding local solution.  Take any route, for example, -A-B-C-D-E-.  We first break it into two pieces: -A-B-C- and -D-E-.  Such partition is of course not unique.  Then we reconnect them with the different way, which is -A-B-C-E-D-.  Note that one piece is placed in the reverse order.  If the new route has shorter length, we will take it.  By repeating this procedure, we should end up with a solution.  This is usually a local optimal solution because we don't accept intermediate results which is longer.

I think this algorithm applies to your second problem too.  The difference is that there is some limitation on partition.

I have a feeling that it is possible to reduce the order but without any theory or proof. Just some thoughts.  For example, xinjiang can not connect to cities too far away,  can we deal with it later?  Or, chengdu and chongqing are so close, maybe they should be always treat as one.  With some distance constrains, can we prove this?

shamohu

由经纬度来计算两点间的距离，用的哪个公式？与下面的一样吗？

地球的直径为D，两点的经纬度为X1、Y1和X2、Y2   
  const   pi   =3.14159   
距离＝ ((((X2-X1)*pi)^2   +   ((Y2-Y1)*pi)^2)^(1/2))*D

FreddyMusic

pcqsl,

Thank you for your kindly clarify algorithm that helps me to understand better.

1st problem
Regarding my previous experience, Mathematica can solve the TSP lower than 10 different locations.
Because the computer calucate them all by " All Tours ".
But, If the location goes up to 11, the computer can not do it all any more.

My feeling is all available algorithm has advantage and disadvantage.
They all have the ability to approach the best answer.
All of them was a shortest loop, until another even shorter is found.
None of them can be proved as the shortest loop. As we cann't have a pure math prove at the moment. But we trust it is there.
As you clarified, there is a chance to find a better solution, there is a chance to lose the best solution.

I image your " distance constrains " is a radius range like radar plot.
But how big is this radius ?  how to set right point as certre ?
We can see and find on chart, How can we best tell the computer ?

Just my feeling, That would be the golden rate, If someone can solve the problem,
how to best balance between the local optimize and global optimze ?


2nd problem
You are right on judge the 2nd problem. A clear define 2nd problem can be something like this.
Problem: We have 34 cities , a foreign salesman wish to travel in China. He destination is city A ( Beijing).
He is free to chose from bordering cities as starting city. Can we find the shortest route to cover all 34 cities ?

I check with Mathematica the answer appears like, The computer is looking from the fartherst city ( I assume , It's Urumqi ), then windingly goes to last city ( I assume, it's Beijing ). When it approach the last city, it makes a almost close loop. The longitude distance from Urumqi to Beijing is grealty reduce by go one direction. But makes other distance quite long.
It looks like a line + a loop. ( as the Beijing is in centre of China. ) If the last city is also close to bordering, that is probably a multilateral Line.

Demo and Benchmarking
This small project has been released by Mathematica as demo project. Code is free download.
http://demonstrations.wolfram.com/OptimizingThe2008BeijingOlympicTorchTour/
That's a better idea to reduce the distance than government tour. But I know that is not perfect answer.
For me, It's interesting to learn a little bit more and know what is a better answer.

Please check this loop, see if it is 15708.902 km ? We name it "fly bird" at the moment?
but I still don't believe it is a shortest loop. That data might go less than 15700.
Then compete more and more precision at digital, until it's approach the 10^ -23 probably.
( 34！/2 = 1.47 X 10^23 )

[ 本帖最后由 FreddyMusic 于 2008-3-20 08:52 编辑 ]

FreddyMusic

原帖由 shamohu 于 2008-3-19 22:56 发表
由经纬度来计算两点间的距离，用的哪个公式？与下面的一样吗？

地球的直径为D，两点的经纬度为X1、Y1和X2、Y2   
  const   pi   =3.14159   
距离＝ ((((X2-X1)*pi)^2   +   ((Y2-Y1)*pi)^2)^(1/2))*D

Mathmatica 代码下载：
http://demonstrations.wolfram.com/OptimizingThe2008BeijingOlympicTorchTour/

球坐标参考计算：
大致思路是先把经纬度转在球坐标上转换为三维坐标，
然后计算球面上任意两点的弧线长度。

也许1opt 可以发现点新的结果，试试！

[ 本帖最后由 FreddyMusic 于 2008-3-20 08:48 编辑 ]

pcqsl

原帖由 shamohu 于 2008-3-19 22:56 发表
由经纬度来计算两点间的距离，用的哪个公式？

For given points, p1=(latitude1, longitude1) and p2=(latitude2, longitude2) on a ball, there are two ways to measure their distance.  First, find a great cycle passing through both points, use the length L of a piece of arc on the great cycle connecting these points.    Second, use the angle A between p1 and p2 by looking at them as vectors.  These two methods are equivalent because L=A*R, where R is the radius of the great cycle.

We use the second method.  We first rewrite two vectors in R^3 space and normalize it(dividing by R):
V_i= ( cos(latitude_i)*cos(longitude_i), cos(latitude_i)*sin(longitude_i), sin(latitude_i) )  , where i=1,2.  
Note that here longitude and latitude are measured by RAD rather than degree.

We calculate the length of the projection of one vector onto the other as v=<V1,V2>, where <,> denote the inner product.  Explicitly, <(a1,a2,a3),(b1,b2,b3)>=a1*b1+a2*b2+a3*b3.

Since V1 and V2 are normalized,  cos(A)=v.  In other words, A=acos(v).

[ 本帖最后由 pcqsl 于 2008-3-21 19:23 编辑 ]

pcqsl

To FreddyMusic,

Congratulations! Your better result is confirmed.   

By comparing your new result with my old one, I come up a new optimization algorithm.  It takes a piece from a loop and inserts it into a different place.  My program will converge to the new result very quickly with this help.  Unfortunately , no better result is obtained.

FreddyMusic

pcqsl，

我想你没有问题阅读中文，所以我用中文把问题写清楚，以便其他会员阅读和加入探讨。

我在考虑如何证明我们现在的结果是正确的或者大致是正确的。我想到两点。

1. 精度问题，以前我说精度要到 10^ -23 ，这过于偏激。
  我想你现有的取舍很正确，保留小数点后 3 位，就足够了，
  即代表了 1 米之遥。如果精度再提高对实际意义也不大了。

2.只是个想法，如果以概率的分布测试现有结果。
  将10000 个任意随机结果的值求解概率分布曲线，
  随后查看现有最优值和置信区间，以便得出结论。
  像是：比现有15700 的结果更小的数值，可能性还有 0.001% 等等。

我周末再来搞。

shamohu

这是一解：
125.35 43.87
123.45 41.8
117 36.67
117.28 31.85
118.78 32.05
121.47 31.23
120.17 30.25
121.45 25.02
119.3 26.08
115.88 28.68
114.27 30.58
112.97 28.2
113.25 23.12
114.15 22.28
113.55 22.2
110.32 20.05
108.32 22.82
106.72 26.58
106.58 29.57
104.07 30.67
102.7 25.05
91 29.6
87.58 43.8
101.77 36.62
103.68 36.05
106.27 38.47
108.9 34.27
113.67 34.75
112.55 37.87
111.64 40.82
114.48 38.05
116.4 39.93
117.2 39.13
126.65 45.75

[ 本帖最后由 shamohu 于 2008-3-21 10:55 编辑 ]

shamohu

这是附图

FreddyMusic

原帖由 shamohu 于 2008-3-21 10:56 发表
这是附图

感谢你的实践和我们共同参与解决问题！

这个解就是现在 Mathematica demo 上的解，但遗憾不是最优解，在球坐标里程是 15782.4 km 。

我想平面坐标和球坐标还是有差异的，球坐标更好点。你把它换到球坐标再试试！

FreddyMusic

pcqsl,

I did some calucation on statistic. Only for your information and get some feeling.

The total quantity of solution is 34!/2 =1.5 * 10^34.

I take 10^5 data by function calucation as random samples. Then study this sample. Find....

If we want to reduce from 15709 km to 15708 km, The possiblity is 4.3%.

If we want to reduce from 15709 km to 15704 km, The possiblity is 10^ -7.

If we want to reduce from 15709 km to 15680 km, The possiblity is 10^ -40.

I show you exactly calucation on monday.

[ 本帖最后由 FreddyMusic 于 2008-3-22 19:17 编辑 ]

FreddyMusic

pcqsl,

Two points !

1. Can you evaluate, how many data we has searched with your algorithm at the moment ?
   Just to get the feeling how big is our net and how big is the ocean.

2. Still have the feeling that there is another better answer.

pcqsl

It is not easy to evaluate.  But I believe that a big region has been searched.  Since I will be extremely busy next week, I will think about it later.

智学德

你的结果对我很有参考价值，谢谢！