UMA ANÁLISE SOBRE O PROBLEMA DO CAIXEIRO VIAJANTE ELÉTRICO COM PASSAGEIROS

Neste artigo apresentamos uma analise sobre o Problema do Caixeiro Viajante Eletrico com Passageiros - PCVEP. O problema e uma variante do classico Problema do Caixeiro Viajante (PCV), que considera elementos de compartilhamento solidario de assentos em veiculos, alem do advento do veiculo utilizado pelo caixeiro ser unicamente eletrico, sendo ambas as questoes atuais, importantes e bastante discutidas nas areas de pesquisa operacional e otimizacao combinatoria. No PCVEP, alem de se determinar a menor rota mediante um conjunto de cidades como no PCV, os custos de deslocamento do motorista sao reduzidos atraves do rateio das despesas, ou seja, mediante o compartilhamento de assentos com os passageiros por meio de ridesharing. Alem disso, o PCVEP deve considerar uma autonomia linear a capacidade de deslocamento, incluindo uma restricao de recarga da autonomia antes do recarregamento. Este trabalho apresenta a descricao, o estado da arte, os algoritmos propostos e os experimentos computacionais. O banco de instancias e composto por 69 problemas, sendo 55 randomicas e 14 advindas da TSPLIB e adaptadas ao PCVEP. Os resultados obtidos sao analisados e as conclusoes acerca do desempenho sao expostas.,