予測交通量に基づくアントコロニー最適化法による時間依存TSPの解法と広域道路網への適用

IPSJ

Bibliographic Information

Other Title
  • Solving Time-dependent Traveling Salesman Problems Using Ant Colony Optimization Based on Predicted Traffic and Its Application to Wide Area Road Network

Search this article

Abstract

本論文では，予測交通量を用いてアントコロニー最適化法（ACO）で時間依存TSP（TDTSP）を解く手法を提案する．TDTSPとは，旅行時間が変化するタイプのTSPであり，ルーティング問題やスケジューリング問題など，いくつかの現実世界の問題をモデル化することができる．現実のルーティング問題を考えると，都市間の経路を求めてから旅行時間を計算する必要がある．旅行時間の変化間隔で良い解を求めるためには，探索の高速化が必要となるため，ACOのフェロモンの初期値に偏りを与えることで，探索領域の削減を行った．TSPのベンチマーク問題からTDTSPを作成した実験と，現実の道路網と交通量データを用いた実験の結果，提案手法は解の精度を落とすことなく収束が早まっていることを確認した．

In this paper, we propose an ant colony optimization based on the predicted traffic for time-dependent traveling salesman problems (TDTSP). TDTSP is a TSP where travel times between cities changes with time and used as models for some real world problems. In the case of real road networks, the travel time changing is associated with paths between cities and needs to be calculated by a shortest path algorithm. A faster algorithm is required to find the best solution every changing of travel times. The proposed method gives deviations from the initial pheromone trails in order to reduce a search space. Experimental results using benchmark problems and real world data suggested that the proposed method has a faster search rate than the conventional method.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top