GS1-3-5

複数巡回セールスマン問題における交錯評価の検討○片田喜章 （摂南大学）
概要 複数巡回セールスマン問題を解くことで得られる巡回路を複数ロボットの目標経路として採用する場合，経路が交錯することによる衝突の可能性を考慮しなければならない．本研究では複数巡回セールスマン問題で従来採用されている評価指標と併用する，経路交錯の評価指標を検討する．
キーワード: 巡回セールスマン問題，経路計画，複数ロボット

1

∑

はじめに

近年，カーロボティクス 1) やドローン 2) に代表されるロボット分野では，GNSS や SLAM3) といったハードウェアとソフトウェアの要素技術の発展が目覚ましい．これらを利用して大域情報から創出される地図上で経路計画・行動計画を立案し，計画した行動を実行する流れにある．また，これらの技術は単体のロボットに適用されることが多いが，現時点で 1 台の価格が高いロボットであっても，将来的に量産化が進み普及すれば価格は下がり，複数台のロボットを用いてより効率的に作業を行うように移行すると予想される．
本研究では，ロボットのような実世界で身体をもつエージェントを想定した，複数巡回セールスマン問題(Multiple Traveling Salesman Problem: MTSP) を対象とする．分割して得られる巡回路を複数ロボットの目標経路として採用する場合など，経路が交錯することによる衝突の可能性を考慮しなければならない．そこで，本研究では複数巡回セールスマン問題で従来採用されている評価指標と併用する，経路交錯の評価指標を検討する．

2

cij xij(1)

xij = 1, ∀i ∈ I(2)

xij = 1, ∀j ∈ I(3)xij ∈ {0, 1}, i, j = 1, 2, . . . , n, i ̸= j

(4)

∑s.t.

3

i=1 j=1,j̸=iと書ける 4) ．ここで，L は巡回路に含まれる経路のコストの総和，cij は都市 i, j 間のコスト，n は都市数，xij
は都市 i から j への経路の有無を表す．
つぎに，m 人のセールスマンで巡回する都市群を分割する場合を考える．k 番目のセールスマン (k ∈{1, 2, · · · , m}) が担当する都市集合を Ik とすると，I1 ∪I2 ∪ · · · ∪ Ik ∪ · · · ∪ Im = I となり，かつ Ih ∩ Ik =ϕ ∀h, k, h ̸= k とする．m 人巡回セールスマン問題はつぎのように書ける．
m
∑
k=1

s.t.

Lk =
∑m ∑∑

∑

cij xij(5)xij = 1, ∀i ∈ Ik , ∀k(6)xij ∈ {0, 1}, i, j = 1, 2, . . . , n, i ̸= j

(9)max Lk − min Lk
max Lk(10)

交錯回避評価法

MTSP に関して様々な研究がなされているが，セールスマンが実体を伴い，巡回路の交錯がセールスマン同士の衝突を意味するような問題の場合，これを回避するように経路を計画する必要がある．都市群の位置が 2 次元平面における座標で与えられる問題の場合，MTSP で得られる巡回路は 2 次元平面内の連続する線分で構成される経路となる．MTSP でセールスマン同士の衝突の可能性があるのは，この経路が交錯する箇所である．衝突を考慮する 1 つのアプローチは，この線分の交錯が経路として現れないように計画することである．一般的な MTSP で都市の経路が対称な問題の場合には巡回方向や時系列的なセールスマンの位置を考慮することはない．一方，本研究が扱う問題設定では，これらを検討対象とする．上述のように，巡回路同士で交錯しないように計画することは可能であると思われるが，各巡回路が交錯していても，そこを同時間に通過しなければ衝突は起こらない．これは上述のすべての線分の交錯が経路として現れないように計画する問題に比較して緩和された問題となる．
以上を考慮して，本研究では，Tsubouchi ら 8) によって開発された移動ロボットの衝突回避アルゴリズムの考え方を採用する．以下でこれを説明する．空間の Z軸方向に時刻 t をとり，任意のセールスマンの位置をPk (t) = (xk (t), yk (t), t) で表す．セールスマン a と bの位置をそれぞれ Pa (t) と Pb (t) で表すと，|Pa (t) −Pb (t)| < R であれば a と b は接近し衝突の可能性があると判定する．ここで，R を衝突判定距離とよぶ．これにより，x, y, t 空間において，(xk (t), yk (t)) を中心とi,i̸=jmin L =(8)(5)(10) 式が，一般的な MTSP で評価される指標である．

j,j̸=i∑xij = 0, ∀i ∈ Ih , ∀j ∈ Ik , ∀h, k, h ̸= k

ρ=

一般の巡回セールスマン問題は，都市の集合を I ={1, 2, · · · , n} とすると，nn∑∑(7)

ここで，Lk は k 番目のセールスマンが担当する巡回路に含まれる経路のコストの総和を表す．したがって，
m 人巡回セールスマン問題では全員分のコスト L を評価する．さらに，各セールスマンのコストをなるべく均等化したい．このため，Lk に関する最大値や平均値6)，分散，標準偏差 7) を評価することが多い．本研究では，つぎの評価指標 5) を採用する．

複数巡回セールスマン問題

min L =

xij = 1, ∀j ∈ Ik , ∀ki∈Ik ,i̸=jk=1 i∈Ik j∈Ik ,j̸=ij∈Ik ,j̸=iシステム ･ 情報部門学術講演会 2020 (2020年11月15日 -17 日･ オンライン開催 )275

20SY0008/0000-0275 © 2020 SICE

アー間で同じ色は同じ時間帯であることを表す．つまり，同じ色が交錯していなければ，衝突は起こらないことを意味する．
つぎに 1379 都市問題で得られた結果を Fig.3，Fig.4，Table 2 に示す．ρ = 0.142 となり，51 都市問題よりも小さい値となった．また，都市数が多い問題の方が交錯数は多くなると予想されるが，本 1379 都市問題では，巡回方向の全組合せで交錯数は 0 となった．
出発都市を都市群の中心付近に設定する MTSP と比べて，本研究の問題設定では一般的に経路同士の交錯数は多くなると予想される．また，m を大きくした場合の結果も考察する必要がある．つぎに，巡回方向を考慮しても 0 にならない場合や ρ を小さくするために，都市群の適応的な分割法を多目的最適化の観点から検討していきたい．

し，半径 R の円が時間経過によって通過する領域は斜円柱とよばれる領域を構成する．よって，この斜円柱が他の斜円柱と領域を共有していれば衝突が起こる可能性がある．本研究では，各セールスマンは同じ速さで移動すると仮定する．そして，巡回行程でセールスマン同士が接近して衝突の可能性が生じる回数，つまり，セールスマンの経路を円の中心とする，複数の斜円柱の交錯数 Collision を交錯に関する最小化すべき評価指標として設定する．

4

問題設定

本研究で取り扱う問題では，2 節で述べた一般的なMTSP の設定を踏襲し，3 節で述べた評価指標を併用する．さらに下記の設定を行う．

1. すべてのセールスマンは共通の出発-帰還都市をもつ (以降，まとめて出発都市とよぶ)．

6

2. 出発都市は，出発都市以外の都市配置がつくる凸包の外側に位置する．
3. 各セールスマンの巡回方向を考慮する．
異なる出発都市を設定することは，例えば，その位置まで人がロボットを配送することを意味し，本研究の想定にそぐわない．そこで，1. により，共通の出発都市を複数移動ロボットの初期位置に設定する．同様の考え方により，2. は人が訪問できない，もしくは訪問しにくい場所に複数移動ロボットを派遣することを想定しているためであり，全都市が形成する多角形の外側にロボットの初期位置を設定する．3. はセールスマン同士の衝突，つまり，時系列的な経路の交錯を考慮しているため，巡回路を巡る向きを逆にすれば衝突を回避できることがあるためである．各セールスマンの巡回路 (サブツアー) は一般的に交錯しない経路の方が短いと考えられるため，良い巡回路が得られるという想定のもとで，巡回方向に関しては各サブツアーで正回転，逆回転の 2 通りを考える．

5おわりに

本稿では，複数巡回セールスマン問題において，セールスマン同士の衝突を避けることを目的として経路交錯の評価指標を検討した．そして，TSP ベンチマークの 2 つの問題に対し，k-means 法と concorde を用いた手法を適用し，MTSP で一般的な指標と経路交錯の指標を評価した．今後，他のクラスタリング手法の適用およびセールスマン数の増加を行い，様々な TSP ベン
チマーク問題に対して MTSP で一般的な指標と経路交錯指標の評価を行っていきたい．

参考文献
1) 永井，ラクシンチャラーンサク：カー・ロボティクス,
ZMP パブリッシング (2010)2) 吉田：飛躍するドローン，ニッケイ出版 (2016)3) 友納：SLAM 入門, オーム社 (2018)4) 山本，久保：巡回セールス問題への招待，朝倉書店（1997）

計算機実験

本稿では，巡回する都市を m 人のセールスマンで分割するクラスタリング問題と，分割された都市内のサブツアーを計画する問題を分けて考える 9) ．クラスタリング手法として，k-means 法を適用する．ここで，出発都市は k-means 法によるクラスタリングの対象としない．また，サブツアーのソルバーとして，concordeを適用する 10) ．m = 3 とし，TSP のベンチマーク 11)の中から，eil51(以下，51 都市問題) と nrw1379(以下，1379 都市) の問題に適用した．最も巡回路長が大きかったサブツアーを等間隔に 1000 分割した長さを単位時間に進む距離とすることで，すべてのサブツアーに同じ時間軸を設定する．
51 都市問題で得られた結果を Fig.1，Fig.2，Table 1に示す．Fig.1 は得られた巡回路を示し，色の違いは担当したセールスマンの違いを表す．Table 1 に得られた評価値を示す．ρ = 0.353 となり，偏りが大きい値となっている．巡回方向の全組合せ 23 のうち，交錯数の最小値は 0(Table 1)，最大値は 12 であった．Fig.2 に時系列に沿った巡回路を示す．黒色が出発時を表し，経路に沿って時間発展的に黒から赤色に近づく．サブツ

2765) 渡邊，小野，松永，金川，高橋：ファジィc-means 法を用いた複数巡回セールスマン問題の一解法，13-1, 119/126(2001)
6) I. Vandermeulen, R. Groß, A. Kolling: Balanced
Task Allocation by Partitioning the Multiple Traveling Salesperson Problem, In Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), 1479/1487 (2019)7) 坂本，延寛，鈴木，山本，古川，渡辺：局所クラスタリ
ング組織化法による n-TSP に解法，2008 年度精密工学会北海道支部学術講演会講演論文集，35/36 (2008)8) T. Tubouchi, T. Naniwa, S. Arimoto: Planning andNavigation by a Mobile Robot in the Presence of Multiple Moving Obstacles and Their Velocities, Journalof Robotics and Mechatoronics, 8-1, 58/66 (1996)
9) X. Xu, H. Yuan, M. Liptrott, M. Trovati: Two Phase
Heuristic Algorithm for The Multiple-travelling Salesman Problem, Soft Computing, 22, 6567/6581 (2018)
10) Concorde
TSPsolver,
http://www.math.uwaterloo.ca/tsp/concorde/11) TSPLIB,
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

subtour1
subtour2
subtour3

subtour1
subtour2
subtour3

Fig. 1: Best tour for k-means clustering in eil51.tsp

Fig. 3:
Best tour for k-means clustering innrw1379.tsp

Fig. 2: Best tour for time series in eil51.tsp

Fig. 4: Best tour for time series in nrw1379.tsp

Table 1: Evaluation for eil51.tsp

Table 2: Evaluation for nrw1379.tsp

L1
L2
L3
L
ρ
Collision

228
163
252
643
0.353
0L1
L2
L3
Lρ
Collision

277

23807
22418
20419
66644
0.1420