[pt] BUSCAS EFICIENTES EM VIZINHANÇAS LARGAS PARA O PROBLEMA DO CAIXEIRO VIAJANTE COM COLETA E ENTREGA

• Ano de defesa: 2018
• Autor(a) principal: TONI TIAGO DA SILVA PACHECO
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] PROGRAMACAO DINAMICA; [pt] VIZINHANCA; [pt] COLETA-ENTREGA; [pt] CAXEIRO VIAJANTE; [pt] BUSCA LOCAL; [en] DYNAMIC PROGRAMMING; [en] NEIGHBORHOOD; [en] PICKUP-AND-DELIVERY; [en] TRAVELING SALESMAN PROBLEM; [en] LOCAL SEARCH
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=35781&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=35781&idi=2; http://doi.org/10.17771/PUCRio.acad.35781

[pt] Em vários problemas de distribuição e logística, os produtos devem ser coletados em uma origem e entregues em um destino. Exemplos incluem o transporte de pessoas com deficiência, serviços de correio expresso, logística de suprimentos médicos, etc. O problema de roteamento abordado neste trabalho, conhecido como Traveling Salesman Problem with Pickup and Delivery (TSPPD), é da classe de problemas do caixeiro viajante com restrições de precedência. Neste problema, existe um mapeamento um-para-um entre coleta-entrega no qual cada cliente do tipo coleta possui um cliente do tipo entrega associado. Os clientes do tipo entrega somente podem ser visitados posteriormente à coleta associada. O TSPPD é um problema NP-difícil uma vez que generaliza o Traveling Salesman Problem (TSP). O TSP pode ser visto como um caso particular do TSPPD onde cada coleta coincide espacialmente com a respectiva entrega. As variantes com restrições de capacidade, janelas de tempo e diferentes políticas de carregamento têm recebido maior atenção na última década, embora ainda existam significantes avanços a serem realizados em termos de qualidades de soluções na versão básica do problema. Para resolver este problema, propomos um algoritmo meta-heurístico híbrido com vizinhanças largas exploradas eficientemente em O(n2). Nossos experimentos demonstram uma redução significativa no tempo computacional e também melhoria na qualidade de soluções previamente conhecidas na literatura.