为TSP的欧式实例创建图形 [英] Creating graphics for euclidean instances of TSP

问题描述

我目前正在围绕旅行推销员问题"进行研究.更准确地说，我正在使用EUC_2D边缘权重类型处理示例数据.如下所示:

I'm currently working on research centring around the Travelling Salesman Problem. More precisely I'm working with sample data using the EUC_2D edge weight type. Like the following:

1 11003.611100 42102.500000
2 11108.611100 42373.888900
3 11133.333300 42885.833300

我能够制作旅游订单.例如2-3-1.

I am able to produce a tour order. For example, 2-3-1.

我希望能够创建一些简单的图形，这些图形分别表示给定问题的要点集，然后再在顶部进行巡视.任何人都可以推荐一种实现此目标的简单方法-实现该目标我应该看什么软件.

I'd like to be able to create some simple graphics which represent a point set for a given problem, and then a point set with a tour over the top. Could anyone recommend a simple method of achieving this - what software should I be looking at to achieve this.

谢谢

推荐答案

仅向您简要演示常用的科学绘图工具的工作原理(假设我正确理解了您的任务):

Just to give you a quick demo on how the usual scientific plotting-tools would work (assuming i understood your task correctly):

使用python& matplotlib :

Plot-only code using 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()

输出:

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

This code is based on data of the following form:

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

A 2d-array positions of shape (n_points, n_dimension) like:

[[  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时，在我们的解决方案之旅中，例如:

A 2d-array x_sol which is our MIP-solution marking ~1 when node x is followed by y in our solution-tour, like:

[[  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％(可以在右侧看到发生交叉的地方看到次优部分):

Bigger example, solved with MIP-gap = 5%; meaning: the solution is guaranteed to be at most 5% worse than the optimum (one could see the sub-optimal part in the right where some crossing is happening):

完整代码，包括伪造的TSP数据和解决方法，可用此处.

Complete code including fake TSP-data and solving available here.

这篇关于为TSP的欧式实例创建图形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！