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

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]

c'est tout