纸浆约束冲突

Question

我正在尝试使用 PuLP 的 GLPK 求解器来求解 VRP，每个节点都有额外的时间成本，该时间成本直接添加到行程时间矩阵中。下面是带有约束的代码，以确保每个客户被 1 名员工拜访一次，并且每个员工的所有路线都在节点 0 开始和结束。

import pulp
from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable, LpMinimize, LpBinary, LpInteger, GLPK
input = []
with open("test.txt", "r") as f:
    for line in f:
        input.append(line)

n = [int(x) for x in input[0].split()]
N = n[0] #number of customer
K = n[1] #number of staff
c = [int(x) for x in input[1].split()] #time cost at each customer vector 
c.insert(0, 0)
poi_ma = [] # distance matrix
for i in range(N+1):
    poi_ma.append([int(x) for x in input[i+2].split()])
    for y in range(0, N + 1):
        if y == i:
            continue
        else:
            poi_ma[i][y] = poi_ma[i][y] + c[y]

model = LpProblem("myprob",sense=LpMinimize)
X =[]
X.append(0)
for k in range(1, K+1):
    X.append([])
    for i in range(N+1):
        X[k].append([])
        for j in range(N+1):
            X[k][i].append(LpVariable(f"X[{k}][{i}][{j}]", cat=LpBinary))

y = LpVariable("y", cat= LpInteger, lowBound = 0)
U = [0]
for i in range(1, N+1):
    U.append(LpVariable(f"U[{i}]",lowBound = 1, upBound = 10000))


# 1 - Each customer is served by exactly one staff member
for i in range(N+1):
    for j in range(N+1):
        if i != j:
            model += (lpSum([X[k][i][j] for k in range(1, K+1)]) == 1)
        else:
            model += (lpSum([X[k][i][j] for k in range(1, K+1)]) == 0)


# 2 - Each staff member starts and ends at the headquarters
for k in range(1, K+1):
    model += (lpSum([X[k][0][j] for j in range(N+1)]) == 1)
    model += (lpSum([X[k][x][0] for x in range(N+1)]) == 1)

# 3 - Enforce flow conservation at each customer location
for k in range(1, K+1):
    for i in range(N + 1):
        tmp1 = lpSum(X[k][i][j] for j in range (N + 1))
        tmp2 = lpSum(X[k][j][i] for j in range (N + 1))
        model += (tmp1 <= 1)
        model += (tmp2 <= 1)
        model += (tmp1 - tmp2 == 0)


# 4 - Miller-Tucker-Zemlin formulation
for i in range(1, N+1):
    #model += (1 <= U[i])
    for j in range(1, N+1):
        if j != i:
            for k in range(1, K+1):
                model += (1 - 10000 + 10000 * X[k][i][j]) <= (U[j] - U[i])

# 5 - Calculate work time for each staff member and ensure it's less than or equal to y
for k in range(1, K+1):
    work_time = lpSum([poi_ma[i][j] * X[k][i][j] for i in range(N + 1) for j in range(N + 1) if i != j])
    model += (work_time <= y)

model += y
status = model.solve(pulp.PULP_CBC_CMD(msg=True, cuts=True)) 

print(model.status)
for k in range(1, K+1):
    print(f"{k}", end = ':')
    for i in range(N+1):
        for j in range(N+1):
            if X[k][i][j].varValue == 1:
                print(f"{i},{j}", end = ' ')
    print()
print(y.varValue)

“test.txt”文件包含：

5 2
6 8 7 1 9
0 5 10 6 4 8
5 0 5 4 2 6
10 5 0 5 7 4
6 4 5 0 6 2
4 2 7 6 0 8
8 6 4 2 8 0

当我尝试执行代码时，它返回以下消息：

Local\Temp\086601480d8341f89343bb8327bacee3-pulp.mps gomory on knapsack on probing on timeMode elapsed branch printingOptions all solution C:\Users\hungn\AppData\Local\Temp\086601480d8341f89343bb8327bacee3-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 123 COLUMNS
At line 825 RHS
At line 944 BOUNDS
At line 1028 ENDATA
Problem MODEL has 118 rows, 78 columns and 542 elements
Coin0008I MODEL read with 0 errors
Option for gomoryCuts changed from ifmove to on
Option for knapsackCuts changed from ifmove to on
Option for timeMode changed from cpu to elapsed
Problem is infeasible - 0.00 seconds
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.00

-1
1:0,3 1,0 2,0 2,3 3,0 4,3 5,0 5,2 5,3
2:0,1 0,2 0,4 0,5 1,2 1,3 1,4 1,5 2,1 2,4 3,1 3,2 3,4 3,5 4,0 4,1
346.0

这表明该问题不可行。我尝试隔离每个约束来评估它们，如图所示：

.

很有可能约束1有问题，但我找不到问题所在。有人可以帮我找出这里的问题吗？我感谢您的所有帮助和意见。

Answer 1

您的第一个约束是不正确的。您应该在求和语句中对

i

或

j

以及

k

进行求和。现在它说一名工作人员应该从每个

i

到每个

j

，这显然不是你想要的。您希望一名工作人员从

some

j 到达每个

i

。

此外，您的 MTZ 约束需要通过

k

进行索引，并且每个员工都需要自己的序列编号。

尝试一下这些事情。如果仍然不可行，请尝试注释掉各个约束并运行它，这应该会给您一些线索。

如果您在尝试后仍然遇到困难，请编辑您的帖子以包含更新的工作，然后进行评论。