【論文読み】灯油配送計画問題の近似最適化における車両別配送地域の決定戦略の検証

はじめに

こんにちは。読んだ論文の紹介記事です。
今回紹介するのは、「灯油配送計画問題の近似最適化における車両別配送地域の決定戦略の検証」という論文です。

• タイトル： 灯油配送計画問題の近似最適化における車両別配送地域の決定戦略の検証
• 出典： 人工知能学会 第127回知識ベースシステム研究会(2022)
• URL： https://www.jstage.jst.go.jp/article/jsaikbs/127/0/127_11/_pdf/-char/ja

概要

本研究では、配達エリアを決定するアルゴリズムと灯油配達計画問題に対する手法を提案する。灯油消費データに基づく実験では、実際の配達時間よりも総作業時間を36%短縮した計画の実現可能性が示された。
本論文では、現状の配送地域よりも良い配送地域を作成し、配送業務に関わる内容の均等化や全体の配送計画の効率化を目標に、配送地域の決定戦略を提案する。
タンクローリーを1台に制限した設定での灯油配送計画問題についてそれぞれの配送地域で解を求め、1配送業者が扱う地域全体での配送計画を評価する。

特徴

• 配送地域の決定戦略

  • 配送地域の決定戦略において考慮すべき内容としては、合計給油量や総配送件数、総移動距離といった作業時間に影響を及ぼす数値であり、これらを均等化することを考える。
  • デポ距離、クラスタ中心距離の2つを考える。まずはこれらの数値を使って求まる評価関数について、重みパラメータを掛けた和として定義する。

• 灯油配送計画問題

  • ローリングホライズン方式とは、在庫配送計画問題(IRP) をはじめとするスケジューリングを行う最適化問題において、最適化する期間を区切り、区切った区間において問題を新たに作成、最適化し、得られた解を適用しながら次の区間へスライドさせていく手法である。以下の２つのパラメータがある。本論文ではW=Sとする。
    • 次の計画開始日を決めるために何日間スライドするかを決定するステップサイズW
    • 下位問題の計画期間を決める値としてウィンドウサイズS
      　　- タブサーチメタヒューリスティクスの1種であり、近傍探索による解の改善（移動操作）をメモリに記憶し、記憶された移動操作を禁止することによって、局所解への停滞を回避する手法である。

• 実験結果

  • 提案手法によって得られた配送計画は、配送履歴から得られた配送計画よりもより少ない作業時間となっていることが分かる。
  • 残量しきい値を現状に合わせたインスタンスでは、最も良い作業時間が 5.62時間であり、配送履歴から作成した配送計画と比べて17%の作業時間を削減可能であることが分かる。
  • また、残量しきい値を低く0.3に設定した結果については、最も良い作業時間が 4.34 時間となっており、配送履歴から作成した配送計画と比べて、36%程度作業時間を減らせていることが分かる。

想定される適用例

• 様々な配送の最適化

参考

• 灯油配送計画問題の近似最適化における車両別配送地域の決定戦略の検証