個人車両問題の近似的乗組共有【JST・京大機械翻訳】

Gu Qian-Ping; Liang Jiajian Leo; Zhang Guochuan

プレプリント

J-GLOBAL ID：202202201288010994 整理番号：21P0041888

個人車両問題の近似的乗組共有【JST・京大機械翻訳】

Approximate Ridesharing of Personal Vehicles Problem

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年07月29日プレプリントサーバーでの情報更新日： 2021年05月30日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

乗り分け問題は,トリップのセットを与えられた場合,各トリップは,個人の車両,およびいくつかの要件から成り,トリップの部分集合を選択し,選択されたトリップの車両を使用して,すべての個人を要求条件を満たす目的に送る。トリップの要件は,ソース,目的地,車両容量,運転者の優先経路,迂回距離,および運転者の停止回数を含むパラメータによって指定され,運転者は,時間制約を準備する。2つの最適化問題の時間複雑性とパラメータの間の関係を分析した:選択された車両の数を最小化し,車両の全走行距離を最小化する。次の条件を考察した。(1)すべてのトリップは,同じソースまたは同じ目的地を持ち,(2)迂回は許されない,(3)各参加者は,1つの好ましい経路,(4)停止の数に制限がない,そして(5)すべてのトリップは,同じ出発と同じ到着時間を持っている。両最小化問題は,条件(1),(2)および(3)が満足されない場合,NP困難であることが知られている。両問題はNP困難であり,さらに,もし条件(4)または(5)が満たされないならば,一定因子内で両方の問題を近似するNP困難であることを証明した。条件(4)が満たされないとき,選択した車両の数を最小にするためのK+2/2近似アルゴリズムを与え,そこでは,Kがすべての車両の最大容量である。【JST・京大機械翻訳】

, , , , , ,
, , , , , 【Automatic Indexing@JST】

輸送方法・施設

, , ,

前のページに戻る