[PYTHON] À 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.

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.