実は超難問!デイサービスにおける送迎表の作成業務

デイサービスで送迎表を担当している皆さん、どのようにしたら短時間で精度の高い送迎表を作成できるか悩んでいませんか。結論からいいますと、送迎表を人力で作成するのは限界があり、最短経路を求めるのは不可能です。
私もデイサービスでの勤務経験があり、その際に送迎表の作成に携わっていました。毎日、送迎表のことで頭がいっぱいで時間をかけて作成しても、後からもっと良い案を思いついたりします。送迎表の作成は時間を費やすほど良い案がでるわけでもなく、かつ短時間でするには難しすぎる問題です。
もっと短時間での作成、かつ高精度な送迎表を求めて、私はGoogleが公開しているAIとPythonを利用して送迎表作成システムを構築してみました。
これらを活用して気づいた介護施設における送迎表作成の問題点や、改善方法について解説していきます。システムの詳細についてはまたの機会とします。
手始めに次の送迎表は作れますか?

手始めに上の地図に示したマーカーをつないで、送迎表を作れますか?
問題の条件は以下となります。
1.家のマーカーは施設
2.赤のマーカーは席に座れる利用者
3.青のマーカーは車いすの利用者
4.利用者の総数は35名
5.送迎にかかる時間は1時間以内
6.送迎車は何台使用しても可
ぱっと見て、送迎ルートごとにグループ分けするのは難しいです。想定する送迎車の種類や数により難易度は変わります。実用的な送迎表を作成できたでしょうか。
ちなみに、例題としてロンドンの街を利用していますが、実在の施設や居住者と関係はございません。
巡回セールスマン問題
いきなり送迎表を作成するのは、難しすぎると感じたでしょう。
そこで次に車の搭乗者数の上限を無視して、1台の送迎車ですべての地点を回るルートの場合はどうでしょう。この問題は1人のセールスマンがすべての地点を、最短で回るルートを計算する巡回セールスマン問題と一緒です。この問題の特徴は、地点が増えれば増えるほど難解となることです。
Google OR-ToolsとPythonを利用したシステムで、この問題を解いてみたところ以下のルートとなりました。

ルートを見てみますと、実際に通れるルートは直線的でないことがわかります。場所によっては、一方通行などもあり、それらを考慮するとこのようなウネウネとしたルートとなります。
ルートの総距離は約62kmです。このルートであれば5時間30分で送迎できます。
この問題は35地点の巡回セールスマン問題です。本来、最短経路を求めるには35!/2✕35通りすべてを計算する必要があります。しかしすべての組み合わせは1.476×10の38乗と途方もない数です。この組み合わせを実用的な時間で調べることは、スーパーコンピューターをもってしても不可能です。
実際は1台で送迎できません
巡回セールスマン問題で、この問題の難解さが理解できたでしょうか。巡回セールスマン問題では、地点が1つ増えるごとに難易度が格段に上がります。例えば40地点であれば、組み合わせの総数は1.101×10の46乗です。難易度は途方もなく難しいです。
送迎表を作る際に考慮すべき点としては、搭乗者の上限数、車いすの利用、送迎車の数や種類などを考慮する必要があります。考慮すべき条件が増えれば増えるほど組み合わせの数が膨大になっていきます。つまり送迎表の作成は、巡回セールスマン問題よりも遥かに難易度が高いです。
最初の問題について、送迎表を作成したものが以下です。

図における色分けは、送迎車が違うことを意味しています。図のように9台の送迎車を利用することで、1時間以内にすべての地点をいけるようになりました。
AIを活用するメリットは、複数の送迎表を作成できる点です。作成した他の案についても紹介していきます。

こちらの案も9台の送迎車で1時間以内に送迎できるルートです。どちらの送迎表も問題がないように思えます。しかし、2つの送迎表は総距離が大きく異なり時間も距離も短い、送迎表案1が優秀です。
送迎表は、ぱっと見ただけでは優劣がわかりにくいのが特徴です。マップを活用していない送迎表であれば、尚更わかりにくいでしょう。
人の手で送迎表を作成する問題点
人の手により送迎表を作成するには、難しいだけではなく様々なデメリットがあります。
これらの問題点について解説していきます。
上司や同僚が難易度を理解していない
まず問題となるのは、上司や同僚が送迎表の作成における難易度を理解していない場合です。
上司からの理解が乏しい場合は、作成時間を十分に与えもらえなかったり、急な調整などの無理難題を押し付けられたりします。
送迎表はNP困難といわれ、最適化問題のなかでも難しい部類に入ります。人の手で作成する場合には、しっかりと時間を確保してもらいましょう。
計算できるルートには限りがある
人の計算能力には限界があります。送迎表を作成する場合、複数のルートを計算することはないでしょう。通常は1通りの送迎表を作成し、問題がないかを確認します。問題がなければ送迎表の作成は終了です。
複数のルートを比較検討できないため、コストの少ないルートがあっても気づけません。それがデメリットとなります。
作成や修正に時間がかかる
人の手による作成や修正には時間がかかります。
デイサービスやデイケアでは、利用者が体調不良などでお休みする場合はよくあります。その都度、送迎表は修正が必要か判断し、必要であれば時間をとって修正しなければなりません。
少しの修正であっても、容易ではないのが送迎表の作成です。担当者にとっては、毎日の修正も負担となります。
より良いルートを探そうとする職員が多い
同僚は出来上がった送迎表をじっくりと確認し、より良いルートを探そうとすることが多いです。これが担当者にとってはストレスとなります。
システムを活用することによるメリット
もっと簡単に、もっと高性能な送迎表の作成を目指している方は、AIやシステムを活用した作成方法も検討されているでしょう。
そこでシステムを活用した場合のメリットを紹介します。
送迎表の優劣をつけやすい
今まで送迎表の優劣はどのようにしていますか。時間内に送迎が間に合ったかなど、実際にルートを走ってうまくいくかどうかで判断していませんか。
システムを活用した場合は、総距離や総時間、必要な送迎車の台数などを把握できます。それらを比較することで送迎表の優劣をつけられます。より良い送迎表を目指す場合には、このような数字での比較が必要です。
気づかなかったルートが見つかる
AIを活用した送迎表の作成では、気づかなかったルートが見つかることもあります。今までのルートよりも、さらに良いルートを見つけるには人力では限界があります。
最適なルートでコスト削減
最適なルートの送迎表を作成できれば、ガソリン代の節約につながりコスト削減となります。また職員の時間の節約にもつながり、その時間を利用者へのケアに充てることで満足度も高まるでしょう。
利用者や家族に到着時間を伝えられる
システムを利用するメリットは、到着時間が把握できる点です。利用者や家族のなかには、送迎がくるのを今か今かと待っている方もいます。事前に到着時間を連絡できれば、利用者や家族の満足度を上げられるでしょう。
ルートがわかりやすい
マップを活用したシステムであれば、送迎ルートがわかりやすいです。新人職員への説明もしやすく、送迎業務における職員の負担を軽減できるでしょう。
送迎表の作成はシステム導入がオススメ

送迎表の作成は、NP困難といわれ最適化問題のなかでも難解な部類となります。
そのため人の手が作成するよりは、システムなどを活用して作成するのがオススメです。作成時間を短縮できたり、ガソリン代を節約できたり、利用者や家族の満足度が向上したりとメリットが多いためです。
システムは様々な会社が開発しており、サービスも充実しています。それらを活用することで、送迎表を作成する担当者の負担を軽減するだけではなく、利用者にとっても便利な介護施設となるでしょう。
・Python
https://www.python.org/
・Google OR-Tools Vehicle Routing Problem
https://developers.google.com/optimization/routing/vrp
・Google map API
https://developers.google.com/maps/documentation?hl=ja
ディスカッション
コメント一覧
まだ、コメントがありません