配送計画問題
配送計画問題は盛んに研究されてきた組合せ最適化問題の1つです。配送計画問題では，複数台の運搬車を用いて，複数の顧客に対して荷物の配送を行う方法を計画します。この際の目的として，移動距離の最小化や，総配送時間の最小化などが用いられます。
配送計画問題ではさまざまな設定がなされますが，ここでは，1日で終えるルートを作成することとします。各運搬車は，朝，拠点と呼ばれる場所に集まり，そこで当日担当する配達荷物を積み込み，出発したら定められた計画に従って，顧客を訪問して荷物を配達し，全ての配達を終了したら拠点に戻ります。
配送計画問題を定式化するためによく用いられるのが，集合分割問題としての定式化です。集合分割問題は，与えられた集合をその部分集合に分割する問題です。例えば，集合$ S=\{1,2,3,4,5,6\}の分割の例として，$ S_1=\{1,3,4\}
$ S_2=\{2,5\} , $ S_3=\{6\} が挙げられます。
配送計画問題を集合分割問題として定式化する場合は，集合$ S を訪問する顧客の集合に対応づけます。そして，1つの部分集合は，1台の運搬車が1日に訪問する顧客の集合を表します。例えば，上記の例では，$ S_1は顧客1,3,4を配送するルートを表します。
顧客の集合を$ C=\{1,2,...,n\}と表すとします。そして，ルートの集合を$ R=\{1,2,...,m\}と表すとします。$ Rの要素$ rは，1台の運搬車が訪問する顧客の列（ルートと呼ぶ）を表し，ルート$ rのコストを$ c_rと表すことにします。ルート$ rに対して0-1変数$ x_rを導入する。$ x_r は，ルート$ rが採用されるとき1，それ以外のとき0となる変数とします。
こうすると，採用されるルートの総コストは，
$ \sum_{r \in R} c_r x_r
と表されます。そして，各顧客がちょうど1回いずれかのルートに訪問されるという条件を課します。
$ \sum_{r \in R:r\text{は顧客}i\text{を含む}} x_r = 1 for $ i \in C
ここで，$ C=\{1,2,3,4,5\}, $ R=\{1,2,3,4,5,6,7,8,9,10\},
$ c=[c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9,c_{10}]=[10,20,30,40,50,60,70,80,90,100]]
とする例をとりあげます。
各ルートにおいて配送される顧客は，下記のとおりとする。
- 1. $ [1,2]
- 2. $ [2,3]
- 3. $ [3,4]
- 4. $ [4,5]
- 5. $ [1,3]
- 6. $ [2,4]
- 7. $ [3,5]
- 8. $ [1,2,3]
- 9. $ [2,3,4]
- 10. $ [3,4,5]
この問題をpyhonで解くためのプログラムを，次に示します。
例えば，google colaboratoryを用いると，手元の計算機にpyhonの実行環境を作らずともオンラインで実行することができます。1行目の !pip install pulpは，整数計画問題をモデル化するためのパッケージをインストールするための命令です。
code:python
!pip install pulp
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpStatus, value
# Initialize the model
prob = LpProblem("SetPartition", LpMinimize)
# Parameters
routes = range(10)
customers = range(5)
# c: route costs
# Binary decision variables
x = LpVariable.dicts("x", routes, 0, 1, cat='Binary')
# Objective function
prob += lpSum([cr*xr for r in routes]) # Constraints
customer_route_matrix = [
1, 0, 0, 0, 1, 0, 0, 1, 0, 0, # customer 0 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, # customer 1 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, # customer 2 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, # customer 3 ]
for i in customers:
prob += lpSum([xr*customer_route_matrixir for r in routes]) == 1 # Solve the problem
prob.solve()
print(f"Optimal Value: {value(prob.objective)}")
for v in prob.variables():
print(f"{v.name} = {v.varValue}")
このプログラムを実行することで，最適解として$ x_0=x_9=1 が得られます。ここで，Pythonではリストの添字が0から始まるので，$ x_0は1番目のルートに対応し，$ x_9は10番目のルートに対応することに注意してください。
ルート1で訪問されるのは顧客1,2であり，ルート10で訪問されるのは顧客3,4,5なので，ルート1とルート10を採用することで顧客1,2,3,4,5,のそれそれが，ちょうど1回ずつ訪問されることがわかります。そして，この時の総コストは10+100=110です。
他に，ルート4とルート8を採用しても，各顧客はちょうど1回ずつ訪問されます。しかし，この時のコストは40+80=120となるので，最適解ではありません。
配送計画問題は，久保先生のページに詳細な解説があります。