[PYTHON] Optimisation des stratégies d'embarquement pour les avions - du numéro d'octobre du magazine OR

Qu'est-ce que c'est

OR Society (Problem Solving Science Recherche opérationnelle % 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 Le numéro d'octobre de la revue% AA% E3% 82% B5% E3% 83% BC% E3% 83% 81) est publié dans ["** Students 'OR **" Special Feature](http. http://www.orsj.or.jp/e-library/elcorsj.html#6110), qui présente 30 résumés de diverses thèses de fin d'études et de maîtrise sur lesquelles des étudiants universitaires ont travaillé.

À partir de là, je voudrais aborder le problème d'optimisation de manière appropriée et le résoudre avec Python. Comme préparation, vous avez besoin de pandas, de pulpe, d'oolpy. Pour la construction de l'environnement, [Utiliser l'optimisation des combinaisons](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88% Veuillez vous référer à E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Optimiser les stratégies d'embarquement des avions

Permettez-moi d'utiliser le problème de l'article "Optimisation de la stratégie d'embarquement dans les avions".

Répartissez 6 passagers en 3 groupes. Conseil dans l'ordre du groupe 1. Au sein d'un même groupe, l'ordre est aléatoire. Je veux minimiser le temps total d'embarquement.

Façon de penser

Supposons que l'on vous donne une matrice $ A $ avec le niveau de congestion $ a_ {ij} $ comme facteur si le passager avec le siège $ i $ est monté en premier et le passager avec le siège $ j $ est monté plus tard. Ici, minimisons simplement la somme des niveaux de congestion (= maximise les niveaux de congestion des combinaisons non congestionnées). De plus, dans le même groupe, le degré de congestion sera divisé par deux.

Degré de congestion de la combinaison non encombrée = (somme de $ a_ {ij} $ à l'embarquement dans l'ordre de j, i) + (somme de $ a_ {ij} $ lorsque i et j sont dans le même groupe) / 2

Résoudre avec Python

Tout d'abord, créez des données aléatoires.

python

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

m, n = 3, 6 #Nombre de groupes et nombre de passagers
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.   ]])

Créez une table de variables qui gère si les passagers du siège (Pos) sont en groupes.

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]

Créez une table de variables qui gère si le niveau de congestion A est appliqué. VarN a embarqué le siège le premier plus tard et le deuxième siège d'abord, VarH représente le cas où le siège premier et le siège deuxième sont dans le même groupe.

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]

Formulez et résolvez. L'explication de l'expression de contrainte est omise car elle est gênante.

python

m = LpProblem(sense=LpMaximize) #Modèle mathématique
m += lpDot(tp.A, tp.VarN) + lpDot(tp.A, tp.VarH) / 2 #Fonction objective
for i in rn:
    m += lpSum(tg[tg.Pos == i].Var) == 1 #Assurez-vous d'appartenir à l'un des groupes
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() #Solveur(CBC)Exécution de
tg['Val'] = tg.Var.apply(value) #résultat
tg[tg.Val > 0] #Affichage de la solution

Un groupe pour chaque siège (Pos) a été trouvé. Cette approche a beaucoup de variables discrètes, donc à mesure que le nombre de passagers augmente, le temps de calcul explose. Dans ce cas, une méthode de résolution approximative telle que la méthode de recherche locale sera efficace comme dans l'article original.

Introduction du séminaire OR

Optimisation et statistiques lors du 3e séminaire OR (Business Analytics en langage Python) qui se tiendra le samedi 12 novembre. Présentation des outils nécessaires dans le domaine de la recherche opérationnelle tels que l'analyse et l'apprentissage automatique. Au bénéfice des participants à ce séminaire, la cotisation annuelle + les frais d'admission pour 2016 et 2017 sont exonérés, et vous pouvez devenir membre régulier de la société. Si vous devenez membre régulier, vous recevrez les magazines institutionnels susmentionnés (12 volumes par an) et les revues, et vous bénéficierez d'avantages tels que la participation gratuite au symposium.

c'est tout