前提・実現したいこと
配送計画問題をpythonのpulpモジュールを用いて解こうとしております.
前提として,1つの配送拠点から複数台の運搬車を用いて需要量が与えられている各地点を巡回する問題を考えております.
通常,配送計画問題の目的関数は「すべての運搬車の総移動距離」を目的関数とし,それを最小化することで配送ルートを決定するのですが,
今回は「最も移動距離が長くなる運搬車」に着目しそれを最小化するような配送ルートを決定したいと考えております.
以下に,通常の目的関数の場合のソースコードを示します.
(こちらのサイトを参考にさせていただいております)
運搬経路問題(配送最適化問題,Vehicle Routing Problem) をPuLPで解く
ソースコード
import numpy as np import pandas as pd import pulp import itertools #データ作成(数値は例) customer_count =10 vehicle_count = 3 vehicle_capacity = 93 #需要量と各地点間のコストの読み込み df=pd.read_csv('demand.csv') cost = pd.read_csv('network.csv',header=None,index_col=None) #定式化と解計算 for vehicle_count in range(1,vehicle_count+1): # 問題の宣言 problem = pulp.LpProblem("CVRP", pulp.LpMinimize) # 決定変数 x = [[[pulp.LpVariable("x%s_%s,%s"%(i,j,k), cat="Binary") if i != j else None for k in range(vehicle_count)]for j in range(customer_count)] for i in range(customer_count)] # 目的関数 problem += pulp.lpSum(cost[i][j] * x[i][j][k] if i != j else 0 for k in range(vehicle_count) for j in range(customer_count) for i in range (customer_count)) # 制約 # (2)式,各顧客の場所に訪れるのは1台の車両で1度である for j in range(1, customer_count): problem += pulp.lpSum(x[i][j][k] if i != j else 0 for i in range(customer_count) for k in range(vehicle_count)) == 1 #(3)式, depotから出発して,depotに戻ってくる for k in range(vehicle_count): # デポを出発した運搬車が必ず 1つの顧客から訪問を開始することを保証する制約条件 problem += pulp.lpSum(x[0][j][k] for j in range(1,customer_count)) == 1 # 必ず 1 つの顧客から運搬車がデポへ到着すること保証する制約条件 problem += pulp.lpSum(x[i][0][k] for i in range(1,customer_count)) == 1 #(4)式, ある顧客の所に来る車両数と出る車両数が同じ for k in range(vehicle_count): for j in range(customer_count): problem += pulp.lpSum(x[i][j][k] if i != j else 0 for i in range(customer_count)) - pulp.lpSum(x[j][i][k] for i in range(customer_count)) == 0 #(5)式, 各車両において最大容量を超えない for k in range(vehicle_count): problem += pulp.lpSum(df.demand[j] * x[i][j][k] if i != j else 0 for i in range(customer_count) for j in range (1,customer_count)) <= vehicle_capacity #(6)式, 部分巡回路除去制約 subtours = [] for i in range(2,customer_count): subtours += itertools.combinations(range(1,customer_count), i) for s in subtours: problem += pulp.lpSum(x[i][j][k] if i !=j else 0 for i, j in itertools.permutations(s,2) for k in range(vehicle_count)) <= len(s) - 1 #最適化問題を解く aaa={} #最適解が出たら終了 if problem.solve() == 1: print('目的関数値:', pulp.value(problem.objective)) break
上記のソースコードを基にし,目的関数部分を修正することで実装できるのではないかと考えております.
ご教示の程宜しくお願い致します.
あなたの回答
tips
プレビュー