algorithm - 为 TSP 的欧几里德实例创建图形

Question

我目前正在围绕旅行商问题进行研究。更准确地说，我正在使用 EUC_2D 边缘权重类型处理样本数据。像下面这样:

1 11003.611100 42102.500000
2 11108.611100 42373.888900
3 11133.333300 42885.833300

我可以制作旅游订单。例如，2-3-1。

我希望能够创建一些简单的图形，这些图形表示给定问题的点集，然后是在顶部进行巡视的点集。谁能推荐一种实现此目的的简单方法 - 我应该使用什么软件来实现此目的。

谢谢

Answer 1

只是给你一个关于通常的科学绘图工具如何工作的快速演示(假设我正确理解你的任务):

使用 python 和 matplotlib 的仅绘图代码:

import matplotlib.pyplot as plt

fig, ax = plt.subplots(2, sharex=True, sharey=True)         # Prepare 2 plots
ax[0].set_title('Raw nodes')
ax[1].set_title('Optimized tour')
ax[0].scatter(positions[:, 0], positions[:, 1])             # plot A
ax[1].scatter(positions[:, 0], positions[:, 1])             # plot B
start_node = 0
distance = 0.
for i in range(N):
    start_pos = positions[start_node]
    next_node = np.argmax(x_sol[start_node]) # needed because of MIP-approach used for TSP
    end_pos = positions[next_node]
    ax[1].annotate("",
            xy=start_pos, xycoords='data',
            xytext=end_pos, textcoords='data',
            arrowprops=dict(arrowstyle="->",
                            connectionstyle="arc3"))
    distance += np.linalg.norm(end_pos - start_pos)
    start_node = next_node

textstr = "N nodes: %d\nTotal length: %.3f" % (N, distance)
props = dict(boxstyle='round', facecolor='wheat', alpha=0.5)
ax[1].text(0.05, 0.95, textstr, transform=ax[1].transAxes, fontsize=14, # Textbox
        verticalalignment='top', bbox=props)

plt.tight_layout()
plt.show()

输出:

此代码基于以下形式的数据:

形状为(n_points, n_dimension)的二维数组positions，例如:

[[  4.17022005e-01   7.20324493e-01]
 [  1.14374817e-04   3.02332573e-01]
 [  1.46755891e-01   9.23385948e-02]
 [  1.86260211e-01   3.45560727e-01]
 [  3.96767474e-01   5.38816734e-01]]

二维数组 x_sol 是我们的 MIP 解决方案标记 ~1 当节点 x 后跟 y 在我们的解决方案之旅中，例如:

[[  0.00000000e+00   1.00000000e+00  -3.01195977e-11   2.00760084e-11
    2.41495095e-11]
 [ -2.32741108e-11   1.00000000e+00   1.00000000e+00   5.31351363e-12
   -6.12644932e-12]
 [  1.18655962e-11   6.52816609e-12   0.00000000e+00   1.00000000e+00
    1.42473796e-11]
 [ -4.19937042e-12   3.40039727e-11   2.47921345e-12   0.00000000e+00
    1.00000000e+00]
 [  1.00000000e+00  -2.65096995e-11   3.55630808e-12   7.24755899e-12
    1.00000000e+00]]

更大的例子，用 MIP-gap = 5% 解决；意思是:解决方案保证最多比最优方案差 5%(可以在右侧看到次优部分，其中发生了一些交叉):

完整的代码，包括伪造的 TSP 数据和解决可用的 here 。