旅館布団敷き巡回効率化について

Question

1 質問の動機
今，旅館で働いています。旅館では，客の登録情報をもとに，夜食事に向かう時間に応じて布団敷きの順番を決めます。ですが，現在，インバウンドの客が増加したことにより，より効率よく布団敷きの巡回をしなければならなくなりました。
そのため，効率的な布団敷き順路を，食事時間に応じて編成できるようなプログラムを作りたいと思っています。
どの旅館でも汎用性のあるプログラムにしたいので，部屋数，階数，移動方法などは打ち込みでできるようにしたいです。しかしここではサンプルとして，特定の旅館を提示してみたいと思います。

2 条件の例示
布団敷きでは，1階から5階までを階の両端にあるエレベーターで移動して目的の部屋に移動します。端から端まで20部屋あり、隣り合う部屋間の移動はx秒、エレベーターによる階数移動は回数に応じてy秒ずつ増加。一部屋の布団敷きにかかる時間はz秒。さらに、ランダムに食事時間（＝布団敷き許容時間）が各部屋に割り当てられています。布団敷きをするチームは2つに分かれて独立して動くことができます。

このような状況下で、どのような計算が適しているか、みなさんと話し合いたいです！
抜けている条件など適宜は追加したいと思うので、たくさん意見くださったら嬉しいです。

（込み入った状況としては、各部屋人数がもちろん違うので、布団敷きにかかる時間も違います。そして、もし全ての部屋が時間に間に合わなそうな結果の場合、クレームを最小限にするため、間に合わない部屋数も最小化したいです。）

3 少し考えてみた。
最初の一部屋を割り出した後は、近くの部屋で、食事時間と対応し、かつ移動時間が少ない順に大きい方から点数をつけていき、最大の点数の部屋を次の部屋として指定する。
ハミルトン閉路の弱化版のような気がするので、総当たり戦が有効なのだろうか？
ぐらいしか思いつきません！助けてください！

4 展望
業務効率化で（自分の）ブラック労働を減らしたいので、そして、布団敷きに苦しむ色んな人に使って欲しいので、ゆくゆくは3D見取り図などに経路が表示されると素晴らしいなと思います。

どうにか皆さんとお話ししながらこの問題を解決したいです！！！