OptaPlanner 8 の新しくなった最適化問題のサンプルを動かしてみる

レッドハットのソリューションアーキテクトの森です。
皆様2022年もよろしくお願い致します。

Red Hatのミドルウェアの中には、ビジネスにおける最適化問題を解決するソリューションとして、Business Optimizerというものがあることをご存知でしょうか？

Business Optimizer について

Red Hat Business Optimizer はプランニング問題を解決するAI制約ソルバーです。限られたリソース内で、様々で複雑な制約条件を満たしつつ、最良の結果を得たいというようなケースにおいて、どの組合せが最適なのかを現実的な時間で探索することができます。オペレーションズリサーチの専門的な知識や難解な数式等は不要で、Javaプログラミングとルールの記述でこれらを実現できることが特長です。オープンソースソフトウェア（OSS）コミュニティの OptaPlannerをベースとしており、Red Hat社により製品化をされて、ルールエンジン「Red Hat Decision Manager」の機能の一つとして提供をされています。

昨年、コミュニティ版のOptaPlanner 8がリリースをされて、付属のサンプルも一新されました。今回は、OptaPlanner 8の新しくなったサンプルを紹介したいと思います。

Let's Try!!

JDK11以降を事前にインストールしておいてください。
プロジェクトをローカルにダウンロードしてから実行

プロジェクトはこちらになります。適当なフォルダにて、下記のコマンドを実行してください。

$ git clone https://github.com/kiegroup/optaplanner-quickstarts.git
$ cd optaplanner-quickstarts
$ ./runQuickstartsFromSource.sh

もしくは、こちらのリンクからzipファイル（400MBくらいあります）をダウンロードして、適当なフォルダに解凍し、中のrunQuickstarts.shファイルを実行してください。（Windowsの場合は、runQuickstarts.batファイルを実行）

ターミナルから実行した場合、以下のようなログが表示されれば、起動完了です。

__  ____  __  _____   ___  __ ____  ______ 
 --/ __ \/ / / / _ | / _ \/ //_/ / / / __/ 
 -/ /_/ / /_/ / __ |/ , _/ ,< / /_/ /\ \   
--\___\_\____/_/ |_/_/|_/_/|_|\____/___/   
2022-01-04 16:20:48,499 INFO  [io.quarkus] (Quarkus Main Thread) optaplanner-quickstarts-showcase 8.14.0.Final on JVM (powered by Quarkus 2.5.0.Final) started in 3.187s. Listening on: http://localhost:8080

2022-01-04 16:20:48,513 INFO  [io.quarkus] (Quarkus Main Thread) Profile dev activated. Live Coding activated.
2022-01-04 16:20:48,515 INFO  [io.quarkus] (Quarkus Main Thread) Installed features: [cdi, resteasy, resteasy-jackson, smallrye-context-propagation, vertx, webjars-locator]

ブラウザで、http://localhost:8080/ にアクセスをしてください。サンプルのメニュー画面が表示されると思います。

f:id:ka_mori:20220106152838p:plain:w600 f:id:ka_mori:20220106153318p:plain:w600 f:id:ka_mori:20220106153345p:plain:w600

School timetabling (授業のスケジューリング)
Facility location problem (施設配置問題)
Maintenance scheduling (保守工事のスケジューリング)
Call center (コールセンターの処理時間最適化)
Vehicle routing (配送経路問題)
Vaccination scheduling (ワクチン接種スケジュール最適化)
Order picking (物流倉庫からのピッキング作業最適化)

今回はこの中から、Order pickingについて、解説をしていきたいと思います。

Order picking を動かしてみる

ピッキングとは物流用語で、指定された商品を保管されている倉庫の場所から取り出す作業のことを指しますが、「オーダーピッキング」とは、注文単位（1オーダーずつ）にピッキング作業を行う方法です。他の方法としては、複数の注文に含まれる商品をまとめてピッキングする「総量ピッキング」という方法もあります。

オーダーピッキングは通販系の倉庫で導入されているケースが多く、商品数や発注頻度が高い注文に対して、迅速で柔軟に対応できるという点や、仕分けスペースが不要で、ピッキング後すぐに梱包作業に入れるというメリットがあります。一方で、オーダーごとにピッキングをするため、商品を探す手間がかかったり、倉庫内の移動効率が悪くなったりすることがデメリットとしてあげられます。

本サンプルでは、仮想の物流倉庫に対して、倉庫内の移動距離を最小にしつつ、オーダーに必要な商品を集めるための計画を立てるものになっています。

では、早速サンプルを立ち上げてみましょう。 ▷Launch -> Showをクリックすると、ブラウザの別画面でアプリが起動します。

f:id:ka_mori:20220106153430p:plain:w600

▷Solveをクリックすると、最適化が始まりますが、その前に問題の初期データについて確認をしていきましょう。右上の Map をクリックしてみてください。

縦3行 * 横5列の枠が表示されていますが、これは倉庫の棚を表しています。棚のサイズは縦10m * 横2mで、棚と棚の間隔は3mとなっています。一応、棚のごとに商品のカテゴリーが決まっているようで、以下のようになっています。

f:id:ka_mori:20220106153510p:plain:w600

C1, C2 列は、特に定義はされていないようです。自分でカスタマイズしてみる際には、変更を加えてみてください。倉庫の棚と商品の定義は、以下のソースファイルの中に記述されています。下記にその一例を示します。

./optaplanner-quickstarts/use-cases/order-picking/src/main/java/org/acme/orderpicking/bootstrap/ProductDB.java

...
        SHELVINGS_PER_FAMILY.put(ProductDB.ProductFamily.FRUITS_AND_VEGETABLES, Arrays.asList(
                newShelvingId(COL_A, ROW_1),
                newShelvingId(COL_A, ROW_2)));
...

...
        PRODUCTS.add(new ProductDBRecord(new Product(nextId(), "Iceberg Lettuce Each", 2500, null), ProductFamily.FRUITS_AND_VEGETABLES));
        PRODUCTS.add(new ProductDBRecord(new Product(nextId(), "Carrots 1Kg", 1000, null), ProductFamily.FRUITS_AND_VEGETABLES));
        PRODUCTS.add(new ProductDBRecord(new Product(nextId(), "Organic Fair Trade Bananas 5 Pack", 1800, null), ProductFamily.FRUITS_AND_VEGETABLES));
        PRODUCTS.add(new ProductDBRecord(new Product(nextId(), "Gala Apple Minimum 5 Pack", 25 * 20 * 10, null), ProductFamily.FRUITS_AND_VEGETABLES));
        PRODUCTS.add(new ProductDBRecord(new Product(nextId(), "Orange Bag 3kg", 29 * 20 * 15, null), ProductFamily.FRUITS_AND_VEGETABLES));
...

次に、右上の Unassigned をクリックしてみてください。

商品をピッキングするトロリーと、オーダーの情報があります。

f:id:ka_mori:20220106153534p:plain:w600

初期条件では、トロリーは5台与えられています。それぞれのトロリーに4個のバケットがあり、バケット1つの容量は48000です。

またオーダーは、8つ与えられています。Order_1 のタブをクリックすると、オーダー1に必要な商品の内容が確認できます。

必要な商品の位置は、Warehouse Location に、商品棚、棚の左右、棚内の列位置 の形式で書かれています。

例えば、下記のオーダー1の2番目の商品のバターであれば、(A,3)の棚、左側の上から6番目の位置にある、ということになります。

f:id:ka_mori:20220106153617p:plain:w600 f:id:ka_mori:20220106153626p:plain:w200

トロリーの台数や、バケットの数とその容量、オーダーの数は、以下のソースファイルで設定をしています。

./optaplanner-quickstarts/use-cases/order-picking/src/main/java/org/acme/orderpicking/rest/OrderPickingSolverResource.java

...
    /**
     * Number of trolleys for the simulation.
     */
    private static final int TROLLEYS_COUNT = 5;

    /**
     * Number of buckets on each trolley.
     */
    private static final int BUCKET_COUNT = 4;

    /**
     * Buckets capacity.
     */
    private static final int BUCKET_CAPACITY = 60 * 40 * 20;

    /**
     * Number of orders for the simulation.
     */
    private static final int ORDERS_COUNT = 8;
...

またオーダーの内容については、ProductDB.java に設定された商品データを元に、自動で生成されるようになっています。そちらの詳細について興味のある方は、以下のソースを確認してみてください。

./optaplanner-quickstarts/use-cases/order-picking/src/main/java/org/acme/orderpicking/bootstrap/DemoDataGenerator.java

では、与えられたオーダーの商品をピッキングするための、トロリー移動経路の最適化を実行してみたいと思います。

最適化を実現するための制約条件は以下のようになっています。制約条件の重要度により、レベル分けをすることが可能です。

Hard制約（満たされない場合は計画が破綻するもの）
- 全てのオーダーの商品が選択されていること
- 異なるオーダーの商品が、同じバケットに混在してはいけない
- バケットの容量を超えて、商品を入れることはできない
  - 満たされない場合は Hard制約のスコアを-1
Soft制約（できれば順守したい制約）
- トロリーが移動する距離を最小限にする
  - Soft制約のスコアから移動距離分をマイナス(縦5m、横3mの移動の場合は-8)
- 注文を異なるトロリーに分割してピッキングすることは避ける
  - 各トロリーに割り付けられたオーダーの数の分、 Soft制約のスコアを-1000 とする

制約条件については、以下のソースファイルに記述がされております。参考に 注文を異なるトロリーに分割してピッキングすることは避ける の実装の例を示します。

./optaplanner-quickstarts/use-cases/order-picking/src/main/java/org/acme/orderpicking/solver/OrderPickingConstraintProvider.java

...
    /**
     * An Order should ideally be prepared on the same trolley, penalize the order splitting into different trolleys.
     */
    Constraint minimizeOrderSplitByTrolley(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(TrolleyStep.class)
                .groupBy(trolleyStep -> trolleyStep.getOrderItem().getOrder(),
                        countDistinctLong(TrolleyStep::getTrolley))
                .penalizeLong("Minimize order split by trolley",
                        HardSoftLongScore.ONE_SOFT, (order, trolleySpreadCount) -> trolleySpreadCount * 1000);
    }
...

上記の制約を考慮した上で、どのトロリーがどのオーダーのピッキングをするのか、各トロリーはどのような順序で各棚の商品まで移動するのか、与えられた時間内で最良のスコアとなるように組み合わせを入れ替えます。

それでは、左上の緑の ▷Solve をクリックしてみましょう。各トロリーに、どの注文の商品をどのような順番で取りに行くか、リストが表示されます。また時間の経過とともにリストの内容が更新されていき、それに伴い上部にあるスコアも変化している様子が見えると思います。

f:id:ka_mori:20220106153830p:plain:w300

f:id:ka_mori:20220106154139p:plain:w200 f:id:ka_mori:20220106154156p:plain:w200 f:id:ka_mori:20220106154209p:plain:w200 f:id:ka_mori:20220106154223p:plain:w200

例えば上記の状態では、5台あるトロリーのうち、4台が稼働予定となっています。各トロリーの移動距離はそれぞれ、168m, 132m, 178m, 160m となっており、合計 638m のため、Soft制約のスコアに-638を与えます。

また、トロリー1は、3つのオーダーの商品をピッキングしているので、Soft制約のスコア 3✖️-1000=-3000 を与えます。各トロリーの割り付けオーダーは合計では9となるため、Soft制約のスコアに-9000を与え、移動距離分のスコアと合わせて、-9638となっています。

次に、右上の Map をクリックしてみると、各トロリーの移動経路が倉庫マップ上に表示されていると思います。

f:id:ka_mori:20220106154809p:plain:w600

終わりに

いかがでしたでしょうか？今回は、すぐに触って頂けるサンプルの中から、Order Picking についてご紹介を致しました。

Red Hat Business Optimizer は、企業のビジネスの重要な意思決定である計画策定業務を標準化し、いつ・どこで・誰がやっても高品質な計画を作成を可能にします。また人手作業では困難だった計画の柔軟な変更や、複雑な制約条件の見直しにも迅速に対応し、より効率的な計画策定業務を実現します。

最適化のツールに興味がある・もう少し詳しい内容が聞きたい、などありましたら、是非弊社までお問合せ頂ければと思います。