[PYTHON] Lassen Sie uns die Position der Feuerwehr durch Kombinationsoptimierung bestimmen

Problem

Sie sind der neue Bürgermeister von Stadt A. Ich beschloss, drei neue Feuerwehren zu bauen. Wo soll ich es bauen? (Diese Geschichte ist Fiktion)

Denkweise 1

Stellen Sie sich das als [Problem bei der Platzierung von Einrichtungen ohne Kapazitätsbeschränkungen] vor (http://qiita.com/SaitoTsutomu/items/0cbd2e9a75ef0ecb3269). Es wird davon ausgegangen, dass der Standort des Bürgerhaushalts bekannt ist. Entscheiden Sie sich dafür, die Gesamtentfernung von jedem Haushalt zum Standort der nächsten Feuerwache zu minimieren.

Löse mit Python

Bestimmen Sie zunächst die Haushaltsposition nach dem Zufallsprinzip.

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)

Anzahl der Haushalte,Anzahl der Feuerwehren= 100,3
Haushaltslage= np.random.rand(Anzahl der Haushalte,2)
plt.scatter(*Haushaltslage.T);

Ich werde versuchen, es zu lösen.

python

Ergebnis 1= facility_location_without_capacity(Anzahl der Feuerwehren,Haushaltslage)
np.unique(Ergebnis 1)
>>>
array([ 9, 62, 77])

Ich fand, dass es besser wäre, es auf der 9., 62. und 77. Haushaltsposition aufzubauen. Visualisieren.

python

Feuerwache Position 1=Haushaltslage[np.unique(Ergebnis 1)]
plt.scatter(*Haushaltslage.T)
plt.scatter(*Feuerwache Position 1.T);

Schauen wir uns die Entfernungsverteilung für jeden Haushalt an. Die Mittellinie ist der Durchschnitt.

python

Entfernung 1= np.linalg.norm(Haushaltslage-Haushaltslage[Ergebnis 1], axis=1)
plt.hist(Entfernung 1, range=(0,0.6), bins=20, alpha=0.5)
plt.vlines(Entfernung 1.mean(), 0, 20);

Denkweise 2

Mit der Gesamtentfernung werden Personen, die weit entfernt sind, und Personen, die nah sind, versetzt. Versuchen Sie, die Anzahl der weit entfernten Personen so weit wie möglich zu reduzieren. Hier wird die Summe der Quadrate der Abstände minimiert.

python

Ergebnis 2= facility_location_without_capacity(Anzahl der Feuerwehren,Haushaltslage,
    func = lambda i,j: (Haushaltslage[i][0]-Haushaltslage[j][0])**2+(Haushaltslage[i][1]-Haushaltslage[j][1])**2)
np.unique(Ergebnis 2)
>>>
array([37, 39, 73])

Es ist ein anderer Ort. Wenn Sie mit PuLP ein mathematisches Modell erstellen, sieht es wie folgt aus. (Gleiches Ergebnis)

python

from pulp import *
from ortoolpy import addbinvars, addvars
r = range(len(Haushaltslage))
m = LpProblem()
x = addvars(len(Haushaltslage), len(Haushaltslage))
y = addbinvars(len(Haushaltslage))
m += lpSum(((Haushaltslage[i][0]-Haushaltslage[j][0])**2+(Haushaltslage[i][1]-Haushaltslage[j][1])**2) * x[i][j]
           for i in r for j in r)
m += lpSum(y) <=Anzahl der Feuerwehren
for i in r:
    m += lpSum(x[i]) == 1
    for j in r:
        m += x[i][j] <= y[j]
m.solve()
Ergebnis 2= [int(value(lpDot(r, x[i]))) for i in r]

Visualisieren.

python

Feuerwache Position 2=Haushaltslage[np.unique(Ergebnis 2)]
plt.scatter(*Haushaltslage.T)
plt.scatter(*Feuerwache Position 1.T)
plt.scatter(*Feuerwache Position 2.T);

Es fühlt sich an, als würde es sich dem Zentrum nähern. Vergleichen wir die Verteilungen.

python

Entfernung 2= np.linalg.norm(Haushaltslage-Haushaltslage[Ergebnis 2], axis=1)
plt.hist(Entfernung 1, range=(0,0.6), bins=20, alpha=0.5)
plt.vlines(Entfernung 1.mean(), 0, 20)
plt.hist(Entfernung 2, range=(0,0.6), bins=20, alpha=0.5)
plt.vlines(Entfernung 2.mean(), 0, 20)
print('durchschnittlich',Entfernung 1.mean(),Entfernung 2.mean())
print('Verteilt',Entfernung 1.var(),Entfernung 2.var())
>>>
Durchschnitt 0.235140814776 0.237069972634
Verteilung 0.0138310436529 0.0100843497562

Sie können sehen, dass der Durchschnitt leicht gestiegen ist, aber die Variabilität abgenommen hat und die Anzahl der weit entfernten Personen abgenommen hat.

Denkweise 3

Versuchen Sie, Ihre Erwartungen zu minimieren, mit einer 90% igen Chance, zum nächstgelegenen Ort zu gelangen, und einer 10% igen Chance, zum zweitnächsten Ort zu gelangen. Es ist in Ordnung, wenn Sie die Variablen für die erste und die zweite vorbereiten und nicht gleichzeitig die erste und die zweite auswählen.

python

m = LpProblem()
x1 = np.array(addvars(len(Haushaltslage), len(Haushaltslage))) #Nächste Feuerwehr
x2 = np.array(addvars(len(Haushaltslage), len(Haushaltslage))) #Zweitnächste Feuerwehr
y  = addbinvars(len(Haushaltslage))
m += lpSum(((Haushaltslage[i][0]-Haushaltslage[j][0])**2+(Haushaltslage[i][1]-Haushaltslage[j][1])**2) * x1[i,j] * 0.9
          +((Haushaltslage[i][0]-Haushaltslage[j][0])**2+(Haushaltslage[i][1]-Haushaltslage[j][1])**2) * x2[i,j] * 0.1
           for i in r for j in r)
m += lpSum(y) <=Anzahl der Feuerwehren
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()
Ergebnis 3= [int(value(lpDot(r, x1[i]))) for i in r]
np.unique(Ergebnis 3)
>>>
array([37, 39, 93])

Lassen Sie es uns visualisieren. Es hat sich ein wenig verändert.

python

Feuerwache Position 3=Haushaltslage[np.unique(Ergebnis 3)]
for i in [Haushaltslage,Feuerwache Position 1,Feuerwache Position 2,Feuerwache Position 3]:
    plt.scatter(*i.T)

das ist alles