最適観光経路問題とその解法
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人 電気学会の論文
- 2004-07-01
著者
-
宮城 雅夫
琉球大学工学部
-
Miyagi Hayao
The Faculty Of Engineering University Of The Ryukyus
-
姜 東植
琉球大学工学部情報工学科
-
宮城 隼夫
琉球大学 工学部
-
名嘉村 盛和
琉球大学 情報工学科
-
松田 善臣
琉球大学 大学院 理工学研究科
-
姜 東植
琉球大学 工学部 情報工学科
-
名嘉村 盛和
琉球大学 工学部情報工学科
関連論文
- 4)非対称半平面マスクを持つ2次元格子形フィルタとその安定性について(〔放送方式研究会 マルチメディア情報処理研究会 映像表現研究会 ネットワーク映像メディア研究会 画像情報システム研究会〕合同)
- 3)3次元格子形フィルタとスペクトル解析への応用(〔放送方式研究会 マルチメディア情報処理研究会 映像表現研究会 ネットワーク映像メディア研究会 画像情報システム研究会〕合同)
- 3次元IIR適応格子形フィルタについて
- 2次元非対称半平面格子形フィルタの設計とその安定条件について
- 非対称半平面マスクを持つ2次元格子形フィルタとその安定性について
- 3次元格子形フィルタとスペクトル解析への応用
- 2次元格子形フィルタの安定性に関する一考察
- 2次元格子形フィルターの一設計法
- オブジェクト指向技術を用いた空間データ転送システム「龍潭」の設計と実装
- 分散型地理情報クリアリングハウスの設計に関する検討
- オブジェクト指向技術を用いた簡易地図生成システム
- CST2000-15 オブジェクト指向GISにおける属性データ間引きに基づく最適空間データ転送
- オブジェクト指向GISにおける優先度に基づく空間データ転送
- オブジェクト指向技術を用いた簡易地図生成システムに関する報告
- 転送効率を考慮した空間データの最適間引きの提案
- 分散環境におけるカタログサービスの連携方式に関する一提案
- オブジェクト指向技術を用いた空間データ相互運用システムの設計
- 繰り返し囚人のジレンマゲームにおける競合共進化戦略の解析に関する考察
- 繰り返し囚人のジレンマゲームにおける競合共進化戦略の解析に関する考察
- 免疫細胞間協同作用および抗原との共進化現象を用いた免疫的分業問題最適化手法の提案と評価
- 免疫細胞間協同作用に基づくマルチエージェントの分業最適化に関する考察
- 免疫的問題空間の分割・統合に基づく最適化システムの提案
- (169)JABEE試行審査に挑んで : さらなる改革を目指し(第45セッション 企業における教育・管理者教育,技術者教育認定関連)
- 期待効用を応用したリスク管理型AHP
- D-9-18 リスク管理型ANPに関する一考察(D-9. オフィスインフォメーションシステム,一般セッション)
- 2-E-14 リスク評価を考慮した意思決定問題(AHP(2))
- D-8-14 Newton-Raphson法によるn事象推論システムの構築(D-8.人工知能と知識処理,一般講演)
- ファジィネスを含む不確実性を考慮した演繹推論法
- Pmax-積演算型の可到達行列を用いたシステムの整合性判定
- 通信・放送機構 直轄研究「ロバスト情報配信プラットホームに関する研究開発プロジェクト」
- 「意味フィルタ」を用いた多階層GISの設計と実装(情報・通信)
- 意味フィルタにおける転送空間データのルール生成(情報・通信)
- A-17-36 地理空間データに対する意味フィルタの実装
- A-17-35 ユーザ情報に基づく地理空間データの適応フィルタリング
- 琉球大学HDLデザイン・コンテスト2001結果報告
- ファジィ分類行列による集団意思決定のためのクラスタリング
- 琉球大学HDL・デザイン・コンテスト2000結果報告
- 沖縄県マルチメディア・アイランド構想と琉球大学SOC設計教育
- ねじり荷重を受けるAl合金小穴材のき裂伝ぱに及ぼす油環境の影響
- 平成18年電力・エネルギー部門大会報告
- 紙幣音響データの独立成分分析による正損判別(パターン認識・メディア理解のための学習理論とその周辺)
- ディジタル画像を用いた魚種の識別(画像符号化・通信・ストリーム技術,及び一般)
- ディジタル画像を用いた魚種の識別
- ディジタル画像を用いた魚種の識別
- ディジタル画像を用いた魚種の識別(画像符号化・通信・ストリーム技術,及び一般)
- ディジタル画像を用いた魚種の識別(画像符号化・通信・ストリーム技術,及び一般)
- Tree-染色体構造を持ったGAでの関数同定のための局所探索手法
- ファジィ最適観光経路問題
- D-12-45 ファジィ学習ベクトル量子化法による疲弊紙幣の識別(D-12. パターン認識・メディア理解, 情報・システム2)
- 改良2-opt法における探索領域拡張戦略と動的プライオリティ設定法
- 改良2-opt法を組み込んだ遺伝的アルゴリズムによるQAPの解探索
- 最適観光経路問題とその解法
- 時間変化を考慮した観光経路探索
- A-17-33 時間変化重みを持つ選択的ハミルトン路問題 : 観光ルート探索への応用
- 意味フィルタを用いた空間データの抽出
- Max-min及びMin-maxファジィ関係不等式の一解法
- D-17-17 沖縄マルチメディア・モデルスタジオシステムによる遠隔地間コラボレーション編集
- D-17-16 沖縄マルチメディア・モデルスタジオシステムの構築
- 非対称半平面マスクを持つ2次元格子形フィルタとその安定性について
- 3次元格子形フィルタとスペクトル解析への応用
- A Design Method of an Adaptive Multichannel IIR Lattice Predictor for k-Step Ahead Prediction
- 2次元一般化格子形フィルタの一設計法
- 2次元一般化格子形フィルタの一設計法
- 油中におけるAl合金押出し材の疲労き裂伝ぱ特性
- 琉球大学HDLデザイン・コンテスト2000結果報告
- 相関アルゴリズムを用いたニューラルネットワークによる非線形時系列の推定法
- ECLMS アルゴリズムを用いたARCH誤差項を有する非線形時系列の推定法
- 解のパッケージ化法を導入した競合共進化アルゴリズムの提案
- 共生共進化アルゴリズムの性能解析に関する考察
- 加法形一対比較行列を用いた多目的意思決定
- 区間評定値を用いた指数型ファジィAHP
- 音響信号の振幅差分特徴を用いたサポートベクターマシンによる疲弊紙幣の識別
- D-9-18 満足度を用いたグループ意思決定
- 意思決定問題における直積空間上の測定
- ヒューマン測度に関する基礎研究
- 客観的測度と主観的測度に関する一考察
- 地理情報システムにおける配送経路問題の遺伝的アルゴリズムを用いた解法
- A-17-34 地理シソーラスを用いたキーワード方式での地理空間データ検索
- A Method of Designing Nonlinear Observers for Squirrel-cage Induction Generators in Windmill Power Systems
- かご形誘導機起動時の突入電流抑制法
- 合成演算子を用いたファジィ関係式の解法
- 高速ネットワークを用いた遠隔地間コラボレーション編集
- 高速ネットワークを用いた遠隔地間コラボレーション編集(高速ネットワークとマルチメディアアプリケーション)
- LMS法に基づく2次元適応ボルテラフィルタ
- リアプノフ関数による電力システムのオンライン過渡安定度評価
- 除外のルールを用いたファジィ関係式の解法
- Sup・minおよびInf・max合成ファジィ関係式の解法
- 繰り返し囚人のジレンマゲームにおける共進化戦略に関する一考察
- 2次元IIR適応格子形フィルターの設計法
- 2次元一般化適応格子形フィルタの一設計法
- 戦略パッケージ法を用いた競合共進化による適応型戦略の獲得
- 戦略パッケージ法を用いた競合共進化によるゲーム戦略の獲得
- 5)2次元一般化格子形フィルタの一設計法(〔放送方式研究会 マルチメディア情報処理研究会 映像表現研究会 ネットワーク映像メディア研究会 画像情報システム研究会〕合同)
- 2次元正規化格子形フィルタの一設計法
- 多次元積形非線形フィードバックをもつシステムのロバスト安定性
- n入出力をもつ混合形ファジィシステム方程式の解法
- D-20-3 観光目的に基づいた観光地の価値推定(D-20.情報論的学習理論と機械学習,一般セッション)
- A-13-4 内部統制に関わる不正発生分析のための意思決定機構の構築(A-13.思考と言語,一般セッション)
- A-13-3 ベイズ的決定法を考慮した意思決定(A-13.思考と言語,一般セッション)
- 音響信号の振幅差分特徴を用いたサポートベクターマシンによる疲弊紙幣の識別