[PYTHON] Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)

Problème typique et méthode d'exécution

Problème d'itinéraire de transport (optimisation de la livraison)

Un ensemble de clients $ V = \ {0, 1, \ dots, n \} $ (où $ 0 $ représente le dépôt qui est le point de départ de l'itinéraire) et un ensemble de transporteurs $ M = \ {1, \ dots , m \} $ est donné. Chaque transporteur quitte le dépôt, livre autour de l'ensemble client attribué et retourne au dépôt. Pour chaque client $ i \ en V $, la demande de service est $ a_i (\ ge 0) $, la capacité de charge maximale de chaque transporteur $ k \ en M $ est $ u (\ ge 0) $, et le client $ Le coût du déplacement entre i $ et le client $ j $ est $ c_ {ij} (\ ge 0) $. On suppose que la demande de chaque client peut être satisfaite en une seule visite. Trouvez des itinéraires pour tous les transporteurs afin de minimiser les coûts de voyage.

• Également appelé VRP (Vehicle Routing Problem). ―― L'optimisation de la livraison est souvent appelée plan XX comme plan de livraison, mais le plan XX est l'ancien nom.

Méthode d'exécution

usage

Signature: vrp(g, nv, capa, demand='demand', cost='cost', method=None)
Docstring:
Problème d'itinéraire de transport
contribution
    g:Graphique(node:demand, edge:cost)
    nv:Nombre de véhicules
    capa:Capacité de transport
    demand:Caractère d'attribut de demande
    cost:Caractère d'attribut de dépense
    method:Méthode de calcul(ex. 'ortools')
production
Liste des paires d'apex pour chaque porteur

python

#Données CSV
import pandas as pd, networkx as nx
from ortoolpy import vrp, graph_from_table, networkx_draw
tbn = pd.read_csv('data/node1.csv')
tbe = pd.read_csv('data/edge1.csv')
g = graph_from_table(tbn, tbe)[0].to_directed()
networkx_draw(g)
nv, capa = 2, 3 #Nombre de véhicules, capacité du véhicule
print(vrp(g, nv, capa))

résultat

[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

python

# pandas.DataFrame
from ortoolpy.optimization import Vrp
Vrp('data/node1.csv','data/edge1.csv',2,3)

python

#Exemple de données
import networkx as nx
from ortoolpy import vrp
nc, nv, capa = 5, 2, 3 #Nombre de clients, nombre de véhicules, capacité du véhicule
g = nx.DiGraph()
g.add_node(0, demand=0)
g.add_nodes_from(range(1, nc + 1), demand=1)
g.add_edges_from([(0, i) for i in range(1, nc + 1)], cost=10)
g.add_edges_from([(i, 0) for i in range(1, nc + 1)], cost=10)
for i, j, t in ((1, 3, 16), (3, 5, 1), (5, 2, 1), (2, 4, 18), (4, 1, 1)):
    g.add_edge(i, j, cost=t)
    g.add_edge(j, i, cost=t)
print(vrp(g, nv, capa))

résultat

[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

Comment utiliser le solveur Google OR-Tools

Si " method = 'ortools' "est ajouté, le solveur (solution approximative) de Google OR-Tools est utilisé.

Mise en garde

--Installez Google OR-Tools avec pip install or tools.

• Le coût doit être un entier.

python

print(vrp(g, nv, capa, method='ortools'))

résultat

[[(0, 1), (1, 4), (4, 0)], [(0, 2), (2, 5), (5, 3), (3, 0)]]

Les données

• data/node1.csv
• data/edge1.csv