[PYTHON] Optimizing boarding strategies for aircraft-from the October issue of the OR bulletin

what is this

OR Society (Problem-solving science Operations Research % 83% 9A% E3% 83% AC% E3% 83% BC% E3% 82% B7% E3% 83% A7% E3% 83% B3% E3% 82% BA% E3% 83% BB% E3% 83 The October issue of the journal of (% AA% E3% 82% B5% E3% 83% BC% E3% 83% 81) researchers' gathering) is "** Students' OR **" Special Feature http://www.orsj.or.jp/e-library/elcorsj.html#6110), which introduces 30 abstracts of various graduation thesis and master's thesis that university students have worked on.

From this, 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).

Optimizing boarding strategies for aircraft

Let me use the problem of the paper "Optimization of boarding strategy in aircraft".

Divide 6 passengers into 3 groups. Board in order from Group 1. Within the same group, the order is random. I want to minimize the total boarding time.

Way of thinking

Suppose you are given a matrix $ A $ with the congestion level $ a_ {ij} $ as the factor if the passengers in seat $ i $ board first and the passengers in seat $ j $ board later. Here, let's simply minimize the sum of the congestion levels (= maximize the congestion levels of non-congested combinations). Also, in the same group, the degree of congestion will be halved.

Congestion degree of non-congested combination = (sum of $ a_ {ij} $ when boarding in the order of j, i) + (sum of $ a_ {ij} $ when i and j are in the same group) / 2

Solve with Python

First, create random data.

python

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvar, addvars

m, n = 3, 6 #Number of groups and number of passengers
rm, rn = range(m), range(n)
np.random.seed(1)
A = np.random.rand(n, n).round(3)
A[np.diag_indices(n)] = 0
A
>>>
array([[ 0.   ,  0.72 ,  0.   ,  0.302,  0.147,  0.092],
       [ 0.186,  0.   ,  0.397,  0.539,  0.419,  0.685],
       [ 0.204,  0.878,  0.   ,  0.67 ,  0.417,  0.559],
       [ 0.14 ,  0.198,  0.801,  0.   ,  0.313,  0.692],
       [ 0.876,  0.895,  0.085,  0.039,  0.   ,  0.878],
       [ 0.098,  0.421,  0.958,  0.533,  0.692,  0.   ]])

Create a variable table that manages whether passengers in a seat (Pos) are in a group (Group).

python

tg = pd.DataFrame(((i, j+1) for i in rn for j in rm), columns=['Pos', 'Group'])
tg['Var'] = addvars(len(tg), cat=LpBinary)
tg[:3]

Create a variable table that manages whether congestion A is applied. VarN will board the seat first later and the seat second first, VarH shall represent the case where Seat First and Seat Second are in the same group.

python

tp = pd.DataFrame(((i, j, A[i,j]) for i in rn for j in rn if A[i,j]),
    columns=['First', 'Second', 'A'])
tp['VarN'] = addvars(len(tp), cat=LpBinary)
tp['VarH'] = addvars(len(tp), cat=LpBinary)
tp[:3]

Formulate and solve. The explanation of the constraint expression is omitted because it is troublesome.

python

m = LpProblem(sense=LpMaximize) #Mathematical model
m += lpDot(tp.A, tp.VarN) + lpDot(tp.A, tp.VarH) / 2 #Objective function
for i in rn:
    m += lpSum(tg[tg.Pos == i].Var) == 1 #Be sure to belong to one of the groups
for _, r in tp.iterrows():
    tf = tg[tg.Pos == r.First]
    ts = tg[tg.Pos == r.Second]
    m += (lpDot(tf.Group, tf.Var) - lpDot(ts.Group, ts.Var) - 1)/n + 1 >= r.VarN
    m += (lpDot(tf.Group, tf.Var) - lpDot(ts.Group, ts.Var))/(n-1) + 1 >= r.VarH
    m += (lpDot(ts.Group, ts.Var) - lpDot(tf.Group, tf.Var))/(n-1) + 1 >= r.VarH
m.solve() #Solver(CBC)Execution of
tg['Val'] = tg.Var.apply(value) #result
tg[tg.Val > 0] #Display of solution

A group for each seat (Pos) was found. This approach has many discrete variables, so as the number of passengers increases, the computational time explodes. In that case, an approximate solution method such as a local search method will be effective as in the original paper.

Introduction of OR seminar

Optimization / Statistics at 3rd OR Seminar (Business Analytics in Python Language) to be held on 11/12 (Sat.) Introducing tools required in the field of operations research such as analysis and machine learning. As a privilege for participants of this seminar, the annual membership fee + admission fee for 2016 and 2017 is exempted, and you can become a regular member of the society. If you become a regular member, you will receive the above-mentioned journals (12 volumes a year) and dissertation journals, and you will receive benefits such as free participation in the symposium.

that's all