レストランの売上を組合せ最適化で最大化する

# <i class='fa fa-beer' /> 何をするのか
予約がいっぱいの繁盛レストランのオーナーから、**売上を最大化して欲しい**と頼まれました。
1日分の予約候補に対し、どれをOKにして、どれをキャンセルにするかを求めることにします。
このような問題も[組合せ最適化](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721)で解くことができます。

予約は、下記のように時間と人数と単価がわかっているものとします。
1行が1つの予約に対応し、[開始時刻]に[人数]だけ来店し、[予約時間]の時間をかけて食事して、[単価]×[人数]払って帰るものとします。

<table>
<tr><td></td><td>開始時刻</td><td>予約時間</td><td>人数</td><td>単価</td></tr>
<tr><td>0</td><td>13</td><td>2</td><td>2</td><td>2000</td></tr>
<tr><td>1</td><td>11</td><td>1</td><td>3</td><td>2800</td></tr>
<tr><td>2</td><td>16</td><td>3</td><td>3</td><td>2800</td></tr>
<tr><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td></tr>
</table>

# <i class='fa fa-beer' /> 座席について
レストランの座席は、2人テーブル×4 と4人テーブル×2の16人まで座れます。
![image](https://qiita-image-store.s3.amazonaws.com/0/13955/b2e31934-3d27-f8b8-71d9-3635c798f91c.png)

また、2人テーブル同士と4人テーブル同士は、くっつけて使うこともできます。
くっつけ方(以下テーブルグループとよぶ)は以下の13通りです。(番号はテーブル番号)

    [0]
    [1]
    [2]
    [3]
    [4]
    [5]
    [0, 1]
    [1, 2]
    [2, 3]
    [4, 5]
    [0, 1, 2]
    [1, 2, 3]
    [0, 1, 2, 3]

# <i class='fa fa-beer' /> 定式化

<table>
<tr><td>$\mbox{objective}$</td><td>$\sum_i{\sum_j{人数_i 単価_i x_{ij}}}$</td><td>総売上</td></tr>
<tr><td>$\mbox{variables}$</td><td>$x_{ij} \in \{0, 1\} ~ \forall i, j$</td><td>予約$i$がテーブルグループ$j$を使うかどうか</td></tr>
<tr><td rowspan="4">$\mbox{subject to}$</td><td>$\sum_j{x_{ij}} \le 1 ~ \forall i$</td><td>何れかのテーブルグループ</td></tr>
<tr><td>$テーブルグループjの座席数 \lt 予約iの人数のとき$</td><td rowspan="2">人数制限</td></tr>
<tr><td>$x_{ij} = 0 ~ \forall i, j$</td></tr>
<tr><td colspan="2">同テーブル同時刻には、1組しか予約受入できない</td></tr>
</table>

ただし、添字の意味は下記の通りとします。

    i: 予約
    j: テーブルグループ
    s: テーブル
    t: 時刻

# <i class='fa fa-beer' /> Pythonで解く

まず、予約表(a)を乱数で作成します。

```py3:python
import numpy as np, numpy.random as rnd, pandas as pd, matplotlib.pyplot as plt
from pulp import *
def addvar(lowBound=0, count=[0], *args, **kwargs):
    count[0] += 1
    return LpVariable('v%d' % count[0], lowBound=lowBound, *args, **kwargs)
rnd.seed(5)
a = pd.DataFrame([(rnd.randint(10, 17), rnd.choice([1, 2, 2, 3]),
      max(1, min(8, int(rnd.lognormal(1.2, 0.5)))), rnd.randint(10, 16) * 200)
      for _ in range(60)], columns=['開始時刻', '予約時間', '人数', '単価'])
cap = [2, 2, 2, 2, 4, 4] # テーブル別座席数
sps = [[0], [1], [2], [3], [4], [5], [0, 1], [1, 2], [2, 3],
       [4, 5], [0, 1, 2], [1, 2, 3], [0, 1, 2, 3]] # テーブルグループ別テーブルリスト
ns, nt = len(sps), 19 - 10 # テーブルグループ数、時刻数
```

定式化して解きます。

```py3:python
m = LpProblem(sense=LpMaximize) # 数理モデル
p = [[[] for t in range(nt)] for _ in range(6)] # テーブル別時刻別変数リスト
a['Var'] = [[addvar(cat=LpBinary) for j in range(ns)] for i, r in a.iterrows()]
m += lpDot(a.人数 * a.単価, a.Var.apply(lpSum)) # 目的関数(総売上)
for i, r in a.iterrows():
    m += lpSum(r.Var) <= 1 # 何れかのテーブルグループ
    for j, sp in enumerate(sps):
        if sum(cap[s] for s in sp) < r.人数:
            m += r.Var[j] == 0 # 人数制限
        for s in sp:
            for t in range(r.予約時間):
                p[s][r.開始時刻 - 10 + t].append(r.Var[j])
for s in range(6):
    for t in range(nt):
        if p[s][t]:
            m += lpSum(p[s][t]) <= 1 # 同テーブル同時刻には、1組しか予約受入できない
m.solve()
a['Val'] = a.Var.apply(lambda v: int(value(lpDot(range(1, ns+1), v))))
print('%s %d人 %.2f 万円' % (LpStatus[m.status],
    sum(a[a.Val > 0].人数), value(m.objective) / 10000))
>>>
Optimal 83人 20.44 万円
```

売上は20万強ですね。成立した予約を表示します。

```py3:python
print('時間 人数 料金 テーブル')
for i, r in a.iterrows():
    if r.Val:
        print('%2d-%2d %d %d %s' % (r.開始時刻, r.開始時刻 + r.予約時間 - 1,
                                    r.人数, r.人数 * r.単価, sps[r.Val-1]))
>>>
時間 人数 料金 テーブル
11-11 3 8400 [2, 3]
16-18 3 8400 [5]
13-13 4 11200 [4]
16-17 2 4800 [2]
16-17 4 11200 [4]
12-12 3 7200 [5]
14-15 8 20800 [4, 5]
14-14 2 4800 [2]
10-10 1 3000 [0]
16-18 2 6000 [3]
15-15 8 16000 [0, 1, 2, 3]
11-11 3 8400 [0, 1]
10-10 2 4000 [4]
11-12 4 9600 [4]
16-18 4 8000 [0, 1]
13-13 2 5600 [0]
12-12 6 13200 [1, 2, 3]
10-11 4 8000 [5]
10-10 3 6600 [1, 2]
13-13 4 10400 [5]
13-13 2 6000 [1]
13-13 4 10400 [2, 3]
14-14 2 5200 [3]
14-14 3 7200 [0, 1]
```

以上