python-3.x - 车辆路线问题：链接变量“path (X)”和变量“Delivered_Quantity”时，PuLP 的“解决方案不可行”

Question

试图最小化总行驶距离（使用纸浆），我得到了一个不可行的解决方案，虽然它显然是可行的。

当我链接变量“path (X)”和变量“Delivered_Quantity”时，解决方案变得不可行。在代码中，链接是在“卡车 t 交付的总数量不能超过卡车 t 的总吨位容量”的约束下完成的。

from pulp import *

# Sets
Client = [0, 1, 2, 3]  # List of clients
Client_without_warehouse = [1, 2]  # List of clients without warehouse
T = [0, 1, 2]  # List of trucks
P = [0, 1, 2, 3]  # List of product types
Routes = [(i, j) for i in Client for j in Client if i != j]

# Parameters
Dist = {0: {0: 0.0, 1: 50.45, 2: 100.96, 3: 0.0}, 1: {0: 50.96, 1: 0.0, 2: 50.56, 3: 50.14},
        2: {0: 100.23, 1: 50.57, 2: 0.0, 3: 100.21}, 3: {0: 0.0, 1: 50.00, 2: 100.63, 3: 0.0}}  # Matrix Distance
Demand = {0: {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0}, 1: {0: 9.0, 1: 1.0, 2: 2.0, 3: 0.0},
          2: {0: 1.0, 1: 5.0, 2: 0.0, 3: 1.5}, 3: {0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0}}  # Demand of client i in product p
TData = {"Truck Capacity": {0: 11.0, 1: 7.0, 2: 10.0}}  # Capacity of the different trucks
Speed = 50.0  # Average speed
TMW = {"Earliest Time": {0: 0.0, 1: 8.0, 2: 9.0, 3: 0.0}, "Latest time": {0: 24.0, 1: 17.0, 2: 16.0, 3: 24.0},
       "Service Time": {0: 0.0, 1: 0.5, 2: 0.5, 3: 0.0}}  # Earliest time, latest time and service time at client i

# Variables
# X = 1, if truck t travels directly from client i to client j ; 0, otherwise
X = LpVariable.dicts("X", (T, Client, Client), lowBound=0, upBound=1, cat="Binary")
# Amount of demand of client i in product p delivered by truck t
Delivered_Quantity = LpVariable.dicts("Delivered_Quantity", (T, Client_without_warehouse, P), lowBound=0, cat="Continuous")
# Starting time of service at client i by truck t
Starting_Time = LpVariable.dicts("Starting_Time", (T, Client), lowBound=0, cat='Continuous')

# Objection Function : Minimize total travel distance
Objective = LpProblem("VRP", LpMinimize)
Objective += lpSum(Dist[i][j]*X[t][i][j] for t in T for (i, j) in Routes)

# Different Constraints
for i in Client_without_warehouse:
    for p in P:
        # Total demand should be fulfilled.
        Objective += lpSum(Delivered_Quantity[t][i][p] for t in T) == Demand[i][p]
for t in T:
    # Warehouse is the starting point.
    Objective += lpSum(X[t][i][0] for i in Client) - lpSum(X[t][0][j] for j in Client) == -1
    # Warehouse is the final point.
    Objective += lpSum(X[t][i][len(Client) - 1] for i in Client) - lpSum(X[t][len(Client) - 1][j] for j in Client) == 1
    for k in Client_without_warehouse:
        # If truck goes to one customer, it has to leave it afterwards.
        Objective += lpSum(X[t][i][k] for i in Client) - lpSum(X[t][k][j] for j in Client) == 0  # (2.1.1)
        for (i, j) in Routes:
            # Total quantity delivered by truck t cannot exceed total tonnage capacity of truck t.
            Objective += lpSum(Delivered_Quantity[t][k][p] for k in Client_without_warehouse for p in P) <= X[t][k][j] * TData["Truck Capacity"][t]
            # Feasibility of time schedule + No sub-tour.
            Objective += Starting_Time[t][i] + (Dist[i][j] / Speed) + TMW["Service Time"][i] - (
                         TMW["Latest time"][i] + (Dist[i][j] / Speed) - TMW["Earliest Time"][i]) * (1 - X[t][i][j]) <= Starting_Time[t][j]

# Print Solution
status = Objective.solve()
if status == LpStatusOptimal:
    print("Solution: ", LpStatus[Objective.status])
    print("Total travel distance: ", pulp.value(Objective.objective))
else:
    print("Solution: ", LpStatus[Objective.status])

你知道有什么问题吗？

标签： python-3.xmathematical-optimizationpulpvehicle-routing

Answer 1

我希望这可以帮助您进行模型调试。无论如何，它提供了一种相当简单的方法来调试我经常使用的复杂数学模型。

1. 我创建了一个新的松弛变量：

ip = [(i, p) for i in Client_without_warehouse for p in  P]
Demand_slack = LpVariable.dicts("Demand_slack", ip, lowBound=0, cat='Continuous')
tkr = [(t, k, i, j) for t in T for k in Client_without_warehouse for (i, j) in Routes]
slack_tkr = LpVariable.dicts("slack_tkr", tkr, lowBound=0, cat='Continuous')

2. 我将它们添加到您之前的目标函数中，权重很大：

BIG_WEIGHT = 99999
Objective += lpSum(Dist[i][j]*X[t][i][j] for t in T for (i, j) in Routes) + \
             BIG_WEIGHT * lpSum(slack_tkr.values()) + \
             10000 * BIG_WEIGHT * lpSum(Demand_slack.values())

3. 我将它们添加到您的约束中：

# Different Constraints
for i in Client_without_warehouse:
    for p in P:
        # Total demand should be fulfilled.
        Objective += lpSum(Delivered_Quantity[t][i][p] for t in T) + Demand_slack[i][p] >= Demand[i][p]

和另一个：

#(...)
            Objective += Starting_Time[t][i] + (Dist[i][j] / Speed) + TMW["Service Time"][i] - (
                         TMW["Latest time"][i] + (Dist[i][j] / Speed) - TMW["Earliest Time"][i]) * (1 - X[t][i][j]) <=\
                         Starting_Time[t][j] + slack_tkr[t, k, i, j]

4. 在解决并获得最佳解决方案后，我打印了非零松弛变量的组合：

[tup for tup, _var in Demand_slack.items() if _var.value()]
[tup for tup in tkr if slack_tkr[tup].value()]

说明以下客户和产品组合存在满足需求的问题：

[(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 3)]

如果您更改松弛变量中的权重，您会在以下路由约束（一半路由）中遇到问题：

[(0, 1, 0, 2), (0, 1, 1, 0), (0, 1, 1, 2), (0, 1, 1, 3), (0, 1, 2, 0), (0, 1, 2, 1), (0, 1, 3, 1), (0, 1, 3, 2), (0, 2, 0, 2), (0, 2, 1, 0), (0, 2, 1, 2), (0, 2, 1, 3), (0, 2, 2, 0), (0, 2, 2, 1), (0, 2, 3, 1), (0, 2, 3, 2), (2, 1, 0, 2), (2, 1, 1, 0), (2, 1, 1, 2), (2, 1, 1, 3), (2, 1, 2, 0), (2, 1, 2, 1), (2, 1, 3, 1), (2, 1, 3, 2), (2, 2, 0, 2), (2, 2, 1, 0), (2, 2, 1, 2), (2, 2, 1, 3), (2, 2, 2, 0), (2, 2, 2, 1), (2, 2, 3, 1), (2, 2, 3, 2)]

祝你好运！