Formulação de programação inteira para um problema de consolidação de cargas com frete morto e custos por múltiplas entregas

Neste artigo, consideramos um problema de consolidação de cargas no qual uma empresa remetente precisa entregar vários itens aos seus clientes em um único dia usando veículos terceirizados de múltiplos transportadores. Cada veículo possui informações de tipo, capacidade, carga mínima contratada, e tipos de itens que pode transportar. Um veículo pode visitar diferentes clientes se estiverem dentro de uma distância máxima permitida. Ademais, os preços dependem do tipo de veículo, do número de entregas (clientes diferentes visitados), do custo de transporte por unidade de peso dos itens consolidados, e do frete morto correspondente à disponibilidade não utilizada da carga mínima contratada dos veículos. Mostramos que mesmo uma variante restrita do problema é NP-difícil e propomos uma formulação de programação inteira. Experimentos preliminares utilizando instâncias sintéticas mostram que a distribuição de clientes em clusters favorece o melhor aproveitamento dos veículos e a encontrar boas soluções ao aumentar o número de itens.