A Compressed Annealing Approach with Pre-Process for the Asymmetric Traveling Salesman Problem with Time Windows

The asymmetric traveling salesman problem with time windows (ATSP-TW) is a problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. The problem of reverse link cost is called asymmetric. We propose a modified compressed annealing approach which has a pre and post processes to get a suboptimal solution within practical computation time for the large size problem. 1. 序論 巡回セールスマン問題 (Traveling Salesman Problem,TSP) とは,ある都市を出発して,全ての都市を ちょうど一度ずつ訪問するとき,その移動距離が最小 となる都市の巡回順序を求める問題である.これは組 合せ最適化問題の典型的な問題である [1]. 巡回セールスマン問題をグラフG = (V,A)を用いて 表すと,枝上のコスト cij が与えられたとき,点集合 V の全ての要素をちょうど一度ずつ経由する巡回路 (ハミ ルトン閉路)のうち,コストの合計を最小にするものを 求める問題となる.Aは点同士を結ぶ枝の集合である. 数式で表現すると,ρを V = {1, 2, . . . , n}から V 上へ の 1対 1の写像として