Problème de placement d'ambulance - Tiré du numéro d'octobre du magazine OR

Qu'est-ce que c'est

OR Society Numéro d'octobre de la revue [Dossier spécial "** Students 'OR **"](http://www.orsj.or.jp/ De e-library / elcorsj.html # 6110), je voudrais aborder le problème d'optimisation de manière appropriée et le résoudre avec Python. Comme préparation, vous avez besoin de pandas, de pulpe, d'oolpy. Pour la construction de l'environnement, [Utiliser l'optimisation des combinaisons](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88% Veuillez vous référer à E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Problème de placement d'ambulance

Permettez-moi d'utiliser le problème de l'article "Concevoir une méthode efficace utilisant la programmation génétique pour le problème de la relocalisation des ambulances" Allons s'en approprier. Dans l'article, il s'agit d'un problème de relocalisation d'ambulances, mais ici nous allons nous concentrer sur le problème de placement d'ambulances.

Placez les ambulances dans plusieurs zones. La capacité et la demande pouvant être allouées sont déterminées pour chaque région. En outre, le mouvement doit être dans les 10 minutes. À ce stade, réduisez le temps de trajet total.

Façon de penser

[Problème p-médian](http://www.orsj.or.jp/~wiki/wiki/index.php/P-%E3%83%A1%E3%83%87%E3%82%A3%E3 % 82% A2% E3% 83% B3% E5% 95% 8F% E9% A1% 8C) Alors résolvons-le rapidement.

Résoudre avec Python

Tout d'abord, créez des données aléatoires.

python


import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvar, addvars

n = 3 #Nombre de régions
rn = range(n)
np.random.seed(2)
tm = (np.random.rand(n, n) * 20).round(0)
tm[np.diag_indices(n)] = 0
tm #Temps de voyage(Minutes)
>>>
array([[  0.,   1.,  11.],
       [  9.,   0.,   7.],
       [  4.,  12.,   0.]])

python


cap = np.random.randint(2, 5, n)
cap #capacité
>>>
array([4, 2, 2])

python


dem = np.random.randint(2, 4, n)
dem #demande
>>>
array([2, 3, 3])

Créez une table de variables. À ce stade, ne créez pas de variables avec un temps de trajet de 10 minutes ou plus.

python


a = pd.DataFrame(((i,j,dist[i,j]) for i in rn for j in rn
        if dist[i,j]<=10), columns=['From', 'To', 'Tm'])
a['Var'] = addvars(len(a))
a[:3]
From To Tm Var
0 0 0 0.0 v1
1 0 1 1.0 v2
2 1 0 9.0 v3

Formulons et résolvons-le.

python


m = LpProblem()
m += lpDot(a.Tm, a.Var)
for i, t in a.groupby('From'):
    m += lpSum(t.Var) <= cap[i]
for i, t in a.groupby('To'):
    m += lpSum(t.Var) >= dem[i]
m.solve()
a['Val'] = a.Var.apply(value)
a[a.Val > 0]
From To Tm Var Val
0 0 0 0.0 v1 2.0
1 0 1 1.0 v2 2.0
3 1 1 0.0 v4 1.0
4 1 2 7.0 v5 1.0
6 2 2 0.0 v7 2.0

c'est tout

Recommended Posts

Problème de placement d'ambulance - Tiré du numéro d'octobre du magazine OR
Plan de mesure optimal - Extrait du numéro d'octobre du magazine OR
Food Desert Problem - Extrait du numéro d'octobre du magazine OR
Optimisation des stratégies d'embarquement pour les avions - du numéro d'octobre du magazine OR
Existence du point de vue de Python
Illustration des résultats du problème du sac à dos
Notes d'apprentissage depuis le début de Python 1
Omettre la nomenclature depuis le début de la chaîne
Modèle de conception du GoF à partir du problème 1. Génération
Notes d'apprentissage depuis le début de Python 2
Modèle de conception GoF à partir du problème 3. Comportement
Méthode Dyxtra: j'ai posé le problème d'AOJ avec Python en me basant sur le contenu de l'article de M. Kencho dans le numéro d'octobre de Software Design