最小化問題を解いています。
顧客数(dataのされぞれの数)が22まではうまくいきますが、23はエラーになります。(データは最大でも23)
python
1raise pulp solver error("Pulp:Error while trying to execute " + / 2pulp.solvers.PulpSolverError: Pulp: Error while trying to execute C:/Users/~~
とpulpのエラーが表示されます。
上記を参考にしようとしたのですが、似た構文が見当たらず解決に至っていません。
解決方法をご存知の方いらっしゃいましたらご教授いただけますと幸いです。
以下実行コードです。
python
1import pulp 2import pandas as pd 3import numpy as np 4import itertools 5import matplotlib.pyplot as plt 6from scipy.spatial import distance_matrix 7 8customer_count = 10 # 顧客数 9vehicle_count = 1 # 車両数 10vehicle_capacity = 8000 # 車両容量 11 12data = { 13"x": [33.642024,33.547292,33.507122,33.546083,33.44278,33.505567,33.540876,33.633199,33.512012,33.5816], 14 "y": [130.415021,130.483337,130.437378,130.477885,130.538346,130.455676,130.483793,130.523473,130.483812,130.254898], 15 "demand": [0,300,80,40,70,80,90,60,204.1,20]} 16 17 18df = pd.DataFrame(data) 19 20# id=0はdepotなので,demand=0にする 21df.iloc[0].x = 33.642024 22df.iloc[0].y = 130.415021 23df.iloc[0].demand = 0 24 25# コストとしてノード間の直線距離を求める 26cost = pd.DataFrame(distance_matrix(df.values, df.values), index=df.index, columns=df.index).values 27df.head() 28 29# depotと顧客の位置の可視化.添え字は荷物の量 30plt.figure(figsize=(5, 5)) 31for i in range(customer_count): 32 if i == 0: 33 plt.scatter(df.x[i], df.y[i], c='r') 34 plt.text(df.x[i] + 1, df.y[i] + 1, "depot") 35 else: 36 plt.scatter(df.x[i], df.y[i], c='b') 37 plt.text(df.x[i] + 1, df.y[i] + 1, str(df.demand[i])) 38plt.xlim([33.4, 33.8]) 39plt.ylim([130.2, 130.6]) 40 41for vehicle_count in range(1, vehicle_count + 1): 42 # 問題の宣言 43 problem = pulp.LpProblem("CVRP", pulp.LpMinimize) 44 45 # 決定変数 46 x = [[[pulp.LpVariable("x%s_%s,%s" % (i, j, k), cat="Binary") if i != j else None for k in range(vehicle_count)] for 47 j in range(customer_count)] for i in range(customer_count)] 48 49 # 目的関数 50 problem += pulp.lpSum(cost[i][j] * x[i][j][k] if i != j else 0 51 for k in range(vehicle_count) for j in range(customer_count) for i in range(customer_count)) 52 53 # 制約 54 # (2)式,各顧客の場所に訪れるのは1台の車両で1度である 55 for j in range(1, customer_count): 56 problem += pulp.lpSum( 57 x[i][j][k] if i != j else 0 for i in range(customer_count) for k in range(vehicle_count)) == 1 58 # (3)式, depotから出発して,depotに戻ってくる 59 for k in range(vehicle_count): 60 # デポを出発した運搬車が必ず 1つの顧客から訪問を開始することを保証する制約条件 61 problem += pulp.lpSum(x[0][j][k] for j in range(1, customer_count)) == 1 62 # 必ず 1 つの顧客から運搬車がデポへ到着すること保証する制約条件 63 problem += pulp.lpSum(x[i][0][k] for i in range(1, customer_count)) == 1 64 65 # (4)式, ある顧客の所に来る車両数と出る車両数が同じ 66 for k in range(vehicle_count): 67 for j in range(customer_count): 68 problem += pulp.lpSum(x[i][j][k] if i != j else 0 for i in range(customer_count)) - pulp.lpSum( 69 x[j][i][k] for i in range(customer_count)) == 0 70 71 # (5)式, 各車両において最大容量を超えない 72 for k in range(vehicle_count): 73 problem += pulp.lpSum(df.demand[j] * x[i][j][k] if i != j else 0 for i in range(customer_count) for j in 74 range(1, customer_count)) <= vehicle_capacity 75 # (6)式, 部分巡回路除去制約 76 subtours = [] 77 for i in range(2, customer_count): 78 subtours += itertools.combinations(range(1, customer_count), i) 79 80 for s in subtours: 81 problem += pulp.lpSum( 82 x[i][j][k] if i != j else 0 for i, j in itertools.permutations(s, 2) for k in range(vehicle_count)) <= len( 83 s) - 1 84 85 # 最適化問題を解く 86 # 最適解が出たら終了 87 if problem.solve() == 1: 88 print('車両数:', vehicle_count) 89 print('目的関数値:', pulp.value(problem.objective)) 90 break 91plt.figure(figsize=(5, 5)) 92for i in range(customer_count): 93 if i == 0: 94 plt.scatter(df.x[i], df.y[i], c='r') 95 plt.text(df.x[i] + 1, df.y[i] + 1, str(i) + ",depot") 96 else: 97 plt.scatter(df.x[i], df.y[i], c='b') 98 plt.text(df.x[i] + 1, df.y[i] + 1, str(i) + "(" + str(df.demand[i]) + ")") 99plt.xlim([33.4, 33.8]) 100plt.ylim([130.2, 130.6]) 101 102for k in range(vehicle_count): 103 for i in range(customer_count): 104 for j in range(customer_count): 105 if i != j and pulp.value(x[i][j][k]) == 1: 106 plt.plot([df.x[i], df.x[j]], [df.y[i], df.y[j]], c="black") 107 108plt.show() 109
あなたの回答
tips
プレビュー