[PYTHON] Décidons la position du service d'incendie par optimisation combinée

problème

Vous êtes le nouveau maire de la ville A. J'ai décidé de construire trois nouveaux services d'incendie. Où dois-je le construire? (Cette histoire est de la fiction)

Façon de penser 1

Considérez-le comme un problème de placement d'installation sans restrictions de capacité. On suppose que l'emplacement du ménage du citoyen est connu. Décidez de minimiser la distance totale entre chaque foyer et l'emplacement du service d'incendie le plus proche.

Résoudre avec Python

Tout d'abord, déterminez la position du ménage au hasard.

python

%matplotlib inline
import numpy as np, pandas as pd, matplotlib.pyplot as plt
from ortoolpy import facility_location_without_capacity
np.random.seed(1)

Nombre de ménages,Nombre de services d'incendie= 100,3
Position du ménage= np.random.rand(Nombre de ménages,2)
plt.scatter(*Position du ménage.T);

J'essaierai de le résoudre.

python

Résultat 1= facility_location_without_capacity(Nombre de services d'incendie,Position du ménage)
np.unique(Résultat 1)
>>>
array([ 9, 62, 77])

J'ai trouvé qu'il serait préférable de le construire aux 9e, 62e et 77e postes du ménage. Visualiser.

python

Poste d'incendie 1=Position du ménage[np.unique(Résultat 1)]
plt.scatter(*Position du ménage.T)
plt.scatter(*Poste d'incendie 1.T);

Regardons la distribution des distances pour chaque ménage. La ligne médiane est la moyenne.

python

Distance 1= np.linalg.norm(Position du ménage-Position du ménage[Résultat 1], axis=1)
plt.hist(Distance 1, range=(0,0.6), bins=20, alpha=0.5)
plt.vlines(Distance 1.mean(), 0, 20);

Pensée 2

Avec la distance totale, les personnes éloignées et proches seront décalées. Essayez de réduire le plus possible le nombre de personnes éloignées. Ici, nous minimisons la somme des carrés des distances.

python

Résultat 2= facility_location_without_capacity(Nombre de services d'incendie,Position du ménage,
    func = lambda i,j: (Position du ménage[i][0]-Position du ménage[j][0])**2+(Position du ménage[i][1]-Position du ménage[j][1])**2)
np.unique(Résultat 2)
>>>
array([37, 39, 73])

C'est un endroit différent. Si vous créez un modèle mathématique avec PuLP, ce sera comme suit. (Même résultat)

python

from pulp import *
from ortoolpy import addbinvars, addvars
r = range(len(Position du ménage))
m = LpProblem()
x = addvars(len(Position du ménage), len(Position du ménage))
y = addbinvars(len(Position du ménage))
m += lpSum(((Position du ménage[i][0]-Position du ménage[j][0])**2+(Position du ménage[i][1]-Position du ménage[j][1])**2) * x[i][j]
           for i in r for j in r)
m += lpSum(y) <=Nombre de services d'incendie
for i in r:
    m += lpSum(x[i]) == 1
    for j in r:
        m += x[i][j] <= y[j]
m.solve()
Résultat 2= [int(value(lpDot(r, x[i]))) for i in r]

Visualiser.

python

Poste d'incendie 2=Position du ménage[np.unique(Résultat 2)]
plt.scatter(*Position du ménage.T)
plt.scatter(*Poste d'incendie 1.T)
plt.scatter(*Poste d'incendie 2.T);

On a l'impression de se rapprocher du centre. Comparons les distributions.

python

Distance 2= np.linalg.norm(Position du ménage-Position du ménage[Résultat 2], axis=1)
plt.hist(Distance 1, range=(0,0.6), bins=20, alpha=0.5)
plt.vlines(Distance 1.mean(), 0, 20)
plt.hist(Distance 2, range=(0,0.6), bins=20, alpha=0.5)
plt.vlines(Distance 2.mean(), 0, 20)
print('moyenne',Distance 1.mean(),Distance 2.mean())
print('Distribué',Distance 1.var(),Distance 2.var())
>>>
Moyenne 0.235140814776 0.237069972634
Répartition 0.0138310436529 0.0100843497562

Vous pouvez voir que la moyenne a légèrement augmenté, mais la variabilité a diminué et le nombre de personnes éloignées a diminué.

Pensée 3

Essayez de minimiser vos attentes, avec 90% de chances d'arriver à l'endroit le plus proche et 10% de chances d'arriver au deuxième endroit le plus proche. C'est OK si vous préparez les variables pour la première et la seconde et ne sélectionnez pas la première et la seconde en même temps.

python

m = LpProblem()
x1 = np.array(addvars(len(Position du ménage), len(Position du ménage))) #Service d'incendie le plus proche
x2 = np.array(addvars(len(Position du ménage), len(Position du ménage))) #Deuxième service d'incendie le plus proche
y  = addbinvars(len(Position du ménage))
m += lpSum(((Position du ménage[i][0]-Position du ménage[j][0])**2+(Position du ménage[i][1]-Position du ménage[j][1])**2) * x1[i,j] * 0.9
          +((Position du ménage[i][0]-Position du ménage[j][0])**2+(Position du ménage[i][1]-Position du ménage[j][1])**2) * x2[i,j] * 0.1
           for i in r for j in r)
m += lpSum(y) <=Nombre de services d'incendie
for i in r:
    m += lpSum(x1[i]) == 1
    m += lpSum(x2[i]) == 1
    for j in r:
        m += x1[i,j] + x2[i,j] <= y[j]
m.solve()
Résultat 3= [int(value(lpDot(r, x1[i]))) for i in r]
np.unique(Résultat 3)
>>>
array([37, 39, 93])

Visualisons-le. Cela a un peu changé.

python

Poste d'incendie 3=Position du ménage[np.unique(Résultat 3)]
for i in [Position du ménage,Poste d'incendie 1,Poste d'incendie 2,Poste d'incendie 3]:
    plt.scatter(*i.T)

c'est tout