FastDOCTOR Technologies の大畠です。ソフトウェアエンジニアとして社内の業務システムのサーバーサイド・フロントエンドを担当しています。

猫も杓子も ChatGPT 、毎日がシンギュラリティといった今日このごろですが、この記事ではあえて古典的であり十分に枯れている最適化問題という技術について、FastDOCTOR Technologies における取り組みと事例を紹介します。

最適化問題というと、巡回セールスマン問題や最短経路問題などの名前が思い浮かぶのではないでしょうか？あるいは競技プログラミングにおける「最大値を求めよ」といった問題も最適化問題に含められると思います。

ファストドクターの業務においては「限りある貴重な医療リソースを、いかにして効率よく再分配運用するか」も重要なテーマの1つです。感染拡大で医療機関が逼迫したコロナ禍においてはもちろん、これから訪れるであろう超高齢社会においても、このテーマは大きな意義があると思います。だからこそ一人のギークとしては、やや古い技術であり流行りの人工知能のような華々しさはなくても、「地味で質実剛健な雰囲気をもっているこのテーマが現代社会を助けるかもしれない」ということに興奮をおぼえます。

この記事では医療リソースのうち、もっとも重要な人的リソースである「医師」を、いかにして救急往診先の患者の自宅へ効率よく送り届けるのか。つまり組合せ最適化問題とその解法、社内のドメインエキスパートとのやりとりなどを解説します。

現実の最適化問題を解く方法

競技プログラミングでは、たとえばナップザック問題には動的計画法、最短経路問題にはダイクストラ法、二部マッチングには最大フロー問題といった感じで、問題に対して答えを出す方法がある程度決まっています。また、ジャッジサーバーが正誤を判定するという都合から、ただひとつの解が保証されている問題がほとんどです。（余談ですが、二部マッチングについては実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬ という有名な記事があります。これは、私が最適化問題を調べるきっかけになったもので、競技プログラミングの世界でとても著名なけんちょん氏によって執筆されています）

現実の問題は、ただひとつの解が存在すると必ずしも保証されているわけではないですし、競技プログラミングのように美しく整理された問題に帰着させて考えることすら、できない場合が多いです。そこで、ソルバー（Solver）と呼ばれるソフトウェアが開発されています。これは、細かいアルゴリズムを指定することなしに、問題に対する解を出してくれるものです。しかし、その多くは商用のソフトウェアであり、気軽に試すことはできません。

これは Web エンジニアとしては納得のいかなかった点でした。依存するソフトウェアというのはオープンソースか、あるいはスモールスタートできる SaaS のどちらか、というのに慣れきっていたからです。しかし、ソルバーは交通・物流・金融といったエンタープライズ領域の基幹を担うパーツのはずで、そういった前提を踏まえれば多くが商用であることも納得できます。

そう思っていたところ、 OptaPlanner という Java 製のオープンソースのソルバーの存在を知りました。これを使えば、とにかく素早く動かして導入することができ、予算や契約や稟議などの事務コストがいっさい関係なくなります。現状のオペレーションは最適解までどれくらい近いのか、または遠いのかという試算や、実際に社内の基幹となる業務アプリに組み込んで、オペレーションを改善することができるようになりました。

（ちなみに、ソルバーの存在を認めてしまうと「競技プログラミングを勉強しなくても、ソルバーを使えばそれでいいじゃん」とやる気がなくなってしまう方もいるかもしれません。でも、ソルバーは仕組みが複雑でおおげさなものなので、問題の本質を見抜いてシンプルなデータ構造とアルゴリズムで答えを求めるという技術は、コンピューターサイエンスの素養として重要でありつづけると思います。）

問題の設定

ファストドクターでは、救急往診サービスを提供するために提携している医療機関の医師とドライバーの組をエリアごとに毎日配置し、全部で100台以上稼働させています。ある日のあるエリアにおいて、夕方から夜までのシフトで医師とドライバーの組が n 組あるとします。それぞれの組は医師の自宅から移動を開始するとします。このシフトにおいて患者が m 人いるとします。患者はそれぞれまったく異なる場所に住んでいます。

医師とドライバーのシフトスケジューリング問題ではない（そこは人間が決めている。ソルバーが活躍する余地はあるが）複数の往診車（医師とドライバーの組）が同時に稼働している稼働開始時にその勤務でまわる患者が確定しているという強い仮定をおく

いわゆる巡回セールスマン問題のようですが、医師とドライバーの組が複数あるので、全体最適を行う余地があります。まず、当然考えられる制約として「あらかじめ決まっている勤務シフトの枠内で完了できる件数までしか割り振らない」と「総移動距離を最小にする」というものを実装しました。

制約 1 担当する患者の数をシフト内でこなせる量におさめる

さっそく、ソルバーに対して「全体最適化をしなさい」という制約をつけていきたいのですが、まずは前提となる「担当する患者の数をシフト内でこなせる量におさめる」という制約からはじめていきます。というのも、この制約をつけずに全体最適を目指すと、ただひと組の医師とドライバーがすべての患者を効率よく周り、「総移動距離も稼働時間も小さいので最適解です」という結果になってしまうからです。

ソルバーを動かしていると、このような到底許容できない解を無邪気に返してくることがあります。融通の効かないコンピューターと、コンピューターに意図をうまく伝えきれない自分をとてももどかしく感じます。同時に、これを人間がやるとこのような極端な解を出してくることは絶対にないので、人間も捨てたものではないなと思います。技術の進歩は速いので、いつまでこんなことを言っていられるかはわかりませんが。

さて、シフト内に業務量をおさめるとなると業務を時間に換算する必要があります。1往診あたりの時間は問診の結果によりますし、次の患者の自宅へ移動するのにかかる時間も道路の混みぐあいによって変わります。ここは悩んでいても仕方がないので、診察には30分、移動は時速 30 km で、緯度・経度の直線距離から求める、というかなりどんぶり勘定の仮定をしました。

せっかくソルバーを導入したのに・・・という気持ちにもなりますが、ファストドクターが持っている患者や症状に関するデータを蓄積・活用することで改善できるようにも考えられるため、まだまだエンジニアリングの余地があると前向きに思うことにします。

OptaPlanner の面白い点として、最適化の対象となるデータをクエリする言語内 DSL があって、これを使って制約を書くことがあります。以下が OptaPlanner における制約のコードです。 Java のコードでありながら制約を記述するための言語内 DSL が書けるというのが OptaPlanner の面白い点だと思います。

HomeVisit は往診、 Vehicle は医師とドライバーのペア組、 Capacity はシフトの稼働時間を表しています。 OptaPlanner の公式ドキュメントにある Vehicle Routing Problem という問題のサンプルコードをもとにコードを書いているため、こういった変数名をひきついでいます。

Constraint vehicleCapacity(ConstraintFactory constraintFactory) {
    return constraintFactory
            .forEach(HomeVisit.class)
            .groupBy(HomeVisit::getVehicle, sum(HomeVisit::getWeight))
            .filter((vehicle, weight) -> vehicle.getCapacity() < weight)
            .penalize(HardSoftScore.ONE_HARD, (vehicle, weight) -> weight - vehicle.getCapacity())
            .asConstraint("Vehicle capacity");
}

制約 2 総走行距離を小さくする

いよいよ本命の制約です。本当に最適化したいのは移動にかかった時間なのですが、前述のとおりそれをやるには道路の混雑状況や幹線道路・川・橋などの経路案内などを考えなくてはいけなくなり途方もない労力なので、ひとまずは緯度・経度をもとにした直線距離と平均 30km という速度を仮定して進めます。

大胆な仮定をいれてしまったものの、制約を記述するコードはたいへんシンプルに書くことができて、やはりソルバーはこういう最短経路問題や全体最適化のために開発されているのだと感じます。

Constraint totalDistance(ConstraintFactory constraintFactory) {
    return constraintFactory
            .forEach(HomeVisit.class)
            .filter(HomeVisit::isLast)
            .penalize(HardSoftScore.ONE_SOFT, HomeVisit::getTotalDistance)
            .asConstraint("distance from last visit to depot");
}

制約 3 経路最適化問題であることの指定

これは当たり前のことですが、解きたい問題が経路に関するものだということを指定します。

@PlanningVariable(valueRangeProviderRefs = { "vehicleRange", "homeVisitRange" }, graphType = PlanningVariableGraphType.CHAINED)

現場からのフィードバック

そうして、ある日の勤務シフトと往診先の住所データを使ってソルバーに問題を解かせてみました。結果はよかったのですが、医師の救急往診スケジュール配置をする担当のコーディネーターという職種の社員に解を吟味してもらったところ、全く使えないとは言わないまでも、自分がやるときはこうしている、という勘所をいくつか共有してもらいました。

制約 4 医師は勤務終了時にできるだけ自宅に近いところに帰りたい

救急往診する医師の気持ちになったらすぐわかることですが、見出しのように言われてみればその通り！といったフィードバックをもらいました。また、医師によっては自宅ではなくて所属している病院まで送ってほしいという場合もありますし、同じ医師でも日によって自宅に帰ったり、病院に戻ったりするそうです。

Constraint distanceFromLastHomeVisitToDropPoint(ConstraintFactory constraintFactory) {
    return constraintFactory
        .forEach(HomeVisit.class)
        .filter(HomeVisit::isLast)
        .penalize(HardSoftScore.ONE_SOFT, HomeVisit::getDistanceToDropPoint)
        .asConstraint("distance from last visit to drop point");
}

制約 5 拠点となる点からの距離を一定以下にする

患者の自宅までの距離がファストドクターの提携している医療機関から半径16km以外のエリアの場合は、救急往診エリアから除外されているのでそれを制約としても加えておくことにしました。

この距離の上限を 16 km と設定しています。実は保険診療のルールで患者の自宅から遠い場所からの往診にはその必然性が認められず、患者の自宅付近の医療機関が往診すべきということになっていて、その基準が 16 km と決められているのです。

Constraint distanceFromBaseBranch(ConstraintFactory constraintFactory) {
    return constraintFactory
            .forEach(HomeVisit.class)
            .filter((visit) -> 16000 < visit.getDistanceFromVehicleBaseBranch())
            .penalize(HardSoftScore.ONE_HARD)
            .asConstraint("distance from the start point");
}

まとめ

ファストドクターにおいて、ソルバーがどのように適用しているか、ご紹介しました。類題や特殊な状況における個別のアルゴリズムを紹介しました。 OptaPlanner というオープンソースのソルバーの数少ない紹介記事でした。

これまでの制約を課した OptaPlanner に、ある日曜日のあるエリアにおけるシステムの記録から取得した実際の救急往診経路をもとに、最適解と比較をしてみました。

実際の移動距離 (道のり) 5359879m 最適解 (道のり) 4175047m (22%減)

ということで移動距離を 22 % 削減できたという結果が得られました。もちろん他にもまだまだ考慮すべき制約はあるのですが、まずはポジティブな効果が得られ、運用上改善の余地があることがわかったということは収穫です。

ファストドクターにおいて医療リソースを有効活用するための取り組みは重要で、そのために制約充足ソルバーの OptaPlanner を導入しています。ソルバーを利用することで個別の具体的なアルゴリズムをエンジニアが考慮する必要がなくなり、より本質的な改善のための作業に時間を割けるようになります。ドメインエキスパートである現場の担当者からヒアリングしてフィードバックをもらうプロセスを継続することで、医療リソースを数理的に最適に活用できるようになると思っています。