[PYTHON] Résolution du problème d'itinéraire de transport (VRP) Planification d'entiers mixtes
Après avoir étudié des problèmes célèbres liés à la logistique, je pense que je vais les résoudre avec python. Donc, pour la première fois, je vais essayer de résoudre le problème de l'itinéraire de transport par la méthode de programmation entière.
Quel est le problème de l'itinéraire de transport?
Nom anglais Vehicle Routing Problem (VRP). [Problème d'itinéraire de transport ORWiki](http://www.orsj.or.jp/~wiki/wiki/index.php/%E9%81%8B%E6%90%AC%E7%B5%8C%E8%B7 % AF% E5% 95% 8F% E9% A1% 8C) a une explication détaillée. Pour faire simple, il s'agit de trouver le coût minimum pour répondre aux demandes de plusieurs clients en utilisant un transporteur appartenant à une base appelée dépôt. Si c'est difficile à comprendre, vous pouvez penser à faire un plan pour minimiser la distance totale de trajet en camion de Yamato Takkyubin. (Désolé, dans leur cas, il y a une nouvelle livraison en raison de leur absence, il est donc extrêmement difficile de le mettre dans un problème mathématique, ou c'est impossible.) Toutes les entreprises de livraison visent à introduire des systèmes dans le but d'automatiser, mais l'automatisation complète est assez difficile. En effet, il y a des changements de commande soudains et des produits dont la taille est inconnue. L'impression que la plupart des entreprises sont créées par des artisans sous Excel.
Type de problème
- Dans VRP, les problèmes sont classés en fonction de la présence ou de l'absence des conditions suivantes. Le logiciel du marché répond à la plupart des restrictions. Cette fois, seule la capacité de la voie est considérée comme une contrainte.
- PickUP and Delivery（VRPPD) --Plusieurs zones de chargement. Pas un seul dépôt.
- LIFO
- Restrictions post-entrée / premier sorti. Il est difficile de retirer les bagages chargés à l'arrière du camion et de retirer les bagages à l'avant. Important dans le plan de transport actuel.
- Délai (VRPTW)
- Restrictions de délai de livraison souhaitées pour chaque client.
- Capacité de piste (CVRP)
- La piste a des contraintes de capacité
Formulation
Puisque VRP est difficile à NP, les logiciels commerciaux utilisent la méthode de solution heuristique. Après avoir étudié cette fois, je vais le résoudre avec MIP (Mixed Integer Program). L'explication est dans la source. Je suis désolé d'être hostile. J'utilise une bibliothèque appelée pulp, mais si vous ne la connaissez pas, je lierai l'article suivant pour ceux qui ne sont pas familiers avec l'utilisation de pulp. Introduction à la résolution de problèmes de planification linéaire avec PuLP Au fait, cette fois, j'ai implémenté la version étendue de DFJ introduite dans le Wiki anglais de VRP.
La source
CVRPwithMIP.py
import pulp
import pandas as pd
import numpy as np
import networkx as nx
import itertools
import matplotlib.pyplot as plt
num_client = 15 #Nombre de clients (id=0,1,2,...Je pense qu'il porte le numéro 14. id=0 est le dépôt. )
capacity = 50 #Capacité de piste
randint = np.random.randint
seed = 10
#X pour chaque client,Créez des coordonnées y et demandez (combien de produits vous voulez) en tant que DataFrame
df = pd.DataFrame({"x":randint(0,100,num_client),
"y":randint(0,100,num_client),
"d":randint(5,40,num_client)})
#Le 0ème client est considéré comme un dépôt (base). Alors demande=0,Venir au centre au moment de la visualisation
#x,y à 50.
df.ix[0].x = 50
df.ix[0].y = 50
df.ix[0].d = 0
#Le coût est le nombre de clients ✖️ Tableau des distances du nombre de clients. np.Tenez dans le tableau.
cost = create_cost()
#subtours est un dépôt (id=0)Un ensemble complet de clients sauf. Je verrai ce que cela aide plus tard.
subtours = []
for length in range(2,num_client):
subtours += itertools.combinations(range(1,num_client),length)
#x est le nombre de clients ✖️ variable binaire Tableau du nombre de clients. Correspond à la table des coûts. S'il vaut 1, la piste passera entre eux.
# num_v est la variable du nombre requis de pistes.
x = np.array([[pulp.LpVariable("{0}_{1}".format(i,j),0,1,"Binary")
for j in range(num_client)]
for i in range(num_client)])
num_v = pulp.LpVariable("num_v",0,100,"Integer")
#Déclaration du problème et paramétrage de la fonction objectif. La fonction objective est de minimiser la distance totale.
problem = pulp.LpProblem('vrp_simple_problem', pulp.LpMinimize)
problem += pulp.lpSum([x[i][j]*cost[i][j]
for i in range(num_client)
for j in range(num_client)])
#Exclus car il n'y a pas de possibilité de passer du client 1 au client 1
for t in range(num_client):
problem += x[t][t] == 0
#Il y a toujours un arc (piste) sortant et un arc (piste) venant du client.
for t in range(1,num_client):
problem += pulp.lpSum(x[:,t]) == 1
problem += pulp.lpSum(x[t,:]) == 1
#Dépôt (ici id=0)Le nombre d'arcs entrants (pistes) et sortants (pistes) est toujours le même.
problem += pulp.lpSum(x[:,0]) == num_v
problem += pulp.lpSum(x[0,:]) == num_v
#C'est le foie. Avec les restrictions ci-dessus, une route fermée isolée qui ne retourne pas au dépôt sera créée. Ce que nous faisons ici
#subtour éliminer la contrainte. Nous examinons également la demande et ajoutons ici une contrainte de capacité. être intéressé
#Si vous êtes intéressé, veuillez rechercher l'élimination des sous-niveaux.
for st in subtours:
arcs = []
demand = 0
for s in st:
demand += df_dpsts["d"][s]
for i,j in itertools.permutations(st,2):
arcs.append(x[i][j])
print(len(st) - np.max([0,np.ceil(demand/capacity)]))
problem += pulp.lpSum(arcs) <= np.max([0,len(st) - np.ceil(demand/capacity)])
#Calcul et confirmation des résultats
status = problem.solve()
print("Status", pulp.LpStatus[status])
for i in range(num_client):
for j in range(num_client):
print(i,j,x[i][j].value())
output_image(G,x)
Visualisation
Visualisation de la solution. Le point bleu est le dépôt et le point rouge est le client (les chiffres sont demandés)
Il s'avère que cinq camions sont nécessaires. Notez que la demande totale pour chaque route fermée ne dépasse pas la capacité du camion (= 50).
Conclusion
Résolu! La formulation ci-dessus ne peut être résolue si le nombre de clients augmente un peu, notamment parce que le nombre de restrictions sur l'élimination de Subtour augmente de manière explosive avec le nombre de clients. Il y a quelques idées ici, mais je ne les présenterai pas cette fois. La prochaine fois, j'écrirai une méthode heuristique (pas une solution exacte, mais une bonne solution).
Recommended Posts