Estratégias de pricing para o problema de orientação de times com conjuntos

Abstract

Neste trabalho estudamos o Set Team Orienteering Problem (STOP) que consiste em encontrar múltiplas rotas para uma frota de veículos de forma que respeitem uma restrição de tempo e maximizem os lucros coletados, que estão associados a conjuntos de clientes. Para resolver o STOP, propomos um algoritmo branch-and-price juntamente com estratégias para o subproblema de pricing. Como o subproblema de pricing é um problema NP-difícil, usamos uma rexação no estado da arte para problemas de roteamento de veículos, a relaxação ng-route e algumas técnicas de aceleração conhecidas: Decremental State Space Relaxation (DSSR) e o Bidirectional Labelling. Avaliamos nosso algoritmo com instâncias derivadas do Team Orienteering Problem (TOP), uma vez que não existiam instâncias conhecidas para STOP. Os testes mostram que o Bidirectional Labelling tem um impacto positivo no desempenho do algoritmo.