Блог

Я создаю VRP (модель проблемы маршрутизации транспортных средств с использованием python PuLP, но он не может найти оптимальное решение, удовлетворяющее всем ограничениям.

используя этот xls-файл:https://drive.google.com/file/d/1s7rOQCULynGxQk8_IMlvHl286d4WfdPt/view?usp=sharing

 import pulp, pandas, itertools
import numpy as np

xls =pandas.ExcelFile('data node VRP 2.xls')
weight = pandas.read_excel(xls,'Sheet1')
sheet2 = pandas.read_excel(xls, 'Sheet2')
matrixjarak = pandas.read_excel(xls, 'matrixjarak')
#weight=sheet1.as_matrix()
vehicle=sheet2.as_matrix() #vehicle
matrixjarak=matrixjarak.as_matrix()

model = pulp.LpProblem("VRP Problem", pulp.LpMinimize)

d = weight['demand']
c = matrixjarak
J = np.arange(len(c)-5) #create array 0..
p = np.arange(len(vehicle))
C = vehicle

x = pulp.LpVariable.dicts("nodes to nodes",
                                     ((r,i,j) for i in J for j in J for r in p),
                                     lowBound=0,
                                     cat='Biner')

model  = (
    pulp.lpSum([
        c[i][j]*x[(r,i,j)]
        for i in J for j in J for r in p if i != j])
)
#1 in out always 1
for i in range(1,len(J)-1):
    model  = pulp.lpSum([x[r,i,j] for j in range(1,len(J)-1) for r in p if i != j]) == 1
    #model  = pulp.lpSum([x[r,i,j] for j in range(1,len(J)-1) for r in p if i != j]) == 1

for j in range(1,len(J)-1):
    model  = pulp.lpSum([x[r,i,j] for i in range(1,len(J)-1) for r in p if j != i]) == 1
    #model  = pulp.lpSum([x[r,i,j] for j in range(1,len(J)-1) for r in p if i != j]) == 1

#2 capacity
for r in p:
    model  = pulp.lpSum([d[i]*x[r,i,j] for i in J for j in J if i != j]) <= 70 #l[v]


#3 go from depot
for r in p:
    model  = pulp.lpSum([x[r,0,j] for j in J for r in p]) == 1

#4 back to depot
for r in p:
    model  = pulp.lpSum([x[r,i,0] for j in J for r in p]) == 1

#5
for r in p:
    for h in J:
        model  = pulp.lpSum([x[r,i,h] for i in J if i != h]) - pulp.lpSum([x[r,h,j] for j in J if h != j]) == 0


model.solve()
pulp.LpStatus[model.status]
for var in x:
    var_value = x[var].varValue
    print("nodes", var[1]," move to nodes ",var[2],"with vehicle ",var[0],"adalah", var_value) 

print("cost optimal",pulp.value(model.objective))


  

Я ожидаю, что это приведет к выводу 0 и 1 для x [r, i, j] (переменная решения). Но это приводит к десятичному выводу:

 nodes 0  go to nodes  0  with vehicle 0 are 0.875
nodes 0  go to nodes  6  with vehicle 0 are 0.125
nodes 1  go to nodes  2  with vehicle 1 are 1.0
nodes 2  go to nodes  1  with vehicle 1 are 1.0
nodes 3  go to nodes  6  with vehicle 1 are 0.23333333
nodes 3  go to nodes  6  with vehicle 2 are 0.76666667
nodes 4  go to nodes  5  with vehicle 2 are 1.0
nodes 5  go to nodes  4  with vehicle 2 are 1.0
nodes 6  go to nodes  0  with vehicle 0 are 0.125
nodes 6  go to nodes  3  with vehicle 1 are 0.23333333
nodes 6  go to nodes  3  with vehicle 2 are 0.76666667

cost optimal adalah 2.8
  

есть ли какой-либо ключ к решению этой проблемы?

класс class pulp.LpVariable определяется как:

 pulp.LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)

with:

cat – The category this variable is in, Integer, Binary or Continuous(default)
  

Кроме того, src/pulp/constants.py определяет:

 LpCategories = {LpContinuous: "Continuous", LpInteger: "Integer",
                LpBinary: "Binary"}
  

Значение:

• вы просите cat='Biner'
• нужно запросить pulp want для cat='Binary'
  • иначе будет сгенерирована непрерывная переменная, приводящая к тому, что вы наблюдаете
  • смотрите оригинальные источники в отношении этого выбора
    • (я думаю, я бы ввел более «агрессивную» проверку в этой процедуре)