[PYTHON] Optimierung der Boarding-Strategien für Flugzeuge - ab der Oktober-Ausgabe des OR-Magazins

Was ist das

OR Society (Problemlösungswissenschaft 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 % AA% E3% 82% B5% E3% 83% BC% E3% 83% 81) (Ein Treffen von Forschern) Die Oktoberausgabe der Zeitschrift ist ["** Students 'OR **" Special Feature](http http://www.orsj.or.jp/e-library/elcorsj.html#6110), in dem 30 Abstracts verschiedener Abschluss- und Masterarbeiten vorgestellt werden, an denen Studenten gearbeitet haben.

Daraus möchte ich das Optimierungsproblem angemessen aufgreifen und mit Python lösen. Zur Vorbereitung benötigen Sie Pandas, Fruchtfleisch, ortoolpy. Für die Umgebungskonstruktion [Kombinationsoptimierung verwenden](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88% Wir verweisen auf E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Optimierung der Boarding-Strategien für Flugzeuge

Lassen Sie mich das Problem des Papiers "Optimierung der Boarding-Strategie in Flugzeugen" verwenden.

Teilen Sie 6 Passagiere in 3 Gruppen ein. Vorstand in der Reihenfolge von Gruppe 1. Innerhalb derselben Gruppe ist die Reihenfolge zufällig. Ich möchte die gesamte Boarding-Zeit minimieren.

Denkweise

Angenommen, Sie erhalten eine Matrix $ A $ mit der Überlastungsstufe $ a_ {ij} $ als Element, wenn der Passagier mit Sitz $ i $ zuerst und der Passagier mit Sitz $ j $ später an Bord geht. Hier minimieren wir einfach die Summe der Überlastungsgrade (= maximieren die Überlastungsgrade von nicht überlasteten Kombinationen). In derselben Gruppe wird sich auch der Grad der Überlastung halbieren.

Überlastungsgrad der nicht überlasteten Kombination = (Summe von $ a_ {ij} $ beim Einsteigen in der Reihenfolge j, i) + (Summe von $ a_ {ij} $, wenn i und j in derselben Gruppe sind) / 2

Löse mit Python

Erstellen Sie zunächst zufällige Daten.

python

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

m, n = 3, 6 #Anzahl der Gruppen und Anzahl der Passagiere
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.   ]])

Erstellen Sie eine variable Tabelle, die verwaltet, ob sich die Passagiere auf dem Sitz (Pos) in Gruppen befinden.

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]

Erstellen Sie eine Variablentabelle, die verwaltet, ob die Überlastungsstufe A angewendet wird. VarN bestieg zuerst den Sitz und später den zweiten Sitz. VarH stellt den Fall dar, in dem Sitz 1 und Sitz 2 zur selben Gruppe gehören.

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]

Formulieren und lösen. Die Erklärung des Einschränkungsausdrucks wird weggelassen, da dies problematisch ist.

python

m = LpProblem(sense=LpMaximize) #Mathematisches Modell
m += lpDot(tp.A, tp.VarN) + lpDot(tp.A, tp.VarH) / 2 #Zielfunktion
for i in rn:
    m += lpSum(tg[tg.Pos == i].Var) == 1 #Stellen Sie sicher, dass Sie zu einer der Gruppen gehören
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() #Löser(CBC)Hinrichtung von
tg['Val'] = tg.Var.apply(value) #Ergebnis
tg[tg.Val > 0] #Anzeige der Lösung

Für jeden Sitzplatz (Pos) wurde eine Gruppe gefunden. Dieser Ansatz hat viele diskrete Variablen, sodass die Berechnungszeit mit zunehmender Anzahl der Passagiere explodiert. In diesem Fall ist eine ungefähre Lösungsmethode wie die lokale Suchmethode wie im Originalpapier wirksam.

Einführung des OP-Seminars

Optimierung und Statistik beim 3. OR-Seminar (Business Analytics in Python Language) am Samstag, den 12. November. Einführung von Tools, die im Bereich der Betriebsforschung erforderlich sind, wie Analyse und maschinelles Lernen. Als Vorteil für die Teilnehmer dieses Seminars ist der jährliche Mitgliedsbeitrag + Eintrittspreis für 2016 und 2017 befreit, und Sie können ein reguläres Mitglied der Gesellschaft werden. Wenn Sie ein reguläres Mitglied werden, erhalten Sie die oben genannten institutionellen Magazine (12 Bände pro Jahr) und Zeitschriften sowie Vorteile wie die kostenlose Teilnahme am Symposium.

das ist alles