Veículo De Roteamento / Recurso De Agendamento De Projeto De Algoritmos

Question

Meu primeiro post aqui, esperando que você pode me ajudar com a concepção de um algoritmo que tenho vindo a considerar, por um pouco de tempo agora – não tiver a certeza de qual a abordagem que tome (VRPTW ou agendamento de recursos, ou algo inteiramente!?)

Para colocá-lo em uma palavra real exemplo, nós temos um monte de resíduos de jardim por um pequeno número de locais (geralmente menos de 5).Os resíduos devem ser transportados para outros locais dentro de determinados períodos de tempo.Para mover os resíduos de jardim temos reboques, que deve ser rebocado por carros.Jardim de resíduos só podem ser descartadas no depósito de resíduos em determinados momentos (janelas de tempo).Em alguns sites que pode deixar a carreta para ser enchido ou esvaziado por pessoas de lá, mas em outros locais, o motorista do carro tem que fazê-lo a si mesmo e o carro deve permanecer lá.Todos os intervalos podem ser calculados (i.e.de carga / descarga vezes, os tempos de trânsito etc.).Carros podem se mover entre sites sem um reboque, reboques podem ser rebocado a branco, mas reboques não pode mover-se entre as localidades.

Nosso objetivo é assegurar a todos reboque de cargas de resíduos são transportados enquanto

• minimização do número de carretas e carros em uso
• reunião de todos os tempo do windows para deixar resíduos
• "balanceamento" trailers – i.e.no final do dia, temos como muitos trailers em cada local que estavam lá no início do dia

Pensei em aproximar-se desse como um recurso algoritmo de programação, mas eu não tenho certeza de como lidar com "balanceamento" de semi-reboques.

Um outro método que eu considerei foi a de considerar os carros de primeira.Eu poderia, em seguida, selecione a tarefa mais cedo e construir um gráfico de todas as tarefas, depois que.Se eu, então, pegou o caminho mais longo através do gráfico que gostaria de serviço, o número máximo de reboque de cargas.Eu poderia, então, remover essas tarefas na lista de tarefas e repita até que todas as tarefas foram atendidos.Eu teria, então, precisa correr sobre estes lista de reboque para cargas de trabalho com o número de reboques necessário.

De qualquer pensamento como a abordagem seria apreciada!

Answer 1

Concordo com Jiri...você quer um algoritmo heurístico que fica razoavelmente perto com uma solução aceitável rapidamente e, em seguida, refina a partir de lá.

Eu já trabalhei em empresas antes de que tinha de entrega de software de roteamento e a abordagem que eles tomaram foi a utilização de um algoritmo genético para resolver muito semelhante, embora muito maior escala, o problema.Tomar um veja aqui se você não estiver familiarizado com a abordagem.A partir desse site:

1. [Iniciar] Gerar uma população aleatória de n cromossomos (soluções adequadas para o problema)
2. [Fitness] Avaliar a adequação f(x) de cada cromossomo x na população

3. [Nova população] Criar uma nova população, repetindo os passos seguintes até que a nova população é completa

   [Seleção] Selecione pai de dois cromossomos de uma população de acordo com sua adequação (o melhor do fitness, a maior chance de ser selecionado)

   [Crossover] Com uma probabilidade de cruzamento cruze os pais para formar uma nova prole (filhos).Se não realizar cruzamento, a descendência é uma cópia exata dos pais.

   [Mutação] Com uma probabilidade de mutação mutação nova prole em cada locus (posição no cromossomo).

   [Aceitação] Coloque a nova geração de uma nova população

4. [Substituir] Utilize a nova população gerada para a próxima execução do algoritmo
5. [Teste] Se a condição é satisfeita, pare e retorne a melhor solução da população atual
6. [Loop] para Ir para o passo 2

O truque para isso é a codificação de suas limitações em um "cromossomo" e escrever o "fitness" função.A função objetivo tem que tomar entradas dos resultados de uma potencial solução e cuspir uma pontuação de como é bom uma solução que é ou jogá-lo fora se violar qualquer das restrições.

Como mencionado por Jiri, a vantagem desta solução é que ele vem com um viável, embora talvez não o melhor, resposta muito rápida e o mais você deixá-lo a funcionar, a melhor solução fica.

Answer 2

Estamos falando de um NP completo algoritmo aqui, com certeza, além do número de automóveis e reboques, esta não vai ser uma tarefa onde você gostaria de obter uma melhor solução de todas as possíveis soluções e, em seguida, ser capaz de descartar e ir novamente para evitar o caminho mais longo como você sugere.Se você criar seu algoritmo dessa forma, é muito provável que um dia você adicionar um pouco mais de automóveis e reboques e nunca concluir a solução de computação.

Você provavelmente quer ir com o algoritmo que pode razoavelmente rápida de gerar bons o suficiente solução do problema.Certifique-se de criar uma métrica de qualidade da solução, você obter uma boa maneira de estimar o valor da métrica para uma solução ideal, em seguida, definir-se alguns %, dentro do qual você gostaria de sua solução a partir de uma solução ideal e pegue a primeira solução que tem métrica dentro dos limites.Isto tem a vantagem adicional de se este algoritmo está levando muito tempo para calcular e anulá-lo, você ainda pode usar a solução com a menor métrica calculada, mesmo se não estiver na sua esperado limites.

Eu não tenho certeza de qual a abordagem que tome a resolução do problema em si embora.Gostaria de sugerir a leitura de alguns artigos, depois de procurar em acm portal.Eu diria UPS e Fedex provavelmente têm problemas semelhantes, se você adicioná-los como palavras-chave para uma pesquisa no google, você pode obter alguns resultados mais úteis.

Answer 3

Eu tendo a concordar com Robert.Isso soa para mim como um ótimo candidato para a evolução técnica de otimização, como a Genética, a implementação do Algoritmo que ele descreve.

Eu também tive muito sucesso em certos problemas com o Particle Swarm Optimization (PSO).Basicamente, você pode pensar de cada genoma como uma partícula em alguns multi-dimensional.As coordenadas da partícula são os parâmetros para o cálculo (função objetivo).Cada partícula é iniciado de forma aleatória com um random velocity.Para cada iteração da simulação, atualizar a posição de cada partícula, com a sua atual viagem vetor e, em seguida, adicionar componentes de outros vetores como:direção para o melhor de partículas para longe, em direção ao melhor de partículas cada vez, em direção a um grupo local best etc...

Pode parecer um pouco assustador à primeira para a implementação de um GA ou PSO mas eu garanto a você que é fácil escrever um pequeno framework que abstrai o algoritmo (GA/PSO) do domínio do problema que você está tentando otimizar.Você pode sempre cair de volta para a Wikipédia para mais detalhes dos algoritmos.

Assim que eu tiver um quadro, eu normalmente começam com um 2 problema de parâmetro (provavelmente uma simplificação do problema, ou X e Y locais de uma imagem), para que eu possa facilmente visualizar e ajustar o algoritmo de forma que eu tenho de bom enxame de comportamento.Então eu escala até mais dimensões.

Eu gosto dessa abordagem, pois me permite facilmente otimizar para os problemas que tenham bastante complexas e intrincadas peças para o problema real de instrução (como os automóveis e reboques).

Também, por isso que as técnicas evolutivas são atraentes porque você pode dedicar uma parcela fixa de tempo para a simulação, e tomar a melhor resposta até agora quando você decidir parar.

Na minha experiência, você tende a demorar muito tempo ajustando os parâmetros para o GA ou PSO (uma vez que você tem uma implementação) como você gostaria de escrever uma codificado heurística de solução, mas a vantagem é que mudar a estratégia para encontrar a solução, normalmente, requer alterações de parâmetros, ou só trocar muito bem definidos algoritmos com outra aplicação, como oposição a codificação de uma estratégia totalmente diferente para resolver o problema de forma heurística a partir do zero.

Por favor, me dê um grito se você precisar de orientação sobre a elaboração do genérico quadros para qualquer um dos dois algoritmos.Devo ressaltar, que você obter vários boa higiene festa de 3 quadros por aí também.Às vezes eu gostaria de código a minha própria, porque eu entendo cada aspecto do algoritmo, em seguida, e eu sei onde eu posso ajustar a estratégia.

Answer 4

Abordagem Geral:

Desde que o problema é pequeno, gostaria de sugerir uma abordagem onde você adicionar carros e reboques até obter uma solução viável ao invés de tentar minimizar automóveis e reboques.

Resolução de problemas:

Eu tenho tido menos sucesso em Gás com restrições e ainda menos sucesso no Gás com restrições nas variáveis de número inteiro (por exemplo,o número de reboques em um local).Pode ser que a restrição de programação é uma abordagem melhor, pois você só deseja gerar uma solução viável para um determinado número de automóveis e reboques, ao invés de tentar minimizar a distância percorrida.

Observação:

Você está resolvendo o problema em uma rede, onde os últimos movimentos podem ser para realocar um vazio trailer.

Boa sorte !

Answer 5

Local De Pesquisa são uma alternativa aos algoritmos genéticos.No Internacional Calendarização Concorrência 2007, local algoritmos de busca (tais como busca tabu e simulated annealing) bater claramente o algoritmo genético (entradas 1 para o 4º lugar para o LS versus 5º lugar do GA na faixa 1 em cerca de 80 competidores IIRC).

Também, dê uma olhada em algumas das bibliotecas lá fora, como OptaPlanner (Tabu Search, Simulated Annealing, Aceitação Tardia, open source, java), JGap (algoritmos genéticos, open source, java), OpenTS (Tabu Search, ...