運搬経路問題とは?

Weblio 辞書 > 学問 > OR事典 > 運搬経路問題の意味・解説 

運搬経路問題

読み方うんぱんけいろもんだい
【英】:vehicle routing problem (VRP)

概要

デポ(depot)と呼ばれる特定の施設待機する運搬車によって, 顧客需要運搬(または収集)し, 再びデポに戻る. このとき顧客位置需要量・作業時間, 利用可能な運搬車台数ならびに運搬車最大積載量最大稼働時間, 地点間の移動時間・移動距離・移動費用などが与えられたとき, 総移動時間・総移動距離・総移動費用・必要な運搬車台数などを最小化する顧客訪問順(ルート)を求め問題.

詳説

 運搬経路問題 (vehicle routing problem) 配送計画問題, トラック配送問題, 配送問題, 輸送経路問題)とは, デポ(depot)とよばれる特定の施設待機する運搬車によって, 顧客需要運搬(または収集)する最小コストルート求め問題総称である [3].


図1:運搬経路問題の概念図

図1:運搬経路問題の概念図


 運搬経路問題の適用分野には, 店舗への配送, 郵便新聞配達, ゴミ収集, 航空機路線決定乗務員スケジューリング等の広範囲領域対象として含まれる.

 以下に代表的構成要素に基づく分類を示す.


1. デポ数に基づく分類
デポ数が単一複数かに分類される.
2. 運搬車種類に基づく分類
運搬車区別をしない場合(等質:homogeneous)と区別をする場合(非等質:heterogeneous)に分類される.
3. 顧客上で作業内容に基づく分類
積み込みまたは積み下ろしのみか, 積み込み・積み下ろし混合分類される.
4. 顧客への到着時刻に基づく分類
(a) 到着時刻に指定なし
通常の運搬経路問題に対す仮定である.
(b) 到着時刻が指定
運搬車スケジューリング問題 (vehicle scheduling problem)とよばれる. バス運行スケジュール飛行機乗務員スケジューリング問題 (crew scheduling problem)への応用をもつ.
(c) 到着時刻が何時か何時までと時間(time window)で指定
時間枠付き運搬経路問題 (vehicle routing problem with time windows)とよばれる.
5. 需要発生する場所に基づく分類
(a) 顧客(点)上
通常の運搬経路問題に対す仮定である.
(b) (ネットワーク上の2点間)上
巡回問題(arc routing problem)とよばれ, 郵便配達人, 除雪車道路清掃車巡回経路求め問題への応用をもつ. 巡回問題は対象とするネットワークに応じて, 郵便配達人問題 (postman problem)または中国郵便配達人問題 (Chinese postman problem), 田舎郵便配達人問題(rural postman problem)等に分類される.

 また上記の他に, 顧客訪問するパターンの中から1つ選択し, 一定期間におけるルート最適化目的とした多期間運搬経路問題(multi-period vehicle routing problem), 顧客訪問する頻度運搬関わる費用顧客上で在庫費用とのトレードオフによって制御する在庫運搬経路問題 (inventory vehicle routing problem)等のバリエーションがある.

 運搬経路問題のバリエーションのほとんどはNP困難(NP-hard)であり, 多項式時間の厳密解法絶望視されている[4] . 近似解法としては, 古典的なものとしてセービング法 (saving method)(クラーク・ライト法, 節約法)が挙げられる. 多く近似解法は, 顧客グループ(クラスター)に分割した後に, 個々クラスターに対してルート設定する解法, クラスター先・ルート後法(cluster-first/route-second method)に基づいている. クラスターへの分割に関しては, 1970年代には 領域分割法 (region partitioning method)が中心に用いられており, 1980年代以降には一般化割当法 (generalized assignment method), 漸近最適性をもつ施設配置ヒューリスティック (location based heuristic) [2] の有効性認識されている. また1990年代には, 得られる解の精度だけでなく現実問題対す頑健性よりメタ解法(meta-heuristics)が注目され, 解法実装に関しては, GIS (geographic information system)を中心とした情報技術との連携による構築導入事例評価されている [1].




参考文献

[1] J. Braca, J. Bramel, B. Posner and D. Simchi-Levi, "A Computerized Approach to the New York City School Bus Routing Problem," IIE Transactions, 29 (1997), 693-702.

[2] J. Bramel and D. Simchi-Levi, "A Location Based Heuristic for General Routing Problems," Operations Research, 43 (1995), 649-660.

[3] G. Laporte and I. H. Osman, "Routing Problems: A Bibliography, " Annals of Operations Research, 61 (1995), 227-262.

[4] J. K. Lenstra and A. H. G. Rinnooy-Kan, "Complexity of Vehicle Routing and Scheduling Problems," Networks, 11 (1981), 221-227.





英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「運搬経路問題」の関連用語

運搬経路問題のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

S002

VS46H/1DV

アオミノウミウシ科の1種4

天城山水源の森

ウォータードリップ

822SH

刺しゅう枠

キャスケット





運搬経路問題のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2017 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2017 Weblio RSS