アルゴリズム サーキットカー 運転順序探索

Question

実現したいこと

あるサーキットを周回する車両に、待機時間をなるべく少なく運転手を割り当てるアルゴリズムを実現したい。
【例】
車両A,B,C,D,E
ドライバー1，2，3，4，5
条件：
①車両は並列走行や追い抜きをせず、必ずA～Eの順で等間隔で走行する。
②ドライバーは1度運転した車両には乗らず、全ドライバーが全車両を運転したら終了する。
③ドライバー1のみ、A,B,C,D,Eの順で車両を運転する。
④初めの車両割り当ては車両A:ドライバー1、車両B:ドライバー2、車両C:ドライバー3、車両D:ドライバー4、車両E:ドライバー5とする。
⑤物理的な乗り換え時間確保のためドライバー1以外は連続した車両は運転できない。例えば車両Bを運転していたドライバー2は次に車両Cを運転できない。

発生している問題・分からないこと

上記のようなアルゴリズムをPythonで実現したいのですが、条件分岐が多すぎて解が見つからない気がしています。
アルゴリズムのアイデアをお持ちの方はご回答お願いいたします。

該当のソースコード

特になし

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

遺伝的アルゴリズムで解決可能？
条件の付け方がわからない。

補足

補足削除

Comments

[TakaiY]

車から下りるための条件とか、車に乗るための条件とか、わからないことが多いように思うのですが、問題の出展元はどこですか？
回答はここではなく、質問を編集してください。

[ikedas]

何やら非常に作為的に見える条件がついていて、問題設定の必然性が感じられないです (そもそも、車両とドライバーが同数なのだから全員がずっと乗り換えずに運転していれば待機時間はゼロでは?)。
個々の条件の必然性や、ここには書かれていない暗黙に設定された条件が分かりませんので、この場には回答できる人はいないと思います。何か疑問があれば問題を出した人に質問してください。

[TakaiY]

出展は？というのはどこかのサイトでの出題なのかと思って聞いたものなので、本来知りたいのはそこではなく、ikedasさんのコメントにもあるとおり、アルゴリズムを考えるために必要ら条件が足りません。
- ドライバーは1週したら下りる？
- 乗り換えはどのように行なわれる？
- 車は追い越される？
- 車の台数と人数はどのような関係？
他にもいろいろ。
また、実際に運用するのであれば、最適を求めるよりも、運用がわかりやすいほうがいいなどあると思いますがそのあたりはどうですか？

[takes.it.easy]

・ドライバーは1周したら下車します。
・乗り換えはサーキットのパドックへ停車し、次の車両が戻ってきたら乗りますが、車両の走行順は必ずA,B,C,D,Eの順である必要があります。
・車は追い越されません。また並走もしません。
・車両は試乗車、人数は今回の参加人数です。場合によっては車両の台数も参加人数も変わります。
その他知りたい条件がございましたらご教示願います。
背景ですが、これまですべての組み合わせを書き出して順番を決めていましたが、人数と車両の数によっては膨大な組み合わせになります。それを解決するようなアルゴリズムがあるのかという気持ちで投稿しました。
運用が分かりやすいに越したことはないと思ってます。今回でいえば全員ドライバー1のように次の車に乗ればいいと思いますが、それでは待ち時間の観点から難しく。。
条件がガチガチに決まっているため、どこかで妥協点を見つけなければ解けない問題かなとも思ってます。

[TakaiY]

ここは、質問に対するコメントを書く場所ですので、回答はここではなく質問を編集して追記してください。

全員順番に乗る場合に
> それでは待ち時間の観点から難しく
というのはどういう意味でしょう？

[takes.it.easy]

1周するのに5分かかるとします。
Aがスタートして1分後にBがスタートします。(条件書き忘れでしたね)
上記のように前の車がスタートしてから1分後に次の車がスタートします。
車両間はなるべく等間隔で走行しますが、車によっては早い遅いがあるので1周してから次の車が来るまでに全員がおよそ1～3分待つことになります。
これがトータルで考えると大きいため、全員が次の車に乗るのは難しいと書きました。

[TakaiY]

ドライバーを一列に並べて、車が空いたとき、先頭から乗ったことのない人を探して車に割り当てる。車から下りたら、列の最後に並ぶ。全て乗ったら列にならばない。

だとだめな理由ってありますか？
これなら、車は常に動いていることになるはず。(ならないか？)

[takes.it.easy]

とてもシンプルかつ私の思っている通りの表現です。
基本的には問題ないと思います。
あとは特別な条件を満たせるかどうかですね。
特別な条件とは、
・ドライバー１は必ずA,B,C,D,Eの順で乗る。
・初期は車両A：ドライバー1、車両B：ドライバー2、…、車両E:ドライバー5
（これは初期の並びをこの通りに並べればよいだけ？）

[TakaiY]

> ドライバー１は必ずA,B,C,D,Eの順で乗る。
これは、なぜそうなっているのでしょう？ まあ、この人にこの順で乗ってもらえばいいだけと思いますけど。

[takes.it.easy]

上からの要望です。

[tmp]

待ち時間の計算ってどのようにカウントするのでしょうか？

[ikedas]

現状の質問文では条件が客観的に過不足なく説明されて**いない**ため伝わらなすぎます。
コメントで聞かれたことに対してはコメント欄に追加説明を書いてすますのではなく、**質問文を編集して**質問文を読めば全てがわかるようにしてくださいませんか。コメント欄は隠れてしまうので見落とされます。

あと、自分で試してみずに「コードをください」という**丸投げの質問**は当サイトでは推奨されません。整理した条件を見ながら、改めてもう一度ご自分でもコードを書いてみて、できたところまでを提示なさった方あよいと思います。そうすればどこで行き詰っておられるのかが伝わりやすいです。

[fana]

> 等間隔で走行

の間隔というのは，周回毎に変わるということ？

例えば最初に B が１周した時点で，AとBのドライバーを入れ替えてAを出発させることができるけども，次のBの出発時刻というのは，残りの B,C,D,E が達成できる「等間隔」の分だけAの出発時刻から遅れさせる（というスケジューリングを行う）必要がある？？

[tmp]

⑤の条件は、
１以外、単純に前回のった車の１つ後ろの車に乗れないって条件ですか？
その場合、車Eの後に車Aには乗れますか？

クイズだと思ってシンプルに

1 2 3 4 5　←③④
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

縦横に同じ数字が入らない。②①（時間待ちを少なくは、一周毎に１回乗るっていう意味？）
1以外、左上に同じ数字が入らない。⑤
上記を数独もどきと考えていいですか？

数独の解法と同じように、条件の当てはまる総当たり？
最適化されてない方法（上から順においていく方法）でも意外と回数が少なくおけるかどうかの判定1326回でおさまりました。結果４つ答えがでました。
little_streetさんと同じ答えがでてきましたので勝手に解いた気になってますｗ
車Eの後に車Aダメの条件は、いれると
[[1, 2, 3, 4, 5], [3, 1, 4, 5, 2], [5, 4, 1, 2, 3], [2, 3, 5, 1, 4], [4, 5, 2, 3, 1]]
[[1, 2, 3, 4, 5], [5, 1, 4, 2, 3], [2, 3, 1, 5, 4], [3, 4, 5, 1, 2], [4, 5, 2, 3, 1]]
が弾かれました。

でも、結局総当たりは、望む解法じゃないんですよね？

[ikedas]

> > ドライバー１は必ずA,B,C,D,Eの順で乗る。
> これは、なぜそうなっているのでしょう？ まあ、この人にこの順で乗ってもらえばいいだけと思いますけど。
おそらく主催者側の人でしょう。主催者側としてはすべての車両の正常性を確認しておく必要があるでしょうし、先導車のような役割もあるのでしょう。

> １以外、単純に前回のった車の１つ後ろの車に乗れないって条件ですか？
> その場合、車Eの後に車Aには乗れますか？
これ、私も最初そう思いました。あと、「連続」という言葉からすると「前回乗った車の1つ前」(例えばC→Bの順に乗る) もだめになるかな。そうするとA→Eもだめということになる。
しかし、そうするとおそらく条件を満たす乗りかたは存在しないです。

しかしその後のコメントを見るとそういうことではなく、単に「降りたらまたすぐに乗車してはだめ (ドライバー1だけが例外で、車両を替えながらずっと乗車し続けている)」ということだと思います。
一旦乗って降りたら、次にくる車両はやり過ごして、それより後の車に乗ればいいということではないですかね。

[tmp]

⑤物理的な乗り換え時間確保とか書いてありますが、一週目１２３４５の後、2週目の車Ａに人５が乗る場合、
車は追い抜けないので、Ｅの５が返ってくるまでみんな待っているわけで、その場合、Ｂ：２が車ＣやＣ：３が後ろの車で車Ｄ二週目に乗り換え時間はあると思うので、そういった話が説明にないのは、現実的な問題解決ではなくて、これはクイズと判断したわけです。
それで逆に答えのでそうな問題を想像したわけです。

[ikedas]

私も同じ理由から、クイズだと最初は思いました。
改めて考えてみると乗車の間隔を空ける理由はいろいろありえて、
・降車してすぐに乗車するのは不慣れなお客さんには難しく危険。
・連続乗車を認めると特定のお客さんだけが乗車して他の大多数は待たされ、不公平^H^H^H不公平感がある。
・休憩なしの長時間運転は事故の危険性が増す。
といったものが考えられます。待機時間だけの問題ではないだろうと思います。

なぜか質問の条件や背景をなるべく隠そうとする (ように見える) 質問というのあ時々ありますが、混乱するので、説明は十分にしてほしいですね (もちろん、質問文を編集して書いていただきたいです)。

[ikedas]

質問者さん、すみませんが、コメント欄でご自分が書いたことを質問文に組み入れて、質問文を読めば問題の全体がわかるようにしていただけますか。
ここで回答やコメントをしている人は、この質問と回答が将来同じような問題に遭った人の解決の助けになるようにと思って回答やコメントをしているので、あなただけのためだったら無償で回答したりなんかしません。ご協力をお願いします。

あと念のためですが、質問文から文章を削除しても編集履歴には残っていますので、せっかく書いた補足を削除したりすることはあまり意味がないです。

Answer 1

コメントに書いた方式を載せておきます。

ドライバーを一列に並べて、車が空いたとき、先頭から乗ったことのない人を探して車に割り当てる。車から下りたら、列の最後に並ぶ。全て乗ったら列にならばない。
ただし、ドライバー１は必ずA,B,C,D,Eの順で乗るように優遇する。

Answer 2

TakaiYさんの回答でよいと思います。細かい補足を加えると、

• ドライバの数が車両の数+1かそれ以下の場合には、「空いている車両があるのに、連続して乗車できないために乗れない人が出る」という矛盾が起きる。したがってドライバの数は車両の数+1より多いと仮定する。
• 前項の仮定により、走行中は常にパドックに乗車待ちの人の列ができるが、乗車して帰ってきた人は列の最後尾に並ぶ 。パドックに車両が着いたら、その車両にまだ乗車したことのない人のうち列の中で一番前の人が乗車する。
  • ただしドライバ1は例外で、降車したらすぐ次にくる車両に優先的に乗車できる。
• すべての車両に乗り終えた人は列を離れる。
  一方、すべてのドライバーに乗られた車両は帰庫する (車庫までは主催者側のスタッフが運転する)。

間違っていたら指摘ください。

Answer 3

待機時間をなるべく少なく運転手を割り当てるアルゴリズムを実現したい。

と条件５の関係が今ひとつ理解できていませんので，条件５の部分は変更し易い形にしてみました。

「行：周回，列：車両」の要素にドライバーを示す値（1, 2, 3, 4, 5）を持つ 5ｘ5 の2次元配列を考え，条件に合うものを選別する記述例を下記に示します。

import numpy as np
from itertools import permutations, combinations

def check_column(x):  # condition 2
    for j in range(x.shape[1]):
        for a, b in combinations(x[:, j], 2):
            if a == b:
                return False
    return True

def check_diagonal(x):  # condition 5
    for i in range(x.shape[0] - 1):
        for j in range(x.shape[1] - 1):
            if i == j:
                continue
            if x[i, j] == x[i + 1, j + 1]:
                return False
    return True


r_grp = [[], [], [], [], []]
for r in permutations((1, 2, 3, 4, 5)):
    for k in range(1, 5):
        if r[k] == 1:
            r_grp[k].append(r)
            break

r0 = (1, 2, 3, 4, 5)  # condition 4
for r1 in r_grp[1]:
    for r2 in r_grp[2]:
        for r3 in r_grp[3]:
            for r4 in r_grp[4]:
                arr = np.array([r0, r1, r2, r3, r4])
                if check_column(arr) and check_diagonal(arr):
                    print(arr)
# [[1 2 3 4 5]
#  [3 1 4 5 2]
#  [4 5 1 2 3]
#  [5 3 2 1 4]
#  [2 4 5 3 1]]
# [[1 2 3 4 5]
#  [3 1 4 5 2]
#  [5 4 1 2 3]
#  [2 3 5 1 4]
#  [4 5 2 3 1]]
# [[1 2 3 4 5]
#  [4 1 5 2 3]
#  [2 5 1 3 4]
#  [5 3 4 1 2]
#  [3 4 2 5 1]]
# [[1 2 3 4 5]
#  [5 1 4 2 3]
#  [2 3 1 5 4]
#  [3 4 5 1 2]
#  [4 5 2 3 1]]