Skip to content

pah-10/caixeiro_viajante_time_window

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

51 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

P2 de Programação Linear - Fatec Ribeirão Preto

Sobre o trabalho

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.

Como navegar neste repositório

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

Artigo

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

Autores

Breno Zukowski

Henrique Ribeiro

Jean Silva

Paola Capita

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • JetBrains MPS 35.1%
  • CLIPS 33.8%
  • Jupyter Notebook 21.2%
  • TeX 8.4%
  • Python 1.5%