[PYTHON] Maximize restaurant sales with combinatorial optimization

What to do

The owner of a thriving restaurant full of reservations asked me to ** maximize sales **. We will ask the candidate reservations for one day which ones are OK and which ones are cancelled. Such problems can also be solved with Combinatorial Optimization (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721).

For reservations, it is assumed that the time, number of people and unit price are known as shown below. It is assumed that one line corresponds to one reservation, visits only [number of people] at [start time], eats over [reservation time], and pays [unit price] x [number of people] to return.

Start time Reservation time Number of people Unit price
013222000
111132800
216332800
...............

About seats

The restaurant seats up to 16 people, 4 tables for 2 people and 2 tables for 4 people. image

You can also use the two-person table and the four-person table together. There are 13 ways to attach them (hereinafter referred to as table groups). (Number is table number)

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

Formulation

$ \ mbox {objective} $ $ \ sum_i {\ sum_j {number of people_i unit price_i x_ {ij}}} $ total sales < / td>
$ \ mbox {variables} $ $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ Reserved $ Whether i $ uses table group $ j $
$ \ mbox {subject to} $ $ \ sum_j {x_ {ij}} \ le 1 ~ \ forall i $ Any table group
$ Number of seats in table group j \ lt When the number of reservation i is $ Number limit
$x_{ij} = 0 ~ \forall i, j$
Only one set can be reserved at the same time at the same table

However, the meaning of the subscript is as follows.

i: Reservation j: table group s: table t: time

Solve with Python

First, create a reservation table (a) with random numbers.

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=['Start time', 'Reservation time', 'Number of people', 'unit price'])
cap = [2, 2, 2, 2, 4, 4] #Number of seats by table
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]] #Table list by table group
ns, nt = len(sps), 19 - 10 #Number of table groups, number of times

Formulate and solve.

python


m = LpProblem(sense=LpMaximize) #Mathematical model
p = [[[] for t in range(nt)] for _ in range(6)] #Variable list by time by table
a['Var'] = [[addvar(cat=LpBinary) for j in range(ns)] for i, r in a.iterrows()]
m += lpDot(a.Number of people* a.unit price, a.Var.apply(lpSum)) #Objective function(Total sales)
for i, r in a.iterrows():
    m += lpSum(r.Var) <= 1 #Any table group
    for j, sp in enumerate(sps):
        if sum(cap[s] for s in sp) < r.Number of people:
            m += r.Var[j] == 0 #Number of people limit
        for s in sp:
            for t in range(r.Reservation time):
                p[s][r.Start time- 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 #Only one group can accept reservations at the same time at the same table
m.solve()
a['Val'] = a.Var.apply(lambda v: int(value(lpDot(range(1, ns+1), v))))
print('%s %d people%.2f 10,000 yen' % (LpStatus[m.status],
    sum(a[a.Val > 0].Number of people), value(m.objective) / 10000))
>>>
Optimal 8 3 people 20.440,000 yen

Sales are over 200,000. Shows the successful reservations.

python


print('Hours Number of people Price table')
for i, r in a.iterrows():
    if r.Val:
        print('%2d-%2d %d %d %s' % (r.Start time, r.Start time + r.Reservation time- 1,
                                    r.Number of people, r.Number of people * r.unit price, sps[r.Val-1]))
>>>
Hours Number of people Price table
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]

that's all

Recommended Posts