オプティマインド・松下健氏インタビュー(2/3)「問題を解く」ことの実社会へのインパクト──「配送計画問題」とはなにか?

松下氏インタビュー

 第1回:「技術が現実社会に実装されていない乖離性を埋めたい」──最適化技術を武器に挑戦する企業・業界を超えた「配送地図」の創造

 第3回:なぜ研究だけじゃなく、「起業」が必要だったのか?──ITベンチャーが目指す「現場主義」

「Car 54」懸賞問題(Procter & Gamble)のポスター(1962年)

トゥーディとマルドゥーンが車で全国を回り、課題地図上の丸印で表された33の都市を一つ一つ訪れますが、その際、移動距離はできるかぎり短くしたいとします。2人がイリノイ州シカゴを出発して、またイリノイ州シカゴに戻ってくる合計距離が最短になるようにルートを計画してください。

──「Car 54」懸賞問題,(Procter & Gamble)

※翻訳は『驚きの数学 巡回セールスマン問題,ウィリアム・J・クック(松浦俊輔訳)』より引用

 

131,565,418,466,846,765,083,609,006,080,000,000

 

この数字は、Procter & Gamble(P & G)が広告キャンペーンとして打ち出した懸賞問題の可能なすべての順路の数だ。たかだか33の点を一筆書きでぐるりと一周するにすぎない単純な問題であるが、これらをすべて計算・比較し、最小距離となるただ一つの経路を導き出すとなれば、天文学的な時間を要することになる。これは「解ける」のだろうか?

松下氏率いる株式会社オプティマインドが得意とする組合せ最適化の古典的な問題として有名なのが、この「巡回セールスマン問題」だ。いわゆる「NP困難(NP hard)」と呼ばれる問題のひとつであり、現実的な時間で厳密解を求めることの困難さが大きな課題となっている。それゆえに巡回セールスマン問題をはじめとする組合せ最適化の研究では、最適解を手早く見出すための近似アルゴリズムの開発が盛んに行われている。

 

松下氏 おっしゃられたように「巡回セールスマン問題」っぽいんですけども、実はもうちょっと複雑で「配送計画問題」って言われる問題を扱っています。複数の車両ですとか、複数のデポ(倉庫)から出発して、極力Uターンのないように計算したり、訪問先に対して(駐車が)左付けになるようにですとか、「この訪問先にはこのドライバーさんしか行っちゃいけない」ですとか、「車両と訪問先」や「ドライバーと訪問先」というような制約条件を考慮して計算しています。

 

異質な条件が混ざる制約条件下で「現実的」に問題を解く

──(配送計画問題や)セールスマン巡回問題などでは現実的な時間で厳密解を出せないNP困難クラスの問題に対して、さまざまなアルゴリズムが提案されていますよね。配送計画などの現実の問題に落とし込んだときに、アルゴリズムって向き不向きがあると思うのですが「やってみて良いものを選ぶ」のでしょうか? それとも、(汎用性のある)決定版みたいなものがあるのでしょうか?

 

松下氏 最初はかなり尖ったアルゴリズムを使っていたのですが、いろんなニーズが出てきて拡張するのが大変でした。今は汎用的なものにアルゴリズムに切り替えて、だいたいの制約条件はクリアできるけれど、特定のケースにおいて計算時間がちょっとかかるというものを採用しています。現場の人からすると、0.5秒で解けようが数十秒で解けようがあまり効果は変わらなかったので、アルゴリズムは汎用性のあるものへとシフトしていき、そこをちょっとずつ改良しています。

 

──ルートを出すのに(44分かかっていたのを)6分くらいに短縮できたという話があったのですが、そこの6分とは計算するのに6分まるまる必要だったということですか?

 

松下 日本郵便さんの場合、配達状が電子データ化されていないんですよ。それを入力画面に入力してもらう時間が5分45秒くらいで、計算が15秒くらいです。

株式会社オプティマインドの独自サービス『Loogia』によるルート計算例

 

技術の実社会への実装──それがオプティマインド代表・松下氏が強く抱いている理念だ。大学1年生の頃から切望して入った研究室で組合せ最適化技術の研究をはじめた当初、「研究のための問題設定」であったことに違和感を覚えた。「配送」を徹底的にやろうと決めたのは、技術と現場の乖離を特に感じたからだという。

最適化アルゴリズムの研究は、一言でいえば「問題をどう解くか」についてだ。この「どう解くか」に直結するのが考慮すべき事象を模したパラメータである。

 

──アルゴリズムなどちょっと知っていると「ただの最適化だよね」「ナビでもできるよね」という風に思ってしまいがちなのですが、他にも御社ならではの「独特のパラメータ」ってありますか?

 

松下氏 ナビって基本的には(システムと車両が)1対1なのですが、我々がやっているのは社用台数が何台でも一気に計算できます。また、勤務時間や積載制限なども考慮することで巡回セールスマン問題より一段高いレイヤーの配送計画問題というところで、より「どう解くか」が重要になってきます。プラス、地図に落とし込む部分が必要なので、実測値を元にもう一回地図に落とし込んで……というところで尖らせています。

 

時間制約の厳密さが求められる配送ならではの特徴として「時間枠を柔軟に考慮できる」こともオプティマインドのアルゴリズムの特徴である。

 

松下氏 たとえば宅配便だと、(配達の)午前指定が9時から12時の場合、11時55分に配達するっていうルートを出すとドライバーさんとしては心象が悪いんです。できるだけ午前指定は前の方に詰めたいんですけど、「午前指定だけ先に配って後から他のものを」となると明らかに効率的じゃなくなります。

そこで時間枠の中で区分線形関数っていうペナルティ関数を区分線形で定義しています。配達のコストが最小になるように、極力前詰みに配送するんですけど、無駄のないように配送する、みたいなことをします。これは私が所属する研究室から出ている2005年の論文で、それをベースに作っています。

 

未来の配送に向けた「ハブ・スポーク配送」

 

松下氏 もうひとつが、これ世界一の論文なんですけれど、「ハブスポーク配送」という配送モデルです。

 

アルゴリズムのオリジナリティについて、松下氏は続けてこう語った。

 

松下氏 ヤマトさんのバス停方式をイメージしていただくといいんですけれど、トラックがすべての家を訪問するわけではなくて、ある場所に停車をしてそこからドライバーさんが歩いていったり、あるいは今後、宅配ロボットがまわったりするようなこともあるかもしれません。

バス停方式:2010年頃からヤマト運輸が採用している配達方法。配送ルート内の決まった場所にトラックを一時停車させ、その近隣を生活圏とするスタッフが荷物を取りに来て、配達する。配達車両数・走行距離の低減に成功し、配達業務の効率化に繋がっている。

 

松下氏の着眼は「少ないコストで多くの人に物を届ける」というモデルであり、そこから見た未来像がハブ・スポーク配送になる。配送において、停車位置を減らすことさえできれば諸々の制約条件を軽減することができる。それにより同時に「どこに停めるか」という問題も生じ、また実際に停車するにあたっては「現場の感覚」が極めて重要になる。ドライバーの業務情報をフィードバックして独自の配送地図を作るオプティマインドだからこその技術だと言える。

 

松下氏 車両がわざわざ家を回るのではなく、例えばECマーケットの靴屋さんが移動してきて、みんなが徒歩で歩み寄ってまた違うところへ行くなど、乗り合いバスなど、停める場所は複数あるけれど全部停める必要はない。被覆しなくちゃいけないお客さんのオーダーを効率よく考慮しながら、どれだけ少ない数で停めていくかというモデルです。

配送の未来モデル。ECマーケットのリアル店舗進出や小売業者のEC進出により、「停車地点に人が集まってくる」というモデルも今後考えられる、と松下氏は語る。

 

配送計画問題は、さまざまな異質な事象が複雑にからみあう環境下で「問題を解く」という普遍的な価値を内在している。配送以外の領域への進出を尋ねてみたところ、松下氏は「ないとはいえない」と慎重に回答したが、組合せ最適化技術の汎用性を鑑みると、松下氏の「もっと現場に応用されてしかるべきだ」という主張の説得力が一段と強くなる。

 

次回は株式会社オプティマインドのビジネスにおける挑戦を紹介する。

参考情報

オプティマインド・松下健氏インタビュー(1/3)「技術が現実社会に実装されていない乖離性を埋めたい」──最適化技術を武器に挑戦する企業・業界を超えた「配送地図」の創造

応用数理の遊歩道 (48) NP困難性の35年 :その誕生, 茨木 俊秀, 2007

P, NP, NP困難, NP完全, 田浦健次朗(PDF)

Ibaraki, Imahori, Kubo, Masuda, Uno, Yagiura, Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints, 2005

Takada, Hu, Hashimoto, An iterated local search algorithm for the multi-vehicle covering tour problem, 2015

ヤマト運輸株式会社 グループ全体で地球温暖化防止対策を推進 [エコライフ]

トラック配達の「配送ルート最適化」。実現するのは本当に不可能? [SmartDrive Magazine]

ハブアンドスポーク方式 [流通・小売物流.com]

(インタビュー:Marvin編集部 文:まちゃひこ)

 

まちゃひこ

文筆家。京都大学大学院工学研究科博士課程で熱工学や統計力学の研究を行う。単位取得中退後、求人広告の代理店に勤務したのち独立。創作プロジェクト「大滝瓶太」を主宰し、2018年第1回阿波しらさぎ文学賞を受賞。同年10月中旬発売の文学ムック「たべるのがおそい Vol.6(書肆侃侃房)」に短編小説を掲載予定。

Twitter:@macha_hiko

ブログ:カプリスのかたちをしたアラベスク

 

松下健

1992年生まれ、岐阜県岐阜市出身。名古屋大学情報文化学部を卒業し、名古屋大学大学院情報学研究科博士前期課程修了、博士後期課程に在籍中。 専門は組合せ最適化。

2015年に合同会社オプティマインドを創業。株式会社オプティマインド代表取締役社長。

オプティマインドでは、経営全般、営業、サービス設計、最適化アルゴリズム設計などを行なう。

株式会社オプティマインド