何をするのか

予約がいっぱいの繁盛レストランのオーナーから、売上を最大化して欲しいと頼まれました。
1日分の予約候補に対し、どれをOKにして、どれをキャンセルにするかを求めることにします。
このような問題も組合せ最適化で解くことができます。

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

	開始時刻	予約時間	人数	単価
0	13	2	2	2000
1	11	1	3	2800
2	16	3	3	2800
...	...	...	...	...

座席について

レストランの座席は、2人テーブル×4 と4人テーブル×2の16人まで座れます。

また、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]

定式化

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

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

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

Pythonで解く

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

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 # テーブルグループ数、時刻数

定式化して解きます。

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万強ですね。成立した予約を表示します。

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]

以上

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

何をするのか

座席について

定式化

Pythonで解く