Проблема с маршрутизацией автомобиля: «Решение невозможно» с PuLP при связывании переменной «путь (X)» и переменной «Delivered_Quantity» - PullRequest
Новая
       34

Проблема с маршрутизацией автомобиля: «Решение невозможно» с PuLP при связывании переменной «путь (X)» и переменной «Delivered_Quantity»

2 голосов
/ 30 октября 2019

Пытаясь минимизировать общее расстояние перемещения (используя целлюлозу), я получил неосуществимое решение, пока оно явно выполнимо.

Решение становится невозможным, когда я связываю переменную "путь (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])

Знаете ли вы, что может быть не так?

...