Exact methods for the traveling salesman problem with drone

Roberti, R., & Ruthmair, M. · 2021

full-text

Um trabalho que ampliou até onde um método exato consegue levar o percurso de um caminhão e um drone. A frase «resolveu até trinta e nove clientes» não pode ser trocada por «resolveu uma cidade». O cartão está na estante para impedir essa troca.

O resumo publicado diz que eles levam recursões de programação dinâmica para um método de branch-and-price sobre uma formulação de particionamento de conjuntos, com relaxação de ng-rotas e ramificação hierárquica em três níveis. Esse branch-and-price, escrevem, resolve até a otimalidade instâncias de até trinta e nove clientes, mais que dobrando o tamanho então considerado tratável. Os cenários deles também indicam que um drone, se for rápido o bastante, pode reduzir significativamente o tempo de conclusão de uma rota.

Trinta e nove é uma contagem de clientes em uma instância. Vento, espaço aéreo proibido, envelhecimento da bateria e autorização regulatória não estão no centro do método exato. «Significativamente» é a palavra deles, sob as hipóteses de velocidade deles, não uma contagem de minutos para uma cidade específica. O texto completo não foi rederivado para este cartão.