I decided to go to the amusement park with her. How do you go around the amusement park facilities to maximize her satisfaction? However, due to her curfew, the amusement park has only 200 minutes.

You can solve such problems with Combinatorial Optimization (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721). It's similar to the knapsack problem and the traveling salesman problem, but let's formulate it now.

Formulation

However, $ TM_ {fr, to} $ is the travel time from the facility $ fr $ to $ to $, and $ TU_ {to} $ is the usage time at the facility $ to $. Also, constraint (6) is valid only when $ x_ {fr, to} $ is 1. The first facility S will be the entrance to the amusement park and will return to the entrance at the end. Also, the same facility can only be used once.

Solve with Python

Try it with Python 3.5 from Jupyter. If you can use docker, you can run it with tsutomu7 / jupyter or tsutomu7 / alpine-python: jupyter.

Preparation

Import the library to be used and set the drawing.

python3

%matplotlib inline
import numpy as np, pandas as pd, matplotlib.pyplot as plt
from collections import OrderedDict
from pulp import *
from pulp.constants import LpConstraintEQ as EQ, LpConstraintLE as LE
plt.rcParams['font.family'] = 'IPAexGothic'
plt.rcParams['font.size'] = 16

Facility and travel time settings

python3

n = 6
np.random.seed(2)
a = pd.DataFrame(OrderedDict([
        ('Facility', ['S'] + [chr(65+i) for i in range(n-1)]),
        ('Satisfaction level', np.random.randint(50, 100, n)),
        ('Utilization time', np.random.randint(3, 6, n) * 10),
        ]))
a.loc[0, a.columns[1:]] = 0
Travel time= np.random.randint(1, 7, (n, n))
Travel time+=Travel time.T #Make a symmetric matrix
a

You can use OrderedDict to fix the order of columns.

Formulate and solve

python3

def solve_route(a, limit):
    n = a.shape[0]
    m = LpProblem(sense=LpMaximize)
    b = pd.DataFrame([(i, j, LpVariable('x%s%s'%(i,j), cat=LpBinary))
        for i in a.Facility for j in a.Facility], columns=['fr','to','x']) # (1)
    b['Travel time'] = Travel time.flatten()
    b = b.query('fr!=to')
    y = {i:LpVariable('y%s'%i) for i in a.Facility} # そのFacilityの利用終了時刻(2)
    m += lpDot(*pd.merge(b, a, left_on='fr', right_on='Facility')
        [['x', 'Satisfaction level']].values.T) #Objective function(3)
    for i in a.Facility:
        m += LpConstraint(lpSum(b[b.fr==i].x), EQ if i=='S' else LE, rhs=1) # (4)
        m += lpSum(b[b.fr==i].x) == lpSum(b[b.to==i].x) # (5)
    M = b.Travel time.sum() + a.Utilization time.sum() #Large enough value
    for _, r in b.iterrows():
        m += y[r.to] >= r.Travel time+ a[a.Facility==r.to].Utilization time.sum() \
                        + (0 if r.fr=='S' else y[r.fr]) - (1-r.x)*M # (6)
    m += y['S'] <= limit # (7)
    m.solve()
    return value(m.objective), b[b.x.apply(value)>0]
objv, rs = solve_route(a, 200)
print('Total satisfaction= %g'%objv)
rs
>>>
Total satisfaction= 311

If you turn A-> E-> C-> B from the entrance (S), you can see that the total satisfaction can be maximized to 311.

Let's see the transition of staying time and satisfaction

python3

%%time
rng = np.linspace(250, 130, 13)
rsl = [solve_route(a, i)[0] for i in rng]

plt.title('Changes in satisfaction')
plt.xlabel('Maximum length of stay')
plt.plot(rng, rsl);
>>>
CPU times: user 1.11 s, sys: 128 ms, total: 1.24 s
Wall time: 6.47 s

The longer you spend together, the more satisfied you are.

This problem becomes a difficult problem called the mixed integer optimization problem. As the number of facilities increases, it suddenly becomes impossible to solve, so in that case, it is necessary to devise such as using an approximate solution method.

that's all