Получите лучшее возможное решение, найденное после ограничения по времени - Целлюлоза - PullRequest
Новая
       39

Получите лучшее возможное решение, найденное после ограничения по времени - Целлюлоза

0 голосов
/ 06 марта 2019

Я пытаюсь решить проблему маршрутизации в нескольких депо с 10 клиентами и 5 депо с.При добавлении ограничения subtour решатель уже не находит оптимальное решение за разумное время.Когда через определенное время я останавливаю решатель и получаю лучшее решение, он возвращает неосуществимое решение (непрерывные переменные, в то время как требуются целые числа).Как я могу найти лучшее из найденных на данный момент возможных решений или есть даже другие способы решить мою проблему?Я знаю, что в стеке есть похожий вопрос, но он решает проблему для решателя gurobi.

Здесь вы можете найти некоторые части кода и вывод, который он мне даст через 10 секунд. 

# Definition of the route variables:
route_vars = plp.LpVariable.dicts("Route",(Places,Places,Trucks),0,None,plp.LpInteger)

# constraint 7: No subtours
for i in Places:
    for j in Places:
        for k in Trucks:
            if i != j:
                prob += u[i]-u[j] + (15)*route_vars[i][j][k] <= 14       


# Solve the problem
prob.solve(plp.PULP_CBC_CMD(maxSeconds=10))
print("status:", plp.LpStatus[prob.status])
print("optimal solution to the problem: ", plp.value(prob.objective))

# Print Results
for i in Places:
    for k in Trucks:
        for j in Places:
            if plp.value(route_vars[i][j][k]) != 0:
                print(plp.value(route_vars[i][j][k]), 'Truck ',k + 1, " from Place ",i+1, " to place ",j+1)

Вывод после запуска в течение 10 секунд: 

status: Not Solved
optimal solution to the problem:  348.1102769976801
0.066666667 Truck  7  from Place  1  to place  11
0.93333333 Truck  8  from Place  1  to place  11
0.066666667 Truck  4  from Place  2  to place  6
0.93333333 Truck  7  from Place  2  to place  6
0.066666667 Truck  2  from Place  3  to place  7
0.93333333 Truck  8  from Place  3  to place  7
0.93333333 Truck  1  from Place  4  to place  5
0.033333333 Truck  3  from Place  4  to place  5
0.033333333 Truck  3  from Place  4  to place  9
0.93333333 Truck  1  from Place  5  to place  9
0.033333333 Truck  3  from Place  5  to place  4
0.033333333 Truck  4  from Place  5  to place  9
0.066666667 Truck  4  from Place  6  to place  2
0.93333333 Truck  7  from Place  6  to place  2
0.066666667 Truck  2  from Place  7  to place  3
0.93333333 Truck  8  from Place  7  to place  3
0.066666667 Truck  2  from Place  8  to place  10
0.93333333 Truck  8  from Place  8  to place  10
0.93333333 Truck  1  from Place  9  to place  4
0.033333333 Truck  3  from Place  9  to place  4
0.033333333 Truck  4  from Place  9  to place  5
0.066666667 Truck  2  from Place  10  to place  8
0.93333333 Truck  8  from Place  10  to place  8
0.066666667 Truck  7  from Place  11  to place  1
0.93333333 Truck  8  from Place  11  to place  1

Как видите, это дает мне невыполнимое решение.

1 Ответ

0 голосов
/ 07 марта 2019

Неправильно определено ограничение Миллера-Такера-Землина на отсутствие подтуров.Вместо этого ограничение должно выглядеть следующим образом, где N - количество клиентов, а D - количество складов.

# constraint 8: No subtours (Miller Tucker Zemlin)
for i in range(0,N):
    for j in range(0,N):
        for k in Trucks:
            if j != i:
                prob += u[i]-u[j] + (N+D+1)*route_vars[i][j][k] <= N+D
...