第1回 ORコンペティション課題

日本全国の46都道府県にある拠点間輸送の中継ルートの最適化を行います。

概要

日本全国を対象として、拠点間輸送の最適化を行うことを想定する。輸送ネットワークには46都道府県に配置された拠点が存在し、各都道府県の拠点から他の46都道府県の拠点への荷量が設定されている。各発着拠点間の荷量については、平均値と標準偏差が与えられるものとする。

拠点間の輸送は、8時間以内で走行可能な区間に限って実施できるものとし、遠距離輸送となる場合には複数回の中継を行う必要がある。各区間の輸送手段はトラックとする。このとき、どのように中継を行うかを決定対象とし、各着拠点ごとに次に向かう拠点を定めるものとする。なお、次拠点の選択は発拠点には依存しないものとする。以上の条件のもとで、車両コストの期待値を最小化することを目的とする。

詳細

入力データ

都道府県情報

prefectures_46_excluding_okinawa.csv

problem-linehaul\case\problem\prefectures.csv

• 都道府県コード、都道府県名、緯度、経度
• prefecture_code
• prefecture_name
• latitude
• longitude

荷量データ

virtual_prefecture_flows.csv

problem-linehaul\case\problem\virtual_prefecture_flows.csv
発着都道府県間平均荷量、標準偏差

• origin_prefecture_code
• origin_prefecture_name
• destination_prefecture_code
• destination_prefecture_name
• virtual_load
• standard_deviation

区間移動時間距離情報

truck_distance_time_long.csv

problem-linehaul\case\problem\truck_distance_time_long.csv
都道府県間のトラック輸送距離・時間

• origin_prefecture_code
• origin_prefecture_name
• destination_prefecture_code
• destination_prefecture_name
• distance_km
• time_min

コスト定義

区間荷量の定義

各区間 $aa$ の平均荷量と標準偏差を、そこを通る OD 荷量の平均荷量と標準偏差から集計

区間平均荷量:

$m{u}_a={\sum }_{od}virtual\mathrm{\_}loa{d}_{od}mu\_a\; =\; \backslash sum\_\{od\}\; virtual\backslash \_load\_\{od\}$

区間分散:

$va{r}_a={\sum }_{od}standard\mathrm{\_}deviatio{n}_{od}^{2}var\_a\; =\; \backslash sum\_\{od\}\; standard\backslash \_deviation\_\{od\}^2$

区間標準偏差:

$s{d}_a=\sqrt{va{r}_a}sd\_a\; =\; \backslash sqrt\{var\_a\}$

車両コストの定義

荷量分布

平均 $m{u}_{a}mu\_a$ 、標準偏差 $s{d}_{a}sd\_a$ の正規分布に従うものとします。
$L_a\sim Normal(m{u}_a,s{d}_a^2)L\_a\; \backslash sim\; Normal(mu\_a,\; sd\_a^2)$

車両数

車両の最大積載量を100,000として必要台数を切り上げで計算します。区間を利用する限り荷量は0にならないとして1台割り当てるものとします。
$N_a=max(1,ceil(L_a\mathrm{/}100,000))N\_a\; =\; max(1,\; ceil(L\_a/100,000))$

車両数期待値

荷量の分布と車両数の計算から、車両数の期待値を計算します。
$E[N_a]E[N\_a]$

区間費用

平均車両数と区間の車両単価から区間の費用を計算します。
$cos{t}_a=E[N_a]\times vehicle\mathrm{\_}cost\mathrm{\_}per\mathrm{\_}tri{p}_{a}cost\_a\; =\; E[N\_a]\; \times \; vehicle\backslash \_cost\backslash \_per\backslash \_trip\_a$

各区間の車両単価:

車両の単価は区間の移動時間に比例する物として、1時間あたり1万円とします。
$vehicle\mathrm{\_}cost\mathrm{\_}per\mathrm{\_}tri{p}_a=10,000\times time\mathrm{\_}mi{n}_a\mathrm{/}60vehicle\backslash \_cost\backslash \_per\backslash \_trip\_a\; =\; 10,000\; \times \; time\backslash \_min\_a/60$

詳細情報

詳細は
https://github.com/opthub-org/problem-linehaul
から取得してください。clone先のディレクトリーは漢字を含まない場所にしてください。

git clone https://github.com/opthub-org/problem-linehaul.git

詳細な説明はORコンペティション課題説明.pdfを確認してください。