[PYTHON] Ambulance placement problem --From the October issue of the OR magazine

what is this

OR Society October issue of the journal ["** Students' OR **" special feature](http://www.orsj.or.jp/ From e-library / elcorsj.html # 6110), I would like to pick up the optimization problem appropriately and solve it with Python. As a preparation, you need pandas, pulp, ortoolpy. [Use combinatorial optimization](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%] Please refer to E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Ambulance placement problem

Let me use the problem of the paper "Designing an effective method using genetic programming for the ambulance relocation problem" Let's get it. In the paper, it is an ambulance relocation problem, but here we will focus on the ambulance placement problem.

Place ambulances in multiple areas. The capacity and demand that can be allocated are determined for each region. Also, the movement must be within 10 minutes. At this time, minimize the total travel time.

Way of thinking

[p-Median Problem](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) So let's solve it quickly.

Solve with Python

First, create random data.

python

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

n = 3 #Number of regions
rn = range(n)
np.random.seed(2)
tm = (np.random.rand(n, n) * 20).round(0)
tm[np.diag_indices(n)] = 0
tm #Travel time(Minutes)
>>>
array([[  0.,   1.,  11.],
       [  9.,   0.,   7.],
       [  4.,  12.,   0.]])

python

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

python

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

Create a variable table. At this time, do not create variables with a travel time of 10 minutes or more.

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]

Let's formulate and solve it.

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]

that's all