抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
乗り分け問題は,トリップのセットを与えられた場合,各トリップは,個人の車両,およびいくつかの要件から成り,トリップの部分集合を選択し,選択されたトリップの車両を使用して,すべての個人を要求条件を満たす目的に送る。トリップの要件は,ソース,目的地,車両容量,運転者の優先経路,迂回距離,および運転者の停止回数を含むパラメータによって指定され,運転者は,時間制約を準備する。2つの最適化問題の時間複雑性とパラメータの間の関係を分析した:選択された車両の数を最小化し,車両の全走行距離を最小化する。次の条件を考察した。(1)すべてのトリップは,同じソースまたは同じ目的地を持ち,(2)迂回は許されない,(3)各参加者は,1つの好ましい経路,(4)停止の数に制限がない,そして(5)すべてのトリップは,同じ出発と同じ到着時間を持っている。両最小化問題は,条件(1),(2)および(3)が満足されない場合,NP困難であることが知られている。両問題はNP困難であり,さらに,もし条件(4)または(5)が満たされないならば,一定因子内で両方の問題を近似するNP困難であることを証明した。条件(4)が満たされないとき,選択した車両の数を最小にするためのK+2/2近似アルゴリズムを与え,そこでは,Kがすべての車両の最大容量である。【JST・京大機械翻訳】