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]
From To Tm Var
0 0 0 0.0 v1
1 0 1 1.0 v2
2 1 0 9.0 v3

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

that's all

Recommended Posts

Ambulance placement problem --From the October issue of the OR magazine
Optimal measurement plan --From the October issue of the OR magazine
Food Desert Problem-From the October issue of the OR magazine
Optimizing boarding strategies for aircraft-from the October issue of the OR bulletin
Existence from the viewpoint of Python
Illustration of the results of the knapsack problem
Learning notes from the beginning of Python 1
Omit BOM from the beginning of the string
GoF design pattern from the problem 1. Generation
Learning notes from the beginning of Python 2
GoF design pattern from the problem 3. Behavior
Dijkstra's algorithm: I asked the problem of AOJ in Python based on the content of Kencho-san's article in the October issue of Software Design.