ComeçarComece de graça

Problema do caixeiro-viajante (TSP)

O Problema do Caixeiro-Viajante (TSP) é um problema clássico com aplicações em logística. No TSP, um vendedor recebe uma lista de cidades e as distâncias entre cada par. Ele busca a rota mais curta que sai da cidade de origem, passa por todos os pontos e retorna à cidade de origem. Esse é um problema computacionalmente difícil, mas Miller-Tucker-Zemlin (MTZ) mostraram que ele pode ser resolvido usando Programação Linear Inteira. Neste exercício, você vai definir a função objetivo e algumas restrições do TSP para um pequeno conjunto de dados com 15 cidades (veja a imagem abaixo). Seu objetivo é praticar o uso de LpVariable.dicts com list comprehension.

Photo of Cities

Três variáveis Python n, cities e dist já foram criadas para você \(^{1}\). A variável n é o número de cidades, cities é uma lista com as cidades numeradas e dist é um DataFrame do pandas com a distância entre cada par de cidades. Você pode explorá-las no console. Além disso, o modelo já foi inicializado para você.

\(^{1}\) Conjunto de dados de Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Este exercício faz parte do curso

Análise de Cadeia de Suprimentos em Python

Ver curso

Exercício interativo prático

Experimente este exercício completando este código de exemplo.

# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____], 
                     cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____], 
                     lowBound=0, upBound=(n-1), cat=____)
Editar e executar o código