Uma Heurística Eficiente para o Problema de Roteamento de Veículos com Coleta e Entrega Rentáveis

Abordamos neste trabalho o Problema de Roteamento de Veículos com Coleta e Entrega Rentáveis (MVPPDP), um importante problema NP-difícil ligado a várias aplicações práticas, incluindo o transporte marítimo. Esse problema combina dois atributos desafiadores de roteamento de veículos: 1)coleta e entrega um-para-um e 2)seleção de clientes. Lidar com os dois atributos requer vizinhanças avançadas de busca local e procedimentos de exploração eficientes. Para resolver o MVPPDP, propomos um algoritmo heurístico (denominado IPPD) baseado em Busca Local Iterada e Descida de Vizinhança Variável Aleatória. Este método explora soluções inviáveis ​​durante a pesquisa com possíveis violações de restrições de duração. Para reduzir o espaço de busca, usamos restrições de vizinhança com base na busca local granular. Nossos experimentos computacionais em 36 instâncias clássicas da literatura demonstraram o bom desempenho do IPPD, que encontrou novas melhores soluções conhecidas para 6 instâncias e também alcançou 20 soluções melhores ou iguais a métodos da literatura.