◎イーウィン エース・大沢　裕（埼玉大）

現在地から最終目的地に向かう途中で，いくつかの種類の施設を訪れる際の最適旅行経路を求める問題は，旅行計画と呼ばれる．この検索は，一般に訪れる施設の種類が多い場合，演算量が急速に増大する．本稿では，この旅行計画を道路網距離で求める近似アルゴリズムを提案する．提案アルゴリズムは，まずユークリッド距離により候補ルートを探し，それを道路網距離で検証するものである．提案アルゴリズムは，その生成検証の過程で探索打ち切りの処理時間を指定することができ，指定された処理時間内での準最適解を求めることができる．また，実際の旅行が提案経路から逸れた際の再計算も高速に実行できる．