著者

松田 善臣 名嘉村 盛和 姜 東植 宮城 隼夫

出版者

一般社団法人 電気学会

雑誌

電気学会論文誌C(電子・情報・システム部門誌) (ISSN:03854221)

巻号頁・発行日

vol.124, no.7, pp.1507-1514, 2004 (Released:2004-10-01)

参考文献数

18

被引用文献数

2 2

---

The paper treats an optimal routing problem for sightseeing (ORPS) in which we consider time varying travel time and location value. ORPS is defined on a complete graph in which location values are associated with node weight while travel time depends on edge weight. The aim of the problem is to construct a path with maximal total value under the condition that the total travel time does not exceed a time limit. In our model, the location value and the travel time are given as functions with respect to time. For the case that all the time functions are represented as piece-wise constant, we verify its ΝΡ-completeness.We present an algorithm to find the exact solution based on the backtrack searching and also propose a heuristic algorithm based on the time domain decomposition approach. The heuristic algorithm can lead good quality of approximate solutions, with drastically reduced computation time. To evaluate the algorithms, a computational experiment is given. The experimental results demonstrate that computing time by exact algorithm grow exponentially with the increase in nodes and time limits, whereas the heuristic approach derive approximate solution of 92% quality to the exact one within one second for practical problem size.