DEIM Forum 2017 A5-2

道なりを考慮した配送計画問題の検討
岡田 拓也†

山本 大介†

高橋 直久†† 名古屋工業大学大学院工学研究科情報工学専攻 〒 466–8555 愛知県名古屋市昭和区御器所町
E-mail: †okadat@moss.elcom.nitech.ac.jp, ††{yamamoto.daisuke,naohisa}@nitech.ac.jp
あらまし オンラインショッピングの普及により配送業が生活に欠かせない存在になっている。その配送業が取り決めている配送ルートは巡回経路問題である。この問題では運送コストが最小になることを目的とした問題であり、基本的には距離を最小化することを目指している。しかし、その場合右左折の回数が増えることがある。特に大型トラックといった運転をするのが難しい車では、この右左折での事故が発生しやすい。またストップ・アンド・ゴーの回数も増え、CO2 の量も増加する。さらに曲がる場所を勘違いする認知的なコストが増加するという点も挙げられる。そこで道なりのルートを定義して、これに沿った配送ルートを考える。ここでいう道なりのルートとは、まっすぐ進むルートや緩やかに曲がる一本道のカーブと、曲がった時、進行方向の変化が少ないときのことを言う。この道なりのルートを考えることで右左折の場所を減らすことができ、前述のようなリスクやコストを減らすことも期待される。
そのアプローチは、各地点間のルートを探索するとき曲がった時の角度がある一定の角度を超えたときに右左折回数を１カウントとし、これをコストとして考える。これを踏まえて配送ルートを決定していく。
キーワード

巡回経路問題, 道案内, 地理情報システム

1. は じ め に
1. 1 研究の背景

内に到着できない場合は、運送コストにペナルティーが加算される [1]。
また配送するトラック１台に積載制限と、それぞれの顧客にAmazon や楽天市場といったオンラインショッピングが大き配送する荷物の重さを設ける容量制約付き配送問題という問題く普及し、その利用回数が増えている。利用者が購入した商品もある。移動に要するコストはもちろん、トラック使用によるは、佐川急便やヤマト運輸などの配送業が請け負っており各利コストを含めた運送コストの最小を目指した問題である [2]。

用者を巡っている。利用回数の増加に伴い、多くの利用者の元道なりに関する研究としては、道なり道路をストロークと呼へ向かわなければなくなり、より効率の良い配送ルートを決めび、ストロークネットワークを構築し、その上で道なり優先経る必要が出てきている。この配送ルートの決定は配送経路問題

路探索手法を用いてストローク数が最小となるような経路を求に当てはめて考えることができる。

めるシステムを開発したものもある [3]。

配送経路問題とは、あらかじめ出発地が決められており、そオンラインショッピングでは時間指定を都合に合わせて設定

こからすべてのノードを１回ずつ訪れて、１周するための最短することはできるが、今回は配送時間の指定を考慮しない。まルートを求める最適化問題のことである。似たような問題に巡た積載については１台ですべての顧客を巡ることができるもの

回経路問題があるが、これは出発地が明確にされていない。ことする。

れらの問題では運送コストを最小にすることを目的とした問題

1. 3 道なりの定義

であり、基本的には総移動距離が最小になるように配送ルート

道なりという表現は、人の感覚によって様々である。多少のを決めることが多い。しかし距離に注目していると、曲がる回角度を曲がったり、緩やかなカーブを進む場合を道なりとする数が増えることがある。この回数が増えると、曲がる場所を勘場合や、一切の右左折を緩さずまっすぐに進むルートを道なり違いする認知的なコストが増加したり、右左折待ちによる渋滞とする場合もある。

も増える。また右左折による事故が多いため、その発生も起きやすくなる。
そこで考えられるのが、道なりに進むという考え方である。
道なりに進むことによって、右左折の回数を減らすことができ、前述の認知的なコストを削減することが可能となる。本研究では、配送ルートの取り決めにおいて、この回数を減らすために道なりに進む巡回経路を生成することを目的とする。

1. 2 関 連 研 究

この論文で定義する道なり道路とは、簡単のために基本的にまっすぐ進むルートを道なりとする。また右左折の回数が少なく、右左折が発生した場合でもその進行方向の変化が少なくなるようなルートとする。

2. 手法

2. 1 使用する道路データのデータ構造
本研究で用いる道路データは OpenStreetMap(以下 OSM)

巡回経路問題では、配送へ向かう場所に配送時間を指定すると呼ばれる、地理情報データを誰でも利用、作成できることを場合がある。設定の仕方の一例として、何時から何時までとい目的としたプロジェクトで作成されているデータである。このう時間枠 (time window) を設けた問題がある。時間指定の範囲

OSM では、次のようなデータ構造となっている [3]。

データ名型

説明

id

int

道路につけられている ID

clazz

int

道路のクラスsourceint

リンクの始点ノードの ID

targetint

リンクの終点ノードの ID

x1

doubleリンクの始点ノードの経度

y1

doubleリンクの始点ノードの緯度x2

doubleリンクの終点ノードの経度

y2

doubleリンクの終点ノードの緯度km

doubleノード間の道路の長さ (km)arc

LineString
表1

道路の形状を表す

道路データの表

clazz で表記される道路のクラスとは高速道路や、国道、主

図1

巡回経路問題の具体的な解法の流れ2. 3 提案手法 1

要地方道や一般道を識別するためのデータである。道路の形状先ほどの通り、２地点間のそれぞれのルートを決定する際、は arc によって表現されており、急なカーブや緩やかなカーブ最短ルートを求めるために、距離をコストとしたダイクストラを表現することができる。本研究では、道路のクラスはなく全法を用いることが多い。ての道路が同じ種類であるとし、リンクについては arc は考え道なりに進むように配送ルートを決定したいため、図 1 のず始点と終点だけで道路を表現しているものとして考える。

「ダイクストラ法による２点間ルート生成」でコストを曲がっ2. 2 従 来 手 法

た回数に置き換えたダイクストラ法に変更する。なお曲がった

まず２地点間のそれぞれのルートを決定する。このとき最短回数は、進行方向を変える際に どのくらい向いている方向がルートを求めたいのでダイクストラ法を用いる。次に、ダイク変わったのかの角度を計算し、それが基準よりも大きければ曲ストラ法によって決定されたルートを使って、どの順番で訪れがった回数として数える。

るべきなのかを求める。この問題を解く手法として、次のような方法がある [4] [5]。

•地点間のルートが決まったら配送順番の決め方は既存と同じく、距離が最短となるように配送ルートを決定する。

局所探索法 (2-Opt 法)

求めた近傍解が暫定解より良い解が得られたら更新をする方法。二つのエッジを選択し、それぞれの結んでいる場所を交換する 2-Opt 法を用いる。局所解に陥りやすいという欠点を持つ。

•焼きなまし法

温度パラメータ T を用いて、局所探索法では受理されなかった暫定解より悪い近傍解を確率で受理する方法。最初 T を大きい数字に設定し、試行回数を増やしつつこのパラメータの数値を減らしていきながら、解を収束させていく。

•タブー探索図 2 提案手法の考え方

タブーリストと呼ばれるキューに状態遷移時の操作を残しておき、そのリストに含まれる操作は実行しないようにすることで、局所解から抜け出して解を求めていく。

•遺伝的アルゴリズム選択

生物における遺伝のメカニズムを応用した手法。初期の個体を元にして、選択、交叉、突然変異の操作を繰り返しながら解を求める。
この手法を用いて解を求める。まず、訪れるべき場所をランダムに決める等して初期解を生成する。この初期解から上記のような手法で訪れる順番を変更して、配送ルートを更新する。
この更新を指定された回数行い、それを暫定解とする。そして再び初期解を生成し、同様に配送ルートを更新し現在の暫定解と比べて解がより良いものになれば暫定解を更新する。この操作も指定された回数実行する。解き方の流れは下の図 1 のとおりである。

2. 4 提案手法 2
既存手法や提案手法 1 では、配送する順番次第で、設定した中間地点に到着して次の場所へ向かうときに、先ほど通った道へ戻らなければなり、折り返ししなければならなくなる。広い道や駐車場が確保されている場合は折り返しが可能だが、狭い道や一方通行が指定されている場合、折り返しをすることができず、まっすぐに進むことを余儀なくされる。
そこで、生成された配送ルートを折り返しが起きないような配送ルートに修正する。修正の対象は、中間地点に到着して次の場所へ向かう２地点間のルートである。ルートの変更方法は、中間地点に到着する直前に通った道を除いた状態で再びダイクストラ法を実行し、新しいルートを決定する。
提案手法を実装することにより、図 4 のように折り返しが発験で用いる地図は、中心を緯度 35.154527 経度 136.933917 とした地図から指定された１４か所とスタート地点を決定した。
図 6 にあるように、白い丸をスタート地点およびゴール地点とし、黄色い地点を途中訪れなければならない中間点として設定した。

図 3 提案手法の流れ (道なり修正)生したルートを次のように修正することができる。青い矢印は実際に通るルートで、白い丸はノード、黒い線はリンク、黄色い丸は中間地点を表している。この例では下のノードから２か所の中間地点へ向かう例で考える。

図6

実験で用いた地図とその地点と道路実験で用いる手法は次の４つである。従来手法と、修正の有
図 4 提案手法の例

2. 5 提案手法 3提案手法 2 では見つけた最良のルートに修正を加えることで距離は当然増加するが、それが必要以上に遠回りになってしまうことが多い。そこで最良解だけでなく、２番目に良いルートや３番目に良いルートといった複数の配送ルートを準備しておき、それらを提案手法 2 と同様の修正を行って、その中から一番良いものを配送ルートとする。

無などの違いで提案手法を３つ提示する。

•従来手法

距離をコストとしたダイクストラ法により２地点間のルートを決定する。

•提案手法 1

曲がった回数をコストとするダイクストラ法により２地点間のルートを決定する。道なりに進む修正はしない。

•提案手法 2

提案手法 1 に加えて、道なりに進む修正をする。

•提案手法 3

提案手法 2 に加えて、複数の配送ルートを修正しその中から最良の配送ルートを決定する。
実行結果は毎回変化するので、試行回数は２０回とする。距離と曲がった回数を計測し、それをグラフ上にプロットし、平均をとる。なお、今回の右左折の基準は 60 度曲がった時を１回とする。

3. 2 実 験 結 果
まず、距離と曲がった回数をグラフ上にプロットした結果を
図 5 提案手法の考え方 (複数の候補による道なり修正)示す。グラフは図 7 に表されている。なお、グラフ上に存在する楕円は分布を示したものであり、80%等確率楕円となって3. 評 価 実 験いる。
いずれの提案手法も、既存手法に比べて距離は長くなり、曲

3. 1 実 験 概 要

がった回数は少なくなった。プロットした点、特に移動距離がこの実験で使用しているサンプルプログラムは murase-nit

6〜6.2km に注目すると、同じ移動距離でも提案手法により、と呼ばれる OSM を使った研究をするためのものである [7]。実少ない曲がった回数で配送ルートが実現できるのがわかった。

図7

プロットと分布結果分布に着目すると提案手法１，３は、ほぼ同じ分布をなしているが、道なりの修正の影響で提案手法３の方が少し距離が長くなっている傾向がある。一方、提案手法２は同じ道なり修正をした提案手法３と比べると、分布がとても広くなっていることがわかる。１つの解を修正するよりも複数の解を修正すること

図 8 既存手法結果 (距離 6.050km, 右左折回数 40 回)

により、ある程度解を収束することができたと考えられる。
続いて、各手法における距離と曲がった回数の平均を表に表す。

手法移動距離 (km) 曲がった回数 (回)

従来手法

6.005

40.85

提案手法 16.22127.35

提案手法 26.456

29.75

6.327

28.25

提案手法 3

表 2 ２０回平均の結果

平均距離を見ると、提案手法１は 200m ほどのわずかに長くなった。一方曲がった回数は 35%減少した。平均距離の増加がわずかに対し、曲がった回数は大幅に減らすことができたので、かなり効率的な巡回経路を生成することができたと考えられる。道なりを修正した提案手法 2,3 は、折り返しを回避する手法をとっているためその分、曲がる回数が増えたところもあ

図 9 提案手法 1 結果 (距離 6.309km, 右左折回数 30 回)

るが、曲がった回数の平均は提案手法１と比べてもわずかな増加である。
最後に生成された配送ルートを比べてみる。実行結果は毎回変化するので生成されたルートの１つをそれぞれの手法で挙げる。なお生成されたルートは水色で表示している。なお、提案手法 3 については複数の候補を修正してその中から最良のルートを見つけるため、生成されるルートそのものは提案手法２とほとんど変わらないため省略する。
それぞれの手法の配送ルートを結果を比べると、提案手法は既存手法 (図 8) に比べて複雑な右左折が少なくなった。特に地図の北側のルートは、その改善がよくみられる。提案手法 2,3では提案手法 1 で起きた折り返しのルートをなくすことができた。
一方、提案手法 2 では図 10 のようなルートもあったが、図7 のように、生成された修正前の配送ルートよりも大きく結果が悪くなるような配送ルートも多く生成された。
図 11 は、その一例で修正前の距離が 6.376km、曲がった回数は 28 回だったが修正により、距離が 6.713km、曲がった回数は 33 回となった。この問題点については、提案手法 3 で実装した複数の候補解を道なりの修正をすることで修正後の配送ルートが極端に悪くなるのを避けることができた。図 7 の結果の通り、修正を行う提案手法 2 の分布の広がりを、同じく修正を行う提案手法 3 では、解の広がりをある程度抑えている。

4. お わ り に曲がった回数の比較によるダイクストラ法により、道なりに進むルートを生成することができた。また折り返しによる方向転換を、生成されたルートを修正することにより、より道なりに進むルートにすることができた。その際、修正前に求めた最文

献[1] 谷口栄一, 山田忠史, 細川貴志. 都市内集配トラックの配車配送計画の高度化・共同化による道路交通への影響分析. 土木学会論文集, No. 625, pp. 149-159, 1999.
[2] 中村有克, 谷口栄一, 山田忠史, 安東直紀. 顧客間の複数経路を考慮した配車配送計画問題に関する研究. 土木計画研究発表会・講演集. No.77, 2008.
[3] ストロークネットワークを用いた道なり優先経路探索法の実現
新帯里奈, 山本大介, 高橋直久平成 27 年度電気・電子・情報関係学会東海支部連合大会 2015 年 09 月 - 2015 年 09 月
[4] 山崎紘揮, 宗久知男, 宗久保子. 巡回セールスマン問題への確率的状態選択法: 集団的焼きなまし法 (学生セッション, 大学の ai・企業の ai). 電子情報通信学会技術研究報告. KBSE, 知能ソフト
ウェア工学, Vol. 106, No. 618, pp. 33-35, 2007.
[5] 青 木 健, 井 上 裕 介, 海 野 紘 旭, 高 橋 伸 典. 巡 回 セ ー
ル ス マ ン 問 題 の 解 法, ２ http://www.info.kanagawau.ac.jp/ hatori/study/yousi2004-5.htm

図 10

図 11

提案手法 2 結果 (距離 6.390km, 右左折回数 31 回)

提案手法 2 による配送ルートの修正による悪化の例 (距離6.713km, 右左折回数 33 回)

良解だけでなくそれより少し悪いいくつかの候補解を選び、修正による極端に解が悪くなる事態を抑えることができた。
しかし、図 11 のように右左折の頻度が増えてしまい、必要以上に遠回りになることもある。今後の課題としては、修正の方法を見直し改善して、右左折が極端に増えてしまうようなルートの生成を防ぐことである。また、今回曲がった回数の基準を６０度に設定して実験を行ったが、道なりかどうかの基準は人の感覚により違いが発生するためこの基準についても検討をする必要がある。
本研究は JSPS 科研費 26330136，25700009，科学技術振興機構 CREST，および，総務省 SCOPE の助成を受けたものです．

[7] GitHub - murase-nit sampleProgramOsm OpenStreetMap
を 使った 研 究 を す る た め の サ ン プ ル プ ロ グ ラ ム
https://github.com/murase-nit/sampleProgramOsm