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.

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

vrp.png

python


# pandas.DataFrame
from ortoolpy.optimization import Vrp
Vrp('data/node1.csv','data/edge1.csv',2,3)
car num node1 node2 cost
0 0 0 0 3 10
1 0 1 0 2 10
2 0 2 3 5 1
3 0 3 5 2 1
4 1 0 0 4 10
5 1 1 0 1 10
6 1 2 4 1 1

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.

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

Recommended Posts

Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de combinaison - problème typique d'allocation généralisé
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Problème de voie de livraison de lait Codeiq
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Optimisation de la combinaison - problème typique - problème de débit maximal
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème de correspondance typique de problème-poids par optimisation de combinaison
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Problème de fractionnement typique de la combinaison de problèmes
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Utiliser l'optimisation des combinaisons
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
Optimisation du regroupement par combinaison
Problème d'optimisation de la combinaison - coupe minimale