Neste trabalho modelamos o problema do caixeiro viajante com deadlines, visando minizar o atraso como descrito no enunciado:
Considere um veículo que deve partir de um ponto inicial, visitar n localidades e retornar ao ponto de partida após as visitas. Considere adicionalmente que cada localidade a ser visitada tem um prazo limite para receber a visita. Atrasos são permitidos, porém uma multa que aumenta com o tempo de atraso é imposta. Os dados apresentam as coordenadas cartesianas das localidades. Utilize a distância euclidiana (em linha reta) entre as localidades como tempo de percurso entre elas. Formule modelo de otimização que determine a rota que minimize o atraso total nas visitas.
A implementação do modelo se encontra na pasta notebooks em sua versão .py e .ipynb
O artigo desenvolvido em LATEX na pasta artigo
Os exports com os resultados obtidos no processamento das instâncias na pasta dados
Além de algumas referências utilizadas na pasta referencias
Resumo:
O problema do caixeiro viajante (PCV) é um clássico da literatura matemática, onde um vendedor deve visitar um conjunto de N cidades uma única vez e retornar ao seu ponto de origem, através de uma rota que minimiza a distância percorrida. Este trabalho propõe uma solução via modelo de programação matemática, para uma variante do problema original que conta com tempos limite para chegada a cada cidade, em que atrasos são permitidos e têm-se como objetivo minimizar o atraso geral da rota. Com a utilização da biblioteca PyMathProg exploramos a complexidade do PCV e os resultados estão expostos neste artigo.
O artigo resultado deste projeto pode ser encontrado em:
https://pt.slideshare.net/BrenoZukowski2/caixeiro-viajante-com-deadline-fatec-rp
Breno Zukowski
Henrique Ribeiro
Jean Silva
Paola Capita