Création de graphiques pour les instances euclidiennes de TSP

Question

Je travaille actuellement sur la recherche centrée autour du problème des vendeurs itinérants. Plus précisément, je travaille avec des données d'échantillons en utilisant le type de poids de bord EUC_2D. Comme le suivant:

1 11003.611100 42102.500000 
2 11108.611100 42373.888900 
3 11133.333300 42885.833300 

Je suis capable de produire un ordre de tour. Par exemple, 2-3-1. Je voudrais être capable de créer des graphiques simples qui représentent un ensemble de points pour un problème donné, puis un ensemble de points avec un tour par-dessus. Quelqu'un pourrait-il recommander une méthode simple pour y parvenir - quel logiciel dois-je regarder pour y parvenir.

Merci

Answer 1

Juste pour vous donner une démonstration rapide sur la façon dont les Traçage outils scientifiques habituels travailleraient (en supposant que je compris votre tâche):

terrain uniquement code en utilisant 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() 

sortie:

Ce code est basé sur les données de la suite f orm:

A 2d-réseau positions de forme (n_points, n_dimension) comme:

[[ 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]] 

A 2d-réseau x_sol qui est notre marquage MIP-solution ~1 lorsque le noeud x est suivie par y dans notre solution-tour, comme :

[[ 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]] 

Agrandir exemple, résolu avec MIP-gap = 5%; ce qui signifie: la solution est garantie au plus 5% pire que l'optimum (on pourrait voir la partie sous-optimale dans le droit où des croisements se passe):

Code complet comprenant TSP faux données et résolution disponibles here.

Answer 2

Je vais recommander bébé X. (Il est mon propre système de fenêtrage).

C'est un système Windows qui fonctionne sous Linux ou MS Windows, et qui est conçu pour ce type de problème - en prototypant rapidement un programme avec quelques graphiques simples.

Bébé X expose les surfaces RVB. Vous dessinez ensuite dans le tampon, soit en utilisant vos propres routines, les routines de base Baby X (lignes et polygones), ou le contexte graphique Baby X (graphiques 2D à base de Bézier à part entière). C'est très rapide à mettre en place. Vous devrez évidemment mettre votre graphique à l'échelle de l'espace des pixels, tracer des symboles pour les villes, puis tracer des lignes entre eux pour représenter la visite.

https://github.com/MalcolmMcLean/babyx

Cependant, il existe plusieurs systèmes graphiques là-bas. Vous avez juste à choisir celui qui fonctionne sur votre plate-forme matérielle.