時間制約付き巡回セールスマン問題（TSP-TW: Traveling Salesman Problem with Time Window constraint）について調査した．TSP-TWは，各点の訪問時間に制約のある巡回セールスマン問題（TSP: Traveling Salesman Problem）で，NP困難に属する．時間帯指定のある宅配業者の経路最適化など，実応用が期待される研究分野である．

近似解法としては，アントコロニー法を始めとするメタヒューリスティクスが提案されている．厳密解法としては，整数線形計画問題による定式化が提案されている．

巡回セールスマン問題

まず，TSP-TWのベースとなる，TSPについてまとめる．

定義

TSPは，\(n\)個のノードを一度ずつ訪れて最初のノードに戻ってくる1，最短の巡回路を求める問題である．対称TSP（任意の二ノード間の距離が対称）の場合，巡回路の総数は\(\frac{(n-1)!}{2}\)であり，ノード数が30以上になると最適解を求めるのは現実的に困難である．

厳密解法

TSPを整数計画問題として定式化すれば，小規模な問題であれば厳密解を求められる．定式化のバリエーションとして，以下の三種類を見つけた2ので，それぞれ紹介する．なお，以下では簡単のため無向グラフ\(G=(V, E)\)，つまり対称TSPを想定するが，それぞれ容易に非対称TSPに拡張可能である．

接続行列を用いた定式化

まずは，参考文献[1]で紹介されていたもの．

\[\begin{align} \mathrm{Minimize:} & \mathbf{c}^{T}\mathbf{x} & \tag{1.1}\\ \mathrm{Subject~to:} & \mathbf{A}\mathbf{x} = \mathbf{2} & \tag{1.2}\\ & \sum_{e \in E(W)} x(e) \leq |W| - 1, &W \subset V, W \neq \emptyset \tag{1.3}\\ & x(e) = \{0, 1\}, &e \in E \tag{1.4} \end{align}\]

ただし，\(e \in E\)はエッジ，\(\mathbf{c} \in \mathbb{R}^{\mid E \mid}\)は各要素\(c(e)\)がエッジ\(e\)の距離に対応する所与のベクトル，\(\mathbf{A} \in \mathbb{R}^{\mid V \mid \times \mid E \mid}\)は所与の接続行列である．ここで接続行列\(\mathbf{A}\)の各行はノード\(v \in V\)に，各列はエッジ\(e \in E\)に対応しており，ノード\(v\)がエッジ\(e\)の端点なら\(A_{ve}=1\)，そうでなければ\(A_{ve}=0\)となる．\(\mathbf{x} \in \mathbb{R}^{\mid E \mid}\)は各要素\(x(e)\)がエッジ\(e\)が巡回路に含まれるかどうかを表す変数であり，TSPではこれを最適化する．

式(1.3)は部分巡回路除去制約と呼ばれ，全点を通らない部分的な巡回路を防ぐためのものである．

距離行列を用いた定式化

次に，参考文献[2]で紹介されていたもの．

\[\begin{align} \mathrm{Minimize:} & \sum_{ij}c_{ij}x_{ij} & \tag{2.1}\\ \mathrm{Subject~to:} & \sum_{j}x_{ij} = 1, & i \in V \tag{2.2}\\ & \sum_{i}x_{ij} = 1, & j \in V \tag{2.3}\\ & u_i + 1 - M (1 - x_{ij}) \leq u_j, & i, j \in V \tag{2.4}\\ & 1 \leq u_i \leq |V| -1, & i \in V \tag{2.5}\\ & x_{ij} \in \{0, 1\}, & i, j \in V \tag{2.6} \end{align}\]

ただし，\(i, j \in V\)はノード，\(c_{ij} \in \mathbb{R}\)はノード\(i\)-\(j\)間の所与の距離，\(M\)は十分大きな数であれば何でも良い．また，\(x_{ij} \in \mathbb{R}\)はノード\(i\)-\(j\)間を結ぶエッジが巡回路に含まれるかどうかを表す変数，\(u_{i} \in \mathbb{R}\)はノード\(i\)の訪問順序を表す変数であり，TSPではこれらを最適化する．

式(2.4)は，式(1.3)と同様に部分巡回路を除去するための制約式であり，ポテンシャル制約と呼ばれる．

到着時刻を用いた定式化

最後に，参考文献[3]で提案されていた，TSP-TW向けの定式化から，時間帯制約を抜いて単純化したもの3．

\[\begin{align} \mathrm{Minimize:~} & x_{n+1} \tag{3.1}\\ \mathrm{Subject~to:~} & x_{i} \geq t_{0i}, & i \in \{1, 2, \dots , n\} \tag{3.2} \\ & x_{n+1} - x_{i} \geq t_{i0}, & i \in \{1, 2, \dots , n\} \tag{3.3} \\ & x_{i} - x_{j} \geq t_{ij} - My_{ij}, & i,j \in \{1, 2, \dots , n\} \tag{3.4} \\ & x_{j} - x_{i} \geq t_{ij} - M(1-y_{ij}), & i,j \in \{1, 2, \dots , n\} \tag{3.5} \\ & y_{ij} \in \{0, 1 \}, & i,j \in \{1, 2, \dots , n\} \tag{3.6} \\ \end{align}\]

ここで，\(i, j \in V\)はノードのインデックス，\(n\)は始点と終点を除いたノード数，\(t_{ij} \in \mathbb{R}\)はノード\(i\)-\(j\)間の所与の移動時間，\(M\)は十分大きな数であれば何でも良い．また，\(x_{i} \in \mathbb{R}\)はノード\(i\)への到着時刻を表す変数，\(y_{ij} \in \mathbb{R}\)はダミー変数であり，TSPではこれらを最適化する．

式(3.4)および式(3.5)は，以下の非線形制約条件を無理やり線形化したものである．

\[\left| x_{i} - x_{j} \right| \geq t_{ij}, ~~ i \in \{2, 3, \dots , n\}, 1 \leq j < j\]

近似解法

参考文献[1]によると，切除平面法で一旦TSPをLPに緩和し，次に変数が整数条件を満たすように，有効な一次不等式を加えていくらしい．

メタヒューリスティクスとしては，遺伝的アルゴリズムや量子アニーリングなどが使われているみたい．必要があれば，別途記事にするかもしれない．

時間制約付き巡回セールスマン問題

定義

TSP-TWは，TSPの各ノードに到着時刻の制約を付けて拡張したものである．

厳密解法

線形な定式化は，私の調べたところ，参考文献[3]しか見つからなかった．

\[\begin{align} \mathrm{Minimize:~} & x_{n+1} \tag{4.1}\\ \mathrm{Subject~to:~} & x_{i} \geq t_{0i}, & i \in \{1, 2, \dots , n\} \tag{4.2} \\ & x_{n+1} - x_{i} \geq t_{i0}, & i \in \{1, 2, \dots , n\} \tag{4.3} \\ & x_{i} \geq a_{i}, & i \in \{1, 2, \dots , n\} \tag{4.4} \\ & x_{i} \leq b_{i}, & i \in \{1, 2, \dots , n\} \tag{4.5} \\ & x_{i} - x_{j} \geq t_{ij} - My_{ij}, & i,j \in \{1, 2, \dots , n\} \tag{4.6} \\ & x_{j} - x_{i} \geq t_{ij} - M(1-y_{ij}), & i,j \in \{1, 2, \dots , n\} \tag{4.7} \\ & y_{ij} \in \{0, 1 \}, & i,j \in \{1, 2, \dots , n\} \tag{4.8} \\ \end{align}\]

ここで，\(i, j \in V\)はノードのインデックス，\(n\)は始点と終点を除いたノード数，\(t_{ij} \in \mathbb{R}\)はノード\(i\)-\(j\)間の所与の移動時間，\(a_{i} \in \mathbb{R}\)はノード\(i\)の所与の訪問可能開始時刻，\(b_{i} \in \mathbb{R}\)はノード\(i\)の所与の訪問可能終了時刻，\(M\)は十分大きな数であれば何でも良い．また，\(x_{i} \in \mathbb{R}\)はノード\(i\)への到着時刻を表す変数，\(y_{ij} \in \mathbb{R}\)はダミー変数であり，TSPではこれらを最適化する．

式(3.1)-(3.6)との違いは，時間帯制約を表す式(4.4)および式(4.5)である．

近似解法

参考文献[4]によると，主に動的計画法（参考文献[5]，[8]，[10]），Compressed annealing法（参考文献[6]，[9]），Ant colony法（参考文献[7]，[9]）などを使ったアプローチが提案されているようだ．

感想

実用上，非常に面白い問題だが，意外と論文数は多くなかった4．

参考文献

  1. 藤澤克樹，他，応用に役立つ50の最適化問題，2009
  2. Qiita，巡回セールスマン問題から始まる数理最適化
  3. I. Kara and T. Derya, Formulations for minimizing tour duration fo the traveling salesman problem with time windows, Procedia Economics and Finance 26 (2015) 1026 -1034, 2015
  4. H. Kona, A review of traveling salesman problem with time window constraint, IJIRST Volume 2, Issue 01, 2015
  5. K. Fagerholt and M. Christiansen, A traveling salesman problem with allocation, time window and precedence constraints-an application to ship scheduling, International Transactions in Operational Research, Vol 7, Issue 3, pp 231-244, 2000
  6. J. W. Ohlmann and B. W. Thomas, Compressed-annealing heuristic for the traveling salesman problem with time windows, Informs Journal on Computing, vol 19, Issue 1, 2007
  7. C.-B. Cheng and C.-P. Mao, A modified ant colony system for solving the travelling salesman problem with time windows, Mathematical and Computer Modeling, Vol 46, Issue 9-10, pp. 1225-1235, 2007
  8. R. Baldacci, et al., New state-space relaxations for solving the traveling salesman problem with time windows, Informs Journal on Computing, Vol 24, Issue 3, 2011
  9. M. L.-Ibanez, et al., The travelling salesman problem with time windows: adapting algorithms from travel-time to makespan optimization, Applied Soft Computing, Vol 13, Issue 9, pp. 3806-3815, 2013
  10. J.-Q. Li, A bi-directional resource-bounded dynamic programming approach for the traveling salesman problem with time windows, 2009

  1. 最初のノードと最後のノードが異なるパターンのTSPも研究されている． ↩

  2. 多分他にもある． ↩

  3. 時間帯制約の除外に加え，\(t_{i}\)を\(x_{i}\)に変更したり，\(x_{0}\)を式中から削除したり，（個人的な）わかりやすさのために一部修正した． ↩

  4. 私の検索スキルが足りないだけかもしれないが． ↩