À propos du problème du vendeur de patrouille commandé

Avez-vous déjà entendu parler du problème du voyageur de commerce? C'est un problème pour trouver le circuit qui minimise la longueur de chemin parmi les circuits qui peuvent tracer le graphe avec un seul trait.

Cette fois, je voudrais traiter d'un ** problème de commande séquentielle ** spécial parmi les problèmes de voyageur de commerce. (Je ne trouve pas de traduction en japonais, je l'ai donc nommée de manière appropriée, donc si quelqu'un la connaît, faites-le moi savoir.)

Ce qui est différent du problème original du voyageur de commerce, c'est qu'il existe une contrainte de commande selon laquelle "ce point doit aller après ce point". Cela permet d'envisager des situations telles que «remettre les bagages reçus de Monsieur A à Monsieur B».

Cette fois, nous traiterons de la formulation et des résultats d'expérimentation numériques en utilisant la conception entière du problème d'ordre séquentiel.

Tout d'abord, préparez les symboles et les constantes.

V :Ensemble de points, |V| := n \\
ss \in V :point de départ\\ 
E :Ensemble de branche\\
c_{ij} ((v_i,v_j)\in E) :branche(v_i,v_j)Coût pour passer\\
\mathcal{S} = \{[v_i,v_j], \cdots\} :Un ensemble avec une liste de deux points qui doivent être en ordre

Ensuite, définissez les variables.

x_{ij} = 
\begin{cases}
    1 &branche(v_i,v_j)Au passage\\
    0 & otherwise
  \end{cases}\\
1\le u_{i} \le n-1 :Point v_Commander via i

Passons maintenant à la formulation. La signification de chaque contrainte détaillée sera ajoutée ultérieurement.

\begin{eqnarray}
{minimize}& \sum_{(v_i,v_j)\in E}c_{ij}x_{ij} \\
subject \ to & \ \sum_{i} x_{ij} = 1 (\forall j) \\
&\sum_{j} x_{ij} = 1 (\forall i)\\
&u_i - u_j + (n-1)x_{ij} \le n-2 \ (\forall j \in S \setminus \{ss\}) \\
&u_{ss} = 0 \\
&u_{i} + 1 \le u_j \ (\forall (v_i,v_j) \in \mathcal{S})
\end{eqnarray}

Ceci est un exemple de mise en œuvre. J'ai fait un graphique aléatoire et j'ai expérimenté.

sop.py


import pulp
import random
import networkx as nx
import math,time
import matplotlib.pyplot as plt

def make_random_graph(n):
    G = nx.DiGraph()
    for i in range(n):
        G.add_node(i,x=random.randint(0,10),y=random.randint(0,10))
    for i in range(n):
        for j in range(n):
            if i != j:
                dist = math.sqrt((G.nodes()[i]['x']-G.nodes()[j]['x'])**2 + (G.nodes()[i]['y']-G.nodes()[j]['y'])**2)
                G.add_edge(i,j,dist=dist)
    return G

def get_random_sequential_order(num_node,m):
    box = set()
    while len(box) < m:
        i = random.randint(0,num_node-2)
        j = random.randint(i+1,num_node-1)
        if (i,j) not in box:
            box.add((i,j))
    return box

def solve_SOP(G,precedense,num_node,ss):
    problem = pulp.LpProblem(name='SOP',sense=pulp.LpMinimize)
    x = {(i,j):pulp.LpVariable(cat="Binary",name=f"x_{i}_{j}") for (i,j) in G.edges()}
    u = {i:pulp.LpVariable(cat="Integer",name=f"u_{i}",lowBound=1,upBound=num_node-1) for i in G.nodes()}
    cost = {(i,j):G.adj[i][j]['dist'] for (i,j) in G.edges()}

    problem += pulp.lpSum([x[(i,j)]*cost[(i,j)] for (i,j) in G.edges()])


    for i in G.nodes():
        problem.addConstraint(pulp.lpSum([x[(i,j)] for j in range(num_node) if j != i]) == 1, f'outflow_{i}')
        problem.addConstraint(pulp.lpSum([x[(j,i)] for j in range(num_node) if j != i]) == 1, f'inflow_{i}')

    for i,j in G.edges():
        if i != ss and j != ss:
            problem.addConstraint(u[i]-u[j]+(num_node-1)*x[i,j] <= num_node-2, f'up_{i}_{j}')

    for i,j in precedense:
        problem.addConstraint(u[i]+1 <= u[j], f'sequential_{i}_{j}')

    u[ss] = 0

    print('start solving')
    start = time.time()
    status = problem.solve(pulp.CPLEX())
    # status = problem.solve()
    print(pulp.LpStatus[status])

    print(time.time()-start)

    if pulp.LpStatus[status] != 'Optimal':
        print('Infeasible!')
        exit()

    return x,u

def plot(G,x,u,precedense,ss):
    pos = {i: (G.nodes()[i]['x'], G.nodes()[i]['y']) for i in G.nodes()}
    nx.draw_networkx_nodes(G, pos, node_size=100, alpha=1, node_color='skyblue')
    edgelist = [e for e in G.edges() if x[e].value() > 0]
    nx.draw_networkx_edges(G, pos, edgelist=edgelist,width=3)
    precedense = [e for e in precedense]
    nx.draw_networkx_edges(G, pos, edgelist=precedense,edge_color='red')
    for i in G.nodes():
        if i != ss:
            plt.text(G.nodes()[i]['x'],G.nodes()[i]['y'],int(u[i].value()))
        else:
            plt.text(G.nodes()[i]['x'],G.nodes()[i]['y'],u[i])


    plt.show()

def main():
    num_node = 10
    num_precedence = 5
    ss = 0
    precedense = get_random_sequential_order(num_node,num_precedence)
    print(precedense)
    G = make_random_graph(num_node)
    x,u = solve_SOP(G,precedense,num_node,ss)
    plot(G,x,u,precedense,ss)

if __name__ == '__main__':
    main()

C'est le résultat de l'exécution avec 10 points. Figure_1.png

La flèche noire indique l'ordre du circuit et la flèche rouge indique l'ordre préféré. Au fur et à mesure que le nombre de points augmente, le temps de calcul augmente de manière exponentielle, il semble donc être strict dans la méthode de limitation de branche qui trouve la solution exacte de la méthode de programmation entière. Par conséquent, des solutions similaires au problème initial du voyageur de commerce ont été proposées.

Recommended Posts

À propos du problème du vendeur de patrouille commandé
À propos du problème du voyageur de commerce
Python: j'ai essayé le problème du voyageur de commerce
Résolvez le problème du voyageur de commerce avec OR-Tools
J'ai essayé de mettre en œuvre le problème du voyageur de commerce
Pensez au problème de changement minimum
Problème de méthode de gravure et de voyageur de commerce
J'ai essayé le problème de campagne de Paiza. (Problème de vendeur circulaire)
À propos du test
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
À propos de la file d'attente
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (code Python)
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
Résolution du problème du voyageur de commerce avec l'algorithme génétique (GA) et sa bibliothèque (vcopt)
Résolvez le problème du voyageur de commerce asymétrique Python avec la méthode de branche et de liaison
À propos de la fonction Déplier
À propos de la commande de service
À propos de la matrice de confusion
À propos du modèle de visiteur
Examiner le double problème
Une histoire sur la façon de traiter le problème CORS
À propos du module Python venv
À propos de la fonction enumerate (python)
À propos de la compréhension du lecteur en 3 points [...]
À propos des composants de Luigi
À propos des fonctionnalités de Python
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"
Une histoire dans laquelle l'algorithme est arrivé à une conclusion ridicule en essayant de résoudre correctement le problème du voyageur de commerce