配送時間制約を考慮したネットワーク設計問題

配送時間制約を考慮したネットワーク設計問題
Network design problems with delivery time constraints
片山 直登：流通経済大学 流通情報学部 教授

略歴1982年 早稲田大学理工学部卒業、1988年 同大学院博士後期課程単位取得退学。博士（物流情報学）。早稲田大学理工学部助手、金沢工業大学工学部講師、1996年 流通経済大学流通情報学部助教授を経て、2002年から現職。

［要約］ インターネット通販の進展に伴い、宅配便のような企業から個人への配送量が急増し、適切な配送サービスを維持するためには、施設や輸送能力の拡充など根本的なネットワークの再構築が必要となってきている。本研究では、当日配送、翌日配送などの複数の配送時間制約と配送車である資源のバランスを考慮する条件を考慮した資源の配置とフローを求めるアーク設計問題のモデルを扱う。このモデルに対して、配送時間制限の考慮方法の異なるいくつかの定式化、およびフローや資源の表現が異なるいくつかの定式化を提示し、ベンチマーク問題を用いてモデルと定式化による求解の困難性を明らかにする。

キーワード

ネットワーク設計問題、配送時間制約、資源バランス

１

はじめに

る。しかし、ITの進展により膨大な量のビッグデータを把握できる状態であるにも関わらず、企業は日々の大量の荷物の処理業務の対応のため、根本的な配送・輸送ネットワークの見直しが進まない状況となっている。

インターネット通販の進展に伴い、宅配便

配送・輸送などのネットワークの構成は大のような企業から個人への配送量が急増してきく3つのレベルに分類することができる。

いる。人手不足や再配送問題も加わり、ラス

配送センターなどの施設の適切な配置と能力

トワンマイルとよばれる配送センターと顧客設定を決める問題、施設間の輸送路と荷物の間の配送は大きな問題となっている。また、輸送経路を決める問題、および企業・施設間

当日配送、翌日配送などの短納期配送サービ

や施設・顧客間の配送経路を決める問題であスが一般化している。加えて、センター間のる。配置と能力設定を決める問題は施設であ幹線輸送では輸送能力がひっ迫する状況にあるノードの配置とフローを求めるノード設計

る。今後、適切な配送サービスを維持するた問題、施設間の輸送路と荷物の輸送経路を決めには、施設や輸送能力の拡充など根本的なめる問題はノード間の資源の配置とフローをネットワークの再構築が必要となってきてい求めるアーク設計問題、企業・施設間や施設・

140

配送時間制約を考慮したネットワーク設計問題

顧客間の配送経路を求める問題は配送・集荷

et al.（2021）は配送期限を超える需要に対経路問題として表すことができる。これらをしてペナルティ費用を付加するソフト配送時同時に取り扱うことが望ましいが、問題の規間モデルを提案している。

模や複雑性や対象となる期間が異なるなどの一方、配送時間の制限を取り扱ったネット

点から、同時に取り扱うことは困難が伴う。

ワーク設計モデルはそれほど多くはなく、

一般的に、ネットワーク設計問題はアーク

Hellsten et al.（2021）は単一の配送期限の制の設計問題として扱われることが多い限を考慮したモデルに対して、いくつかの定（Crainic et al. 2021）。このアーク設計のモデ式化を示し、列生成法と分枝価格法を用いた

ルでは、ノードをノード間のアークに変換す解法を示している。

ることにより、ノードの設計問題を扱うこと

本研究では、資源の配置とフローを求めるが可能である。ネットワーク設計問題には、アーク設計問題を対象とし、当日配送、翌日

アークの容量を考慮する／ しないモデル

配送などの複数の配送時間制約を考慮した（Crainic et al. 2021）、資源のバランスやスケ

ネットワーク設計問題を扱う。加えて、配送

ジ ュ ー ル を 考 慮 す る モ デ ル（Jarrah et al.

車である資源のバランスを考慮する資源バラ2009, Andersen et al. 2011, Erera et al. 2013,

ンス設計条件と同一品種のフローが１つのパCrainic et al. 2016, Boland et al. 2017）、フ

スを流れる条件を考慮する。このようなモデ

ローが１ つのパスを通るモデル（Atamtürk

ルに対して、配送時間制限の考慮方法の異な

and Rajan 2002, Yaghini and Kazemzadeh

るいくつかの定式化、およびフローや資源の2012, Li et al. 2017）や確率的モデル（Crainic

表現が異なるいくつかの定式化を提示する。

et al. 2011, Bai et al. 2014、Rahmaniani et al.

ベンチマーク問題を用いて、いくつかの定式

2018、Wang et al. 2019）など様々なモデル化について数値実験を行い、問題の条件や定が研究されている。

式化による求解の困難性を明らかにする。

資源のバランスやスケジュールを考慮す
るモデルは配送車などの資源の巡回経路を考慮するモデルであり、時間空間ネットワーク
により資源の巡回スケジュールを求めることができる。一方、ネットワークの構成が与え２モデルの前提条件

はじめに、本研究における前提条件を列挙する。

られたもとで、配送期限を条件として荷物の• ノード集合が与えられる。

流れであるフローを求めるモデルは、コンテ• 向きをもつアーク候補集合が与えられナの海上輸送である定期船輸送の分野で数多くの研究（Karsten et al. 2017, Balakrishnan
and Karsten 2017, Tierney et al. 2019, Koza
et al. 2020）が行われている。また、Trivellaる。
• アーク上には整数個の資源が割り当てられる。
• 資源には決められた容量が与えられる。
141配送時間制約を考慮したネットワーク設計問題• 品種集合が与えられる。

全需要の10%までを当日に配送し、全需要の• 品種ごとの需要量が与えられ、品種は異50%までを翌日までに配送するというようななる始点・終点をもち、始点・終点の対条件を考慮するモデルである。二つ目は、時で表す。

間制限を超える需要に対してはペナルティ費• アーク上を流れるフローに対して、単位用が発生するモデルである。ここでは、非減当たりのフロー費用が与えられる。

少の区分的線形関数をペナルティ費用の関数• アーク上を流れる品種のフローの移動時間が与えられる。
• 同一の終点をもつ品種の需要は、単一の経路上を移動する。
問題により、以下の前提条件のうちのいとする。
モデルの定義は以下の通りである。複数種
類のモデルを扱うため、共通部分を記述する。
ノード集合、アーク候補集合、アークに割り当てる容量・費用をもつ資源集合、始点とくつかを満足する。

終点をもつ品種の需要、各品種の配送時間制• 資源はアークで構成されるサイクル上に限集合が与えられる。フローの単一パス条件

配置される。
• アーク上を使用する資源に対して、単位当たりの固定費用であるデザイン費用がを満たす。このとき、全体の費用合計を最小にするフローおよびアークに割り当てる資源を求めよ。

与えられる。
• 使用する資源に対して、固定費用が与えられる。
配送時間に関しては、次の前提条件のう３

配送時間制限カバー率モデル

はじめに、配送時間の制限を全需要に対す

ちいずれかを満足する。

るカバー率を用いる4つのモデルを示す。4つ• 複数の配送時間の制限が与えられ、それのモデルは、整数デザイン変数とアークフぞれの配送時間の制限を満たす需要のカ

ロー変数を用いたモデル、0-1デザイン変数

バー率の下限が与えられる。

とアークフロー変数を用いたモデル、整数デ• 複数の配送時間の制限が与えられ、それ

ザイン変数とパスフロー変数を用いたモデぞれの配送時間の制限を超える需要につル、整数デザイン変数とアーク通過時間フ

いては、超過時間に比例したペナルティ

ロー変数を用いたモデルである。なお、デザ費用が発生する。

イン変数はアークに配置される資源数を表す

配送時間の制限には、当日、翌日など複数変数の総称である。

の時間制限があるものとする。ここでは、配送時間の制限について2つのモデルを使用す

3.1

整数デザイン・アークフローモデル

る。一つ目は、複数の時間制限を満たす需要

デザイン変数値が0以上の整数値を取り、のカバー率を与えるモデルである。例えば、アークフロー変数を用いたネットワーク設計

142

配送時間制約を考慮したネットワーク設計問題

モデルを示す。

源 に 対 す る 単 位 当 た り の デ ザ イ ン 費 用fij、

ノード集合をN、向きのあるアーク候補集

アーク上の移動時間tij、アーク上の資源の単合をA、品種集合をKとする。ノードnを始位当たりの容量bijが与えられる。ノードnが点とするアークの終点であるノード集合を

品種kの始点okであれば−1、終点d kであればN +n 、ノードnを終点とするアークの始点であ1、それ以外であれば0である定数をekn とする。

るノード集合をN−n とする。配送時間制限のまた、h番目の配送時間制限を満たす需要の集合をHとする。また、0以上の整数の集合

全需要に対する需要カバー率をdhとする。たをZとする。

だし、dh−1<dh（h=2, · · ·, hmax）とする。

品種kは始点ok、終点d kをもち、需要量qk

アーク（i,j）に対して、品種kのフローがアーが与えられ、品種の需要はいくつかのアーク

ク上を流れるとき1、そうでないとき0であるを経由して始点okから終点d kに流れるものとフロー変数をxkij 、アーク上に割り当てられるする。最大の配送時間制限をhmaxとし、配送資源数を表す整数変数である資源数変数をyij

時間制限集合HはH = {1, · · · , hmax} で表されとする。また、品種kの需要がh番目の配送る。h番目の配送時間制限をlhとしたとき、lh

時間制限を満たすとき1、そうでないとき0−1< l（h=
2, · · · , hmax）を満たす。アーク（i,j）
hには、アーク上の単位当たりのフローに対すである時間制限変数をvkh とする。
このとき、整数デザイン・アークフローモ

るフロー費用cij、アークに割り当てられる資デルIDAFは次のようになる。

（1）式は総費用を表す目的関数であり、こイン費用の合計である。yijは整数値をとる資れを最小化する。第一項はアーク上のフロー

源数変数であり、アーク上のデザイン費用は費用の合計であり、第二項はアーク上のデザ

資源数変数に比例して発生する。
（2）式はフ143

配送時間制約を考慮したネットワーク設計問題

ローの保存式であり、始点を発した需要のフを表す式である。左辺は配送時間がh番目のローがいくつかのアークを経由して終点に達

制限時間を満たす需要の合計であり、右辺はすることを表す。xが0-1変数であることから、

満たさなければならない量である。
（7）式と特定の品種が流れるパスは1 本に限定され（8）式は変数の0-1条件であり、（9）式は変る。一般のネットワーク設計モデルでは複数数の整数条件である。

のパスを許す場合が多いが、複数パスを許すモデルに拡張することは容易である

3.2

0-1デザイン・アークフローモデル（Hellsten et al. 2021）。
（3）式は容量制約式

デザイン変数値が0-1値を取り、アークフ

であり、左辺はアーク上を流れるフローの合ロー変数を用いたネットワーク設計モデルを計、右辺は資源数と容量の積であるアーク上示す。

の容量である。
（4）式は強制制約式であり、アーク上の資源を表す整数の資源数変数

アーク上に資源が設定されるときに限り、を0-1変数に分解することにより、より強いアーク上をフローが流れることを表す。一般

定式化を行うことができる。アーク（i,j）に的には強い制約式となるが、この定式化では配置できる資源の集合をSijとする。アーク

資源数変数が整数値をとるため、一般的なモ（i,j）上にs個の資源が配置されるとき1、そデルと比べると弱い式となる。
（5）式は配送

うでないとき0を表す0-1のデザイン変数をysij

時間制限に関する式である。左辺は品種kのとおく。また、アーク（i,j）上のs個目の資始点・終点間の配送時間を表す。右辺は、vkh源を使用する品種kのフロー比率を表す連続が1のときにlhとなりh番目の制限時間を満足変数であるアーク資源数フロー変数をukij s とし、vkh が0のときにlmaxとなり最大の制限時間おく。

を満足することを表す。
（6）式は配送時間制
限を満足する需要が全需要に対するカバー率144

このとき、0-1デザイン・アークフローモ
デルBDAFは次のようになる。

配送時間制約を考慮したネットワーク設計問題（10）式は総費用を表す目的関数であり、となる。
（19）式は変数の非負条件である。

これを最小化する。デザイン費用は資源数にこの定式化は区分的線形費用をもつネッ

比例して発生し、第二項はアーク上に配置さ

トワーク設計問題で用いられている

れるs個の資源のデザイン費用の合計となる。

（Croxton et al. 2003）。この定式化は、アー（12）式はアークフローとアーク資源数フロー

ク容量の強い上限値が与えられる場合に有効の関係式である。左辺はこのアークを使用すなものとなる。一方、アークに配置できる資る品種のフローの比率であり、右辺はこの源数に上限がない場合は、使用する0-1変数

アークを使用する品種の資源に対するフローは膨大なものとなる。

比率の合計を表す。
（13）式は容量の下限の制約式であり、s個の資源を使用するアーク

3.3

整数デザイン・パスフローモデル

上のフローの合計はs−1個の資源数を配置しデザイン変数値が整数値を取り、パスフ

たときの容量以上であることを表す。
（14）

ロー変数を用いたネットワーク設計モデルを

式は容量の上限の制約式であり、s個の資源示す。
kを使用するアーク上のフローの合計はs個の品種kの取りうるパスの集合をP とする。

資源数を配置したときの容量以下であること

品種kのパスpを使用するとき1、そうでないを表す。（17）式は強制制約式であり、アーとき0であるパスフロー変数をzkp とし、パスp

ク上にs個目の資源が設定されるときに限り、がアーク（i,j）を使用するとき1そうでないアーク上を資源sのアーク資源数フローが流とき0である定数をδpij とする。

れることを表す。左辺は0または1をとり、右辺も0または1をとることになり、強い制約式

このとき、整数デザイン・パスフローモデ
ルIDPFは次のようになる。

145配送時間制約を考慮したネットワーク設計問題（23）式は総費用を表す目的関数であり、題を最適に解くための手法であり、最適解まこれを最小化する。Σp∈Pkδpij zkp =xkij であるこたは近似解を求めるためには、別の手法を組とから、第一項はアーク上のフロー費用の合み合わせる必要がある。

計となる。
（24）式はフローの保存式であり、なお、0-1デザイン変数を用いたパスフロー

パスフロー変数が0-1変数であることから、による定式化も可能であるが、ここでは省略

品種kの取りうるパス集合P kから1本のパスする。

を選択することを表す。
（25）式は容量制約式であり、左辺はアーク上を流れるフローの

3.4

整数デザイン・アーク通過時刻フロー

合計、右辺は資源数と容量の積であるアーク

モデル

上の容量の合計である。
（26）式は強制制約

デザイン変数値が整数値を取り、アーク通式であり、アーク上に資源が設定されるとき

過時間フロー変数を用いたネットワーク設計に限り、アーク上をフローが流れることを表モデル（Hellsten et al. 2021）を示す。

す。
（30）式は変数の0-1条件である。

時刻の集合をDとし、品種kがアーク（i,j）

多くのネットワーク設計問題では、このパのノードiから出る可能性のある時刻の集合

スフローによる定式化が使用される。取りうをDkij とする。また、時刻dにノードiを出る

るパスは指数個あるために陽的に列挙するこアーク（i,j）を使用する品種kのフローが存とは困難である。このため、適時、目的関数

在するとき1、そうでないとき0であるアーク

値を減少させるような変数である列を生成す

通過時刻フロー変数をx kij dとする。

る列生成法を使用する。生成する列を求める
問題は最短経路問題または制約付きの最短経路問題となり、効率的に変数である列を生成することができる。列生成法は、線形緩和問
146

このとき、整数デザイン・アーク通過時刻
フローモデルIDATFは次のようになる。

配送時間制約を考慮したネットワーク設計問題（33）式は総費用を表す目的関数であり、ズを縮小することが必要になる。

これを最小化する。第一項は取りうるすべての時刻のフロー費用の合計である。
（34）式
から（36）式はフロー保存式である。
（34）

４

資源バランス設計モデル

式は、中継ノードにおける関係式であり、取これまで示したモデルは、アークに配置す

りうるすべての時刻に対して、ノードに入る

る資源数または容量を決めるモデルであり、フローとノードから出るフローが一致するこ

資源が輸送・配送車の場合には行きの便のみとを表す。ここで、ノードnに入るフローとを考慮し、帰り便は考慮しないモデルとなる。

出るフローにはtinの時間差があることに注意

輸送・配送車は巡回するものとし、巡回路でする。（35）式は、時刻0に始点okから出るフあるサイクルを考慮する、またはノードを出ローの合計が1であることを表す。
（36）
式は、

入りする資源数のバランスを考慮するモデル

そのノードで取りうる時刻について終点d kには資源バランス設計モデル（Pedersen et al.

入るアークフローの合計が1であることを表2009）またはサービスネットワーク設計問題

す。

（Andersen et al. 2009）とよばれている。
ネッ

取りうる時刻は、アーク上の移動時間の公トワークを時間・空間ネットワークとするこ

倍数ではあるが膨大なものとなるため、移動とにより、資源の巡回スケジュールを求める

時間の丸め込みなどにより、時刻集合のサイことも可能となる。
147

配送時間制約を考慮したネットワーク設計問題

4.1

資源バランス・0-1 デザイン・パスフ

ローモデル

また、アーク（i,j）上で、資源rが使用されるとき1、そうでないとき0である資源デザイ

デザイン変数値が整数値を取り、パスフ

ン変数をy rij とする。資源rのタイプが異なり、ローを用いた資源バランス設計モデルを示

容量や移動時間が異なってもよいが、ここです。

はすべての資源は同じタイプとする。

資源の集合をR、資源rが使用されるとき

このとき、整数パスフロー変数を用いた資の固定費用をg rとする。資源rが使用される源バランス設計モデルABDAFは次のようにとき1、そうでないとき0である資源変数をwrなる。

とする。資源rの最大稼働時間をTとする。

（44）式は総費用を表す目的関数であり、生する固定費用の合計である。
（46）式は容これを最小化する。第二項はアーク上で使用量制約式であり、右辺はアークで使用されるする資源デザイン費用の合計である。第三項

資源の合計数と容量の積であるアーク上の容はネットワーク上で使用する資源に対して発量である。
（47）式は強制制約式であり、
アー

148

配送時間制約を考慮したネットワーク設計問題

ク上にいずれかの資源が設定されるときに限としても定式化することができる（Pedersen

り、アーク上をフローが流れることを表す。

et al. 2009）。ここでは、資源サイクル変数を（50）式は資源バランス式であり、資源rがノー

用いた資源バランス設計モデルを示す。

ドに入ればそのノードから出ることになり、資源サイクルはあるノードからいくつか

資源rがノードに入らなければそのノードかのアークとノードを経て、このノードに戻る

ら出ないことを表す。バランス式により、資サイクルであり、このサイクル上を資源が巡源はネットワーク上の巡回路で使用されるこ

回することを意味する。資源サイクルが選択とになる。
（51）式は資源が使われるか否かされると、この資源サイクル上のアークに容を判定する式であり、いずれかの資源デザイ

量が設定される。

ン変数が1であれば、その資源が使用される取りうる資源のサイクルの集合をMとすことを表す。なお、左辺の最大数はアーク数る。なお、Mには同じサイクルが複数含まれとなるため、右辺にはアーク数を係数としてても良いものとする。資源サイクルmを使用

使用している。
（52）式は資源の稼働時間がするとき1、そうでないとき0である資源サイ

最大稼働時間以下であることを表す。

クル変数をgmとし、資源サイクルmを使用する際に発生する固定費用をwmとする。また、

4.2

資源サイクル・0-1 デザイン・アーク

フローモデル
資源バランス設計モデルでは、資源が巡回

資源サイクルmがアーク（i,j）を使用すると
き1、そうでないとき0である定数をϵm
ij とす
る。

路であるサイクルを形成することになる。そこのとき、資源サイクル変数を用いた資源

こで、個々のアーク上のデザイン変数としてバランス設計モデルCYBDは次のようになではなく、取りうるサイクルをデザイン変数

る。

149

配送時間制約を考慮したネットワーク設計問題（56）式は総費用を表す目的関数であり、サイクル変数は列生成法により列挙する。

これを最小化する。第二項はアーク上で使用する資源サイクルがアークを使用するときのデザイン費用の合計であり、第三項は使用さ

５

配送超過時間ペナルティーモデル

れた資源サイクルに対して発生する固定費用

配送時間制限を超過する需要に対して、ペの合計である。
（58）式は容量制約式であり、ナルティーを与えるモデルを示す。
ここでは、右辺はアークで使用される資源サイクルの合

整数デザイン変数とアークフロー変数を用い計数と容量の積であるアーク上の容量であたモデルを示す。

る。（59）式は強制制約式であり、アーク上

h番目の時間制限lhを超えたときの品種kににいずれかの資源サイクルが設定されるとき対する単位当たりの非負のペナルティ費用をに限り、アーク上をフローが流れることを表p kh とし、時間制限lhの超過時間をs kh とする。

す。資源サイクル変数は資源バランス条件とこのとき、整数デザイン変数とアークフ

稼働時間制限を満足するものに限るため、資ロー変数を用いた配送超過時間ペナルティー

源バランス式と稼働時間制限式は必要ない。

モデルOTPは次のようになる。

資源サイクルは指数個あることから、資源（65）式は総費用を表す目的関数であり、これを最小化する。第三項は配送時間超過に用と超過時間の積で表す。
（69）式は、品種kよるペナルティー費用の合計であり、配送時の配送時間期限lhに対する超過時間である。

間制限に対する単位当たりのペナルティー費

品種kの配送時間が制限時間を超えなければ

150

配送時間制約を考慮したネットワーク設計問題

左辺は負となり、（70）式からskh は0となる。

ン ス・0-1デ ザ イ ン・ ア ー ク フ ロ ー モ デ ル

また、配送時間が時間期限を超えた場合、左ABDAFである。ABDAFでは、資源のアー辺は非負の超過時間となる。ペナルティ費用

クデザイン費用を考慮するが固定費用を考慮は非負であり、目的関数値を最小化することしないモデルABDAF−Dと、資源の固定費から、（69）式は等号で成り立ち、skh は超過用を考慮するがアークデザイン費用を考慮し時間に一致する。

ないモデルABDAF−Fを対象とする。

パスフロー変数や0-1デザイン変数を用いた定式化や、資源バランスを考慮した定式化も可能である。

数値実験で使用したソフトウエア・機器等
は以下の通りである。
• 使用OSおよび言語：UBUNTU 20、
		 Python 2.7

６

数値実験

配送時間制約をもつネットワーク設計問• 最適化ソルバー：Gurobi 9.1• CPU AMD Ryzen9 3950X 3.5GHz
16Cores、RAM 64GByte

題で用いられるベンチマーク問題を用いて、		 また、数値実験で使用した設定したパラモデルと定式化による問題の困難性を比較す

メータは以下の通りである。

る。

• 時間パラメータ：1.2

使用したベンチマーク問題は、Hellsten et• 配送時間制限集合：0.8、1.2

al.（2021）が用いたインスタンスの中のR問• 需要カバー率：0.5、1.0

題である。このインスタンスは、容量制約を• 最大計算時間：3時間

もつネットワーク設計問題のためにCrainic

な お、 時 間 パ ラ メ ー タ はHellsten et al.

et al.（2001）が提示したものに、アーク上の（2021）で使用されている時間制限を設定す

移動時間を追加したものである。このR問題

る倍数である。配送時間制限の0.8は、1.2には、r04からr18（r06は欠）に分類され、そ対して2/3倍の時間制限となる。需要カバー

れぞれは9個のインスタンスで構成される。

率の1.0は配送時間制限1.2に対して全需要、表1にノード数、
アーク候補数、品種数を示す。

0.5は配送時間制限0.8に対して全体の50%を

また、表2 に容量と費用のレベルを示し、c1カバーすること意味している。

はアーク容量が大きい、c8はアーク容量が小使用したR問題は時間制約と容量制約をもさいことを表し、f01はデザイン費用が相対

つネットワーク設計問題のためのインスタン

的に安い、f10はデザイン費用が相対的に高スである。このインスタンスを資源数の制約

いことを表す。

のないモデルに適用できるようにするため計算の対象とした定式化は、整数デザイに、資源の単位当たりの容量とデザイン費用

ン・アークフローモデルIDAF、0-1デザイン・を、アークの容量とデザイン費用の値を1/1、アークフローモデルBDAF、および資源バラ

1/5、1/10 倍とした3通りのインスタンスを
151

配送時間制約を考慮したネットワーク設計問題

生 成 し、 そ れ そ れ をA1、A5、A10と し た。

スで実行可能解を算出することができた。平

A1は1資源当たりの容量が大きく、費用が高均誤差は0.1%、最大で0.6%であり、平均計算

く、A10は1資源当たりの容量が小さく、費時間は1102秒であった。A5では、121インス

用が安いインスタンスである。需要量は同一

タンスの最適解、5インスタンスの近似解をのため、A1は使用する総資源数は相対的に求めることができた。平均誤差は0.0%、最大

少なく、A10は使用する総資源数は相対的にで0.2%であり、平均計算時間は511秒であっ多くなる。ABDAFにおける最大稼働時間は、た。A10では、126すべてのインスタンスのHellsten et al.（2021）による品種中の時間最適解を求めることができた。平均誤差は制限の最大値とした。また、ABDAF−Fお0.0%であり、平均計算時間は24秒であった。

ける資源の固定費用はアークのデザイン費用

A10はA1と比べ、資源数が多くなるインスの平均値の30倍とした。また、ABDAF−D

タンスであり、デザイン変数が比較的大きなとABDAF−FにおけるA1、A5、A10の最大整数となることから、容易な問題となってい資源数をそれぞれ50、100、150とした。

ることが分かる。また、最大で0.6%程度の誤4つのモデルをPythonとGurobiを用いて、最大3時間の計算時間で定式化を直接解くこ
とにより、最適値または下界値と上界値を求めた。

差であるため、近似解も有用であると考えられる。
表4にBDAFの計算結果を示す。A1では、
126インスタンスのうち、97インスタンスの表3にIDAFの計算結果を示す。結果はr04

最適解、8インスタンスの近似解を求めるこからr18までのグループごとに集計した。最とができたが、3時間以内で21インスタンス

適解数は9個のインスタンスのうち、計算時の実行可能解を算出することができなかっ間の上限である3時間以内に最適解を求める

た。実行可能解が得られたインスタンスの平ことができたインスタンス数、近似解数は最均誤差は0.4%、最大で4.9%であり、平均計算

適解を除く近似解を求めることができたイン

時間は1693 秒であった。A5では、92インス

スタンス数であり、未解数は実行可能解を求タンスの最適解、6インスタンスの近似解をめることができなかったインスタンス数であ求めることができたが、28 インスタンスのる。誤差は（上界値-下界値）/下界値×100

実行可能解を算出することができなかった。

で算出し、平均誤差は実行可能解が求められ実行可能解が得られたインスタンスの平均誤たインスタンスの平均値である。また、平均差は0.8%、
最大で6.3%と大きくなった。また、

時間は計算時間の平均値であり、最適解が求平均計算時間は2463秒であった。A10では、められない場合は3時間（10800秒）となる。

86インスタンスの最適解、1インスタンスのA1では、126インスタンスのうち、115イ

近似解を求めることができたが、39 インス

ンスタンスの最適解、11インスタンスの近似

タンスの実行可能解を算出することができな解を求めることができ、すべてのインスタンかった。実行可能解が得られたインスタンス

152配送時間制約を考慮したネットワーク設計問題の平均誤差は0.1%、最大で0.9%、平均計算時
間は1267秒であった。

ABDAF−DはIDAFに資源バランス条件を加えたモデルであるが、得られた結果からはBDAFとIDAFは同じ問題である。資源数問題の困難性の増加は見られない。また、最の上限が大きなインスタンスではBDAFの離大で0.5%程度の誤差であるため、近似解も有散変数の数が膨大なものとなるため、単純に用であると考えられる。

汎用の最適化ソルバーを用いて求解する場合

表6にABDAF−Fの 計 算 結 果 を 示 す。

は、整数変数を用いた方が良いことが分かる。

ABDAF−Fは資源の固定費用を考慮し、アー

しかしながら、さらに規模の大きなインスタ

クのデザイン費用を0としたものである。A1ンスになると、IDAFも解を算出することがでは、126インスタンスのうち、64インスタ

困難になることが考えられるので、0-1変数

ンスの最適解、61インスタンスの近似解を求とパスフローによる定式化に列生成法や分枝めることができたが、1つのインスタンスで価格法などを適用した解法などを検討する必実行可能解を算出することができなかった。

要がある。

実行可能解を算出できたインスタンスの平均

表5にABDAF−Dの 計 算 結 果 を 示 す。

誤差は0.4%、最大で1.0%であり、平均計算時

ABDAF−Dは資源の固定費用を0としたもの

間は5750秒であった。また、平均の資源数はである。A1では、126インスタンスのうち、5.8であった。A5では、24インスタンスの最108インスタンスの最適解、18インスタンス

適解、96インスタンスの近似解を求めることの近似解を求めることができ、すべてのインができたが、6インスタンスで実行可能解をスタンスで実行可能解を算出することができ算出することができなかった。実行可能解をた。平均誤差は0.2%、最大で1.0%であり、平算出できたインスタンスの平均誤差は0.5%、

均計算時間は1804秒であった。また、平均の最大で1.1%であり、平均計算時間は8881秒で資源数は14.7であった。A5では、96インスタ

あった。また、
平均の資源数は15.7 であった。

ンスの最適解、26インスタンスの近似解を求多くのインスタンスグループで最適解を求めめることができ、すべてのインスタンスで実る こ と が で き ず、 平 均 計 算 時 間 が 上 限 の行可能解を算出することができた。平均誤差

10800秒となっている。A10では、7インスタ

は0.1%、最大で0.5%であり、平均計算時間はンスの最適解、107インスタンスの近似解を2641秒であった。また、平均の資源数は42.5求めることができたが、12インスタンスで実であった。A10では、92インスタンスの最適行可能解を算出することができなかった。実解、27インスタンスの近似解を求めることが行可能解を算出できたインスタンスの平均誤

でき、すべてのインスタンスで実行可能解を差は0.4%、最大で0.8%であり、平均計算時間算出することができた。平均誤差は0.1%、最は10409秒であった。また、平均の資源数は大で0.5%であり、平均計算時間は2786秒で25.4であった。多くのインスタンスグループ

あった。また、平均の資源数は71.5であった。

で最適解を求めることができず、平均計算時
153配送時間制約を考慮したネットワーク設計問題

間が上限の10800秒となっている。

の異なるいくつかの定式化、およびフローや

ABDAF−Dと比較すると、最適解を求めることが困難で、3時間以内で近似解を求め資源の表現が異なるいくつかの定式化を提示した。

ることも難しくなり、資源の固定費用の考慮

ベンチマーク問題を用いて、4つの定式化が問題の困難性に大きな影響を与えているこについて数値実験を行い、問題の条件や定式とが分かる。

化による求解の困難性を明らかにした。数値

７

実験は陽的に定式化されたものを最適化ソルおわりにバーで解くことによって行った。しかし、ベ

本研究では、当日配送、翌日配送などの複ンチマーク問題においても、一定の計算時間

数の配送時間制約を考慮し、配送車である資の下で実行可能解すら算出できないインスタ

源のバランスを考慮する資源バランス設計条

ンスが存在した。このように、陽的に定式化

件と同一品種のフローが１つのパスを流れるを直接解くことには限界があるため、パスフ

条件を考慮した複数の資源の配置とフローを

ローや資源サイクルの列生成法の適用、線形求めるアーク設計問題のモデルを扱った。こ緩和解を用いた近似解法の開発や分枝価格法のモデルに対して、配送時間制限の考慮方法の適用など、多くの課題が残されている。

表1:R問題:属性1

表2:R問題:属性2

154

配送時間制約を考慮したネットワーク設計問題
表3:IDAFの結果

155配送時間制約を考慮したネットワーク設計問題
表4:BDAFの結果

156

配送時間制約を考慮したネットワーク設計問題
表5:ABDAF−Dの結果

157配送時間制約を考慮したネットワーク設計問題
表6:ABDAF−Fの結果

158配送時間制約を考慮したネットワーク設計問題
参考文献
Andersen, J., M. Christiansen, T. G. Crainic, R.
Grønhaug. 2011. Branch and price for service
network design with asset management
constraints. Transportation Science 45(1) 33–49.
Andersen, J., T. G. Crainic, M. Christiansen. 2009.
Service network design with management andcoordination of multiple fleets. European Journalof Operational Rsearch 193(2) 377–389.
Atamtürk, A., D. Rajan. 2002. On splittable andunsplittable flow capacitated network design arcset polyhedra. Mathematical Programming 92(2)315–333.
Bai, R., S. W. Wallace, J. Li, A. Y. Chong. 2014.
Stochastic service network design with rerouting.
Transportation Research Part B 60 50–65.
Balakrishnan, A., C.V. Karsten. 2017. Container
shipping service selection and cargo routing withtransshipment limits. European Journal ofOperational Research (263(2)) 652—-663.
Boland, N., M. Hewitt, L. Marshall, M. Savelsbergh.
2017. The continuous-time service network
design problem. Operations Research 65 1115–
1428.
Crainic, T. G., A. Frangioni, B. Gendron. 2001.
Bundle-based relaxation methods for
multicommodity capacitated fixed charge
network design problems. Discrete Applied
Mathematics 112(1-3) 73–99.
Crainic, T. G., Fu X, M. Gendreau, W. Rei, S.
Wallace. 2011. Progressive hedgingbased
metaheuristics for stochastic network design.
Networks 58 114–124.
Crainic, T.G., M. Gendreau, B.Gendron, eds. 2021.
Network Design with Applications toTransportation and Logistics. Springer.
Crainic, T.G., M. Hewitt, M. Toulouse, D.M. Vu.
2016. Service network design with resource
constraints. Transportation Science 50(4) 1380–
1393.
Croxton, K. L., B. Gendron, T. L. Magnanti. 2003. A
comparison of mixed-integer programming
models for nonconvex piecewise linear cost
minimization problems. Management Science 49
1268–1273.
Erera, A., M. Hewitt, M. Savelsbergh, Y. Zhang.
2013. Improved load plan design through integer
programming based local search. Transportation
Science 47(3) 295–454.
Hellsten, E., D.F. Koza, I. Contreras, J.F. Cordeau, D.
Pisinger. 2021. The transit time constrained fixedcharge multi-commodity network design
problem. Computers & Operations Research 136
105511.
Jarrah, A. I., E. Johnson, L. C. Neubert. 2009. Largescale, less-than-truckload service network design.
Operations Research 57(3) 609–625.
Karsten, C.V., B.D. Brouer, D. Pisinger. 2017.
Integrated liner shipping network design andscheduling. Transportation Research Part E:
Logistics and Transportation Review (105) 152—
-162.
Koza, D.F., G. Desaulniers, S. Ropke. 2020.
Integrated liner shipping network design andscheduling. Transportation Science (Published

Online).
Li, X., K. Wei, Y.P. Aneja, P. Tian, Y. Cui. 2017.
Matheuristics for the single-path design-balanced
service network design problem. Computers &Operations Research 77 141–153.
Pedersen, M. B., T. G. Crainic, O. B. G. Madsen.
2009. Models and tabu search metaheuristics forservice network design with asset-balance
requirements. Transportation Science 43 158–177.
Rahmaniani, R., T. G. Crainic, M. Gendreau, W. Rei.
2018. Accelerating the benders decomposition
method: Application to stochastic network design
problems. SIAM Journal on Optimization 28(1)875–903.
Tierney, K., J.F. Ehmke, A.M. Campbell, D. Müller.
2019. Liner shipping single service design
problem with arrival time service levels. Flexible
Services and Manufacturing Journal (31(3)) 620—
-652.
Trivella, A., F. Corman, D. F. Koza, D. Pisinger.
2021. The multi-commodity network flow
problem with soft transit time constraints:
Application to liner shipping. Transportation
Research Part E: Logistics and Transportation
Review 150 102342.
Wang, X., T. G. Crainic, S. W.Wallace. 2019.
Stochastic network design for planning scheduledtransportation services: the value of deterministic
solutions. Informs Journal on Computing 31.
doi:10.1287/ijoc.2018.0819.
Yaghini, M., M. R. A Kazemzadeh. 2012. A
simulated annealing algorithm for unsplittablecapacitated network design. International Journalof Industrial Engineering & Production Research23(2) 91–100.

159