The profitable single truck and trailer routing problem with time windows

Abstract

Neste trabalho, investigamos o Problema do Roteamento Mais Lucrativo de Veículo com Reboque e com Janelas de Tempo. Nesse problema, são dados uma frota contendo caminhões e reboques, além de um conjunto de clientes, que fornecem uma recompensa caso sua demanda seja coletada por um veículo. Os reboques podem ser acoplados aos caminhões para aumentar a capacidade do veículo; em compensação, a velocidade do veículo é reduzida, e os custos de viagem são aumentados. Alguns clientes só podem ser atendidos por caminhões desacoplados, o que pode dar origem a rotas em que um reboque é desacoplado do caminhão em vértices satélite dados. O caminhão pode, então, viajar alguns trechos da rota desacoplado, após os quais retorna ao ponto onde o reboque foi estacionado, e a carga coletada pelo caminhão é transferida para o reboque. O objetivo do problema é encontrar uma escolha de veículo e uma rota a ser percorrida por ele, para a qual o lucro, dado pelas recompensas coletadas menos os custos de viagem, seja máximo. Propomos uma formulação de Programação Inteira para o problema, além de desigualdades válidas e estratégias de lifting, capazes de reforçar as relaxações lineares da formulação. A formulação desenvolvida emprega apenas variáveis binárias e garante o cumprimento das restrições de capacidade, janelas de tempo e sincronização das operações de acoplamento, transferência de carga e desacoplamento, por meio de cortes de Benders Combinatórios. Pelo que conhecemos, esta é a única formulação compacta no espaço de variáveis que permite múltiplas sub-rotas partindo do mesmo vértice satélite. Em trabalhos anteriores, diferentes variações do Problema de Roteamento de Veículo com Reboque (PRVR) têm sido tratadas. Essas variações são caracterizadas por considerar ou não algumas propriedades importantes na modelagem do problema, como janelas de tempo para os clientes, vértices satélite dedicados, frota heterogênea e tempos de transferência dependentes da carga. Nosso modelo lida com todos esses aspectos listados, além de considerar velocidades diferentes para veículos da frota e velocidades reduzidas para o caminhão quando acoplado a um reboque, o que, segundo nossa pesquisa, ainda não havia sido abordado na literatura sobre PRVRs. Desenvolvemos um algoritmo exato Branch-and-Cut para o problema e apresentamos resultados computacionais. Os resultados sugerem que as desigualdades válidas aqui introduzidas não apenas melhoram os limites duais mas resultam em melhores algoritmos Branch-and-Cut.