A Lawn King

Em Adulyasak et al. (2013b), quatro formulações para o problema em estudo foram propostas, classificadas em índice de veículo e formulações de índice não-veículo. As formulações dos índices de veículos são nomeadas F (OU) | k e F (ML) | k e modele o problema quando a diretiva OUandML for aplicada, respectivamente. Essas formulações, em sua versão básica, são equivalentes a (k − S − ou) e (k − A − ml), respectivamente. As formulações do índice não-vivas são denominadas F (OU) | nk e F (ML) | nk e são derivadas de F (OU) | k e F (ML) | k, respectivamente, sem fazer uso do índice e modelagem de veículos as restrições de capacidade e roteamento como restrições semelhantes às SECs fracionárias generalizadas (GFSECs) para os VRPs. Estas últimas formulações têm a vantagem de usar menos variáveis do que as formulações de índices de veículos (o número de variáveis diminui proporcionalmente de acordo com a frota

tamanho), mas ainda tem um tamanho exponencial em termos de número de restrições. Pelo contrário, o fluxo formulações propostas na Seção 3.2 mantêm o número de variáveis pequenas enquanto são polinomiais em termos de número de restrições. Em Coelho e Laporte (2013), apenas as formulações de índice de veículos proposto. Esses modelos são semelhantes a (k − A − ou) e (k − A − ml). Em particular aqui, para cada período de tempo, os SECs são substituídos pela versão de três índices do Miller et al. (1960) restrições. Isto dá origem a formulações de tamanho polinomial com um grande número de variáveis e limites mais fracos. Finalmente, as reformulações do problema derivadas da subestrutura de dimensionamento de lote de item único foi proposto muito recentemente em Avella et al. (2013).

4. Desigualdades válidas

4.1. Desigualdades válidas herdadas

Algumas das desigualdades que consideramos são extensões das desigualdades válidas propostas por Archetti et al. (2007) para a versão de veículo único do problema.

As primeiras desigualdades fortalecem as restrições da política de reposição. As desigualdades afirmam que se entre os períodos de tempo t - τ et o cliente não for visitado, o nível de estoque em t - τ deve ser suficiente para cobrir o consumo entre os dois períodos de tempo. Distinguir entre veículo formulações de índice e fluxo, as desigualdades (SC1) são formuladas como

...