|
Abstract:
|
Apresenta-se neste trabalho o Twin-Robot Pallet Assignment and Scheduling Problem (TRPASP), que consiste em determinar a programação de tarefas realizadas por robôs móveis dois robôs móveis posicionados em extremidades opostas ao longo de um trilho em ambientes de picking e delivery. O problema abrange a identificação de quais produtos devem ser coletados por cada robô, bem como a definição da sequência dessas coletas, com o objetivo de minimizar o tempo total necessário para a execução das tarefas. Além de respeitar as posições de coleta, é necessário atender às posições de entrega para formar os pedidos dos clientes. Para resolver instâncias de pequeno porte, propõe-se um modelo de programação linear inteira mista. Por se tratar de um problema NP-difícil (NP-Hard), foi desenvolvido um método heurístico capaz de obter soluções de boa qualidade em tempo computacional reduzido para instâncias maiores. Adicionalmente, são apresentados algoritmos meta-heurísticos baseados em busca local em vizinhanças variáveis (Variable Neighborhood Search – VNS, e Variable Neighborhood Descent – VND) como estratégias de reotimização. Os resultados mostram que as meta-heurísticas propostas melhoram os resultados da heurística em pelo menos 18% para instâncias de pequeno porte e alcançam melhorias de até 74,1% para instâncias de maior complexidade. Observou-se que o método VNS se destacou pelo menor tempo computacional requerido em instâncias de grande porte, apresentando uma redução média de 26% no tempo, em comparação ao VND, para todos os testes realizados. |
