はじめに

私はほぼ毎週飛行機に乗るため、飛行機搭乗時に、「混雑を避けるため、後方座席のお客様からご案内いたします」という案内、非常に良く聞くのですが、いつもこのアルゴリズムにあまり納得がいっていませんでした。

搭乗時の混雑の原因は主に二つあります。

手荷物の上部収納
既に乗客が座っているよりも奥の座席に入る場合（例えば、通路側に既に座っている人がいる時に、窓側の席に座ろうとすると、一度通路側の席の乗客が立つ必要がある）
私は、この2点については、後方座席・前方座席を分けることによって、むしろ上記渋滞発生箇所が近くで発生してしまい、より混雑を生むように思っていました。

全ての乗客を早く搭乗させることを目的とするならば、例えば窓側の乗客を先に搭乗させれば上記の混雑はある程度解消されます。しかし、飛行機では上部収納がいっぱいになってしまって席の近くの収納棚が使えないことがしばしばありますので、その公平性の面で、少なくとも列を保って搭乗させているのだとしぶしぶ理解していました。

しかし、です。先日搭乗した際に、なんと地上係員の方が「窓際のお客様から先にご案内いたします」と宣言したのです！収納棚の公平性が関係ないのであれば、いろいろと手段があります。そこで、（前置きが長くなりましたが、）飛行機搭乗中の暇つぶしを兼ねて、この問題をシミュレーションしてみることにしました。

前提

機体はA320（中央に通路、両側に6席、28列。最後方の4席レイアウトは便宜上6席とする）http://www.ana.co.jp/domestic/departure/inflight/seatmap/detail.html?c=a32
優先搭乗（小さな子ども連れ、プレミアムメンバーなど）は無視
入り口は前方一つ
以上に基づいて、通路をキューにみたてたシンプルなモデルをプログラム

基本コード

flight.pl

use strict;
use List::Util qw/shuffle/;
use Statistics::Descriptive;
use POSIX;
use Perl6::Say;

my $seats = 28;
my @passengerids;
my $debug = 0;
for my $one (1..$seats){
    for my $two (qw/L R/){
        for my $three (0..2){
            push(@passengerids, sprintf("%02d%s%d", $one,$two,$three));
        }
    }
}

say flightTest(shuffle(@passengerids));


sub flightTest{
    my @passengers = @_;
    my @path;
    my @wait;
    my $turn = 0;
    my $seated = 0;
    my $data;
    while($seated < scalar(@passengerids)){
	$turn ++;
	
	print "turn: $turn    " if($debug);
	for (0..$seats){
	    my $num = $seats - $_;
	    my $fnum = sprintf("%02d", $num);
	    
	    next unless(length($path[$num]));
	    
	    if($wait[$num]){  #waiting to be seated
		$wait[$num] --;
		if($wait[$num] == 0){ #wait time is over. time to get seated.
		    if($path[$num] =~ /^$fnum([LR])(\d)$/){
			$seated++;
			print $path[$num] . sprintf(" is seated. \(%d/%d\)\n", $seated, scalar(@passengerids)) if($debug);
			$data->[$num]->{$1}->[$2] = 1;
			$path[$num] = '';
		    }else{
			die("something is wrong in seating");
		    }
		}
	    }elsif(length($path[$num + 1]) < 2){  #proceed if there is opening in front
		my $fnum = sprintf("%02d", $num + 1);
#	    say $path[$num] . " moved forward to $fnum";
		$path[$num + 1] = $path[$num];
		$path[$num] = '';
		if($path[$num + 1] =~ /^$fnum([LR])(\d)$/){  #is my row
		    my $side = $1;
		    my $spos = $2;
		    my $waittime = int(rand(5)); #wait time for baggage placement
		    for (0..2){
			if($spos < $_){
			    $waittime += 4 if($data->[$num]->{$side}->[$_]);
			}
		    }
		    $waittime ++; #basic time to be seated.
		    $wait[$num + 1] = $waittime;
		}
	    }else{  #wait if queued
		
	    }
	}
	
	if(length($path[0]) < 1 && scalar(@passengers)){
	    $path[0] = shift(@passengers);
	    print $path[0] . " entered on plane.\n" if($debug);
	}
	
	
    }
    return $turn;
}

シミュレーション！

まぁ実際に通路を移動する時間$turn = 1や、荷物を収納する時間int(rand(5))、席につく時間$waittime ++、既に席に人がいた場合の待ち時間$waittime += 4 #per personなどのパラメータはツッコミどころ満載だと思いますが、とりあえず見ていきましょう。以下、それぞれ100回施行の平均と標準偏差で議論します。

完全にランダムに全員を乗せる場合

my @result;
for (1..100){
    my @passengers = shuffle(@passengerids);
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "regular: ", $stat->mean() , " ", sprintf("%.2f", $stat->standard_deviation());

$ perl flight.pl
regular: 389.45 20.24

普通に何も考えないで乗せると389.45±20.24ターンです。

後方の乗客優先の場合

@result = ();
for (1..100){
    my $num = $seats * 6 / 2;
    my @passengerids1 = @passengerids[$num..$#passengerids];
    my @passengerids2 = @passengerids[0..($num - 1)];
    my @passengers = (shuffle(@passengerids1), shuffle(@passengerids2));
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "halves:  ", $stat->mean() , " ", sprintf("%.2f", $stat->standard_deviation());

$ perl flight.pl
halves:  460.31 21.05

460.31±21.05ターンです！やはり直感通り、この方法の方がトータルの時間では大きく余分にかかっています。ただし、搭乗を開始するまでは待合室で座っていられるので待ち時間と考えなければ、乗客個人あたりの平均搭乗時間はこの半分程度だと考えられますので、顧客満足度はひょっとするとマシなのかもしれません。

窓側の乗客を優先した場合

@result = ();
for (1..100){
    my @passengerids1 = grep {/[LR]0/} @passengerids;
    my @passengerids2 = grep {!/[LR]0/} @passengerids;
    my @passengers = (shuffle(@passengerids1), shuffle(@passengerids2));
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "windows: ", $stat->mean() , " ", sprintf("%.2f", $stat->standard_deviation());

$ perl flight.pl
windows: 321.29 13.91

321.29±13.91ターンです。早いです。やはり効率だけ考えるなら窓際から乗せるべきです。

通路側以外（窓側2席）を先に乗せる場合

@result = ();
for (1..100){
    my @passengerids1 = grep {!/[LR]2/} @passengerids;
    my @passengerids2 = grep {/[LR][01]/} @passengerids;
    my @passengers = (shuffle(@passengerids1), shuffle(@passengerids2));
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "notisle: ", $stat->mean() , " ", sprintf("%.2f",$stat->standard_deviation());

$ perl flight.pl
notisle: 336.32 13.46

こちらは窓際優先とほとんど差がありませんが、2/3の乗客にとって搭乗開始がすぐなこと、1/3の乗客は全員通路側なので、確実にスムーズに乗れること、などから多少利点があるかもしれません。

偶数・奇数席で２分

@result = ();
for (1..100){
    my @passengerids1 = grep {/^(\d+)[LR]/; $1 % 2} @passengerids;
    my @passengerids2 = grep {/^(\d+)[LR]/; !($1 % 2)} @passengerids;

    my @passengers = (shuffle(@passengerids1), shuffle(@passengerids2));
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "odd-even: ", $stat->mean() , " ", sprintf("%.2f", $stat->standard_deviation());

$ perl flight.pl
odd-even: 392.6 14.86

通常（完全ランダム）とほとんど変わりません。が、これは特筆すべき状況で、後方座席優先の場合トータルの時間が延びるのに対し、こちらは伸びていません。よって、搭乗時間を無駄に伸ばすことなく、乗客の搭乗開始からの時間を見かけ上半減させている優れたアルゴリズムと考えることができます。

5の倍数の席を優先

@result = ();
for (1..100){
    my @passengerids1 = grep {/^(\d+)[LR]/; !($1 % 5)} @passengerids;
    my @passengerids2 = grep {/^(\d+)[LR]/; $1 % 5} @passengerids;

    my @passengers = (shuffle(@passengerids1), shuffle(@passengerids2));
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "multiple5: ", $stat->mean() , " ", sprintf("%.2f", $stat->standard_deviation());

$ perl flight.pl
multiple5: 386.86 18.49

これは他の倍数でもあまり変わらないので、2分割する偶数・奇数が乗客あたりの搭乗時間で見た時にベストでありそうです。

フィボナッチ

ちょっと変態な（現実的でない）乗せ方ですが、後方座席からフィボナッチ数列に相当する席（0, 1, 1, 3, 5, 8, 13, 21)、つまり、28, 27, 25, 20, 15, 7番の席から優先に乗せるアルゴリズム。後方よりから詰めつつ、前方にいくほど余裕を持たせる方法です。

@result = ();
for (1..100){
    my (@passengerids1, @passengerids2);
    for my $id (@passengerids){
	if($id =~ /^(\d+)[LR]/){
	    if( $1 == $seats || $1 == $seats - 1 || $1 == $seats - 2 || $1 == $seats - 3 || $1 == $seats - 5 || $1 == $seats - 8 || $1 == $seats - 13 || $1 == $seats - 21){
		push(@passengerids1, $id);
	    }else{
		push(@passengerids2, $id);
	    }
	}
    }

    my @passengers = (shuffle(@passengerids1), shuffle(@passengerids2));
    push(@result, flightTest(@passengers));
}
my $stat = new Statistics::Descriptive::Full;
$stat->add_data(@result);
say "fibonacci: ", $stat->mean() , " ", sprintf("%.2f", $stat->standard_deviation());

$ perl flight.pl
fibonacci: 367.89 16.82

ほとんどギャグのつもりで入れたんですが、悪くないです。明らかに実用的ではないですが。

結論

$ perl flight.pl
regular: 389.45 20.24
halves:  460.31 21.05
windows: 321.29 13.91
notisle: 336.32 13.46
odd-even: 392.6 14.86
multiple5: 386.86 18.49
fibonacci: 367.89 16.82

パラメータなど要検討条件はそれなりにあるとは思いますが、

後方・前方で分けるアルゴリズムはよろしくない
収納棚の公平性に目をつぶれば、窓側、あるいは窓より2列から搭乗させるのが最も効率が良い
収納棚の公平性を考えるのであれば、偶数・奇数列ごとに搭乗させ、偶数・奇数のどちらを優先にするかはランダムに決めると良い
フィボナッチ（以下略）

お後がよろしいようで。

by gaou