Как избавиться от подтур и навязать определенный порядок в точках посещения, используя гуробипы? - PullRequest
Новая
       41

Как избавиться от подтур и навязать определенный порядок в точках посещения, используя гуробипы?

0 голосов
/ 24 сентября 2019

Мне известно, что на сайте Gurobi есть пример TSP.Мне потребовалось много времени, чтобы понять это, однако я не смог (полностью).Поэтому я решил сам сделать более простой.

Проблема: Я не могу избавиться от под-туров и не знаю, как и какое ограничение яследует включить посещение пунктов выдачи перед отправкой в ​​пункт доставки.Нет необходимости немедленно идти от пункта получения до пункта доставки.Хорошо, если перед отправкой в ​​точки доставки посещают несколько пунктов получения.

Мой код выполняет следующие действия: он генерирует случайные заказы, содержащие: пункты получения, точки доставки и количество отправляемых пакетов (еслиэто успешно, я также хочу включить время доставки, вместимость транспортного средства, несколько транспортных средств и т. д.).После генерации заказов он создает матрицу расстояний между транспортными средствами, подбирает баллы и доставляет баллы.Затем я использую оптимизатор Gurobi, чтобы найти оптимальный маршрут.Мне удалось добавить ограничения, которые мешают путешествовать из точки i в точку i.Я добавил ограничение на посещение каждой точки и, поскольку это симметричная матрица, я также добавил ограничение, которое предотвращает перемещение между двумя точками: 0 - 4 - 0 - 4 -... 

# Using spyder 3.6 and gurobi. For simplicity I only added the DISTANCE matrix, not how the orders and distance matrix are created

import numpy as np
from gurobipy import *

DISTANCE = [[0, 96.64884893, 94.41398202, 88.23264702, 18.86796226, 97.52948272, 105.99056562],
    [96.64884893, 0, 183.14202139, 19.02629759, 80.77747211, 194.17775362, 189.1692364],
    [94.41398202, 183.14202139, 0, 169.53170795, 113.25193155, 55.22680509, 122.58874337],
    [88.23264702, 19.02629759, 169.53170795, 0, 74.81310046, 185.01081049, 187.01069488],
    [18.86796226, 80.77747211, 113.25193155, 74.81310046, 0, 114.28035702, 113.35784049],
    [97.52948272, 194.17775362, 55.22680509, 185.01081049, 114.28035702, 0, 73.00684899],
    [105.99056562, 189.1692364, 122.58874337, 187.01069488, 113.35784049, 73.00684899, 0]]

dist = np.array(DISTANCE)
n=dist.shape[0]

# Create model
m = Model('Pickup_Deliver_Optimizer')

# Add variables
x = {}                    
for i in range(n):  
    for j in range(n):  
        x[i,j] = m.addVar(vtype=GRB.BINARY)  

# Objective function
obj = (quicksum(x[i,j]*DISTANCE[i][j] for i in range(n) for j in range(n)))
m.setObjective(obj, GRB.MINIMIZE)

# Constraints
# Constraint that does not allow to travel from point i to point i
for i in range(n):
    m.addConstr(x[i,i],GRB.EQUAL,0) 

# To prevent the vehicle from returning to the same point from the previous point: if x[i,j] == 1, then x[j,i] == 0
m.addConstrs((x[i,j] == 1) >> (x[j,i] == 0) for i in range(n) for j in range(n))

# Visit all points by making a connection between two points
for i in range(n):
    m.addConstr(quicksum(x[i,j] for j in range(n)),GRB.EQUAL,1)
    m.addConstr(quicksum(x[j,i] for j in range(n)),GRB.EQUAL,1)

# The vehicle should return to its starting point
m.addConstr(quicksum(x[i,0] for i in range(n)),GRB.EQUAL,1)

# The vehicle always starts at its starting point
m.addConstr(quicksum(x[0,i] for i in range(n)),GRB.EQUAL,1)

m.update()
m.optimize()

Используя пример TSP от Gurobi, оптимальное решение должно быть ~ 522.Результат, который я получаю, составляет ~ 457.Разница является результатом разных маршрутов.Согласно примеру Гуроби правильным должно быть [0, 4, 1, 3, 2, 5, 6, 0].Мой код создает следующие два цикла: [0, 4, 1, 3, 0] и [2, 5, 6, 2].Два комбинированных маршрута имеют более короткое расстояние, чем один маршрут из примера Gurobi, поэтому я получаю два маршрута как оптимальное решение.Я знаю, что идет не так, но я понятия не имею, как решить эту проблему с помощью addConstr ().В Интернете я посмотрел, какая теория скрывается за этим, согласно методу Миллера-Такера-Землина в Википедии https://en.wikipedia.org/wiki/Travelling_salesman_problem, Мне нужно добавить новое ограничение 'u'.Тем не менее, я думаю, что это можно решить проще, добавив следующее ограничение: 

# Create one route
for j in range(n):
    if j != 0:
        m.addConstrs((x[i,j] == 1) >> (quicksum(x[j,k] == 1)) for i in range(n) for k in range(n))

Эта строка кода не работает, но, похоже, что-то подобное должно решить проблему.Это заставит узлы соединяться друг с другом.

Вторая проблема, которую я не могу решить, это посещение пункта получения до пункта доставки.Нечетные строки / столбцы в матрице DISTANCE представляют точки получения, а четные строки / столбцы представляют точки доставки (строка / столбец 0 является начальной точкой транспортного средства).Могу ли я решить эту проблему с помощью текущей переменной x [i, j] или мне нужно добавить дополнительную переменную (которую я ожидаю)?

Любая помощь очень ценится.

...