Branch and Price Algorithm

Question

O ramal e o preço podem ser uma abordagem de boa solução para um problema de roteamento com função objetivo mín-máx? Por exemplo, minimizar o comprimento máximo de qualquer rota de veículo em um VRP.

Na literatura, nunca vi que essa abordagem de solução fosse usada para resolver esse problema. Pelo que eu sei, essa abordagem é usada para resolver VRPs minimizando o custo total.

Answer 1

Ser uma abordagem boa ou ruim dependerá de vários fatores, por exemplo:

• o tamanho das instâncias
• tempo disponível para encontrar uma solução (isso tende a ser uma questão importante em aplicações de roteamento de veículos)
• poder de computação
• qual nível de qualidade da solução é qualificado como bom o suficiente

Veja este trabalho de Yu, Nagarajan e Shen sobre o VRP do makespan mínimo com restrições de compatibilidade, já que é um problema semelhante que foi estudado antes de usar branch-and-price como uma abordagem para resolver uma variante do VRP do makespan. Funcionou muito bem. Observe que, no caso deles, eles projetaram um algoritmo de aproximação para acelerar o tempo de execução do B&P.

Eu sugiro o seguinte experimento:

Primeiro passo: Seguindo a resposta de @RobPratt à sua pergunta anterior sobre a minimização do makespan no VRP :

Deixei $d_i$ seja a demanda do cliente $i\in N$, deixei $V=\{1,\dots,K\}$ seja o conjunto de veículos, e deixe $P$ ser o conjunto de colunas, onde cada coluna corresponde a um subtour viável a partir do depósito, com variáveis ​​de arco $x_{i,j}$ e variáveis ​​de nó $y_i$. Deixei$z$seja o makepan. O problema principal acabou$z$ e $\lambda$é o seguinte, com variáveis ​​duais entre parênteses: \ begin {align} & \ text {minimize} & z \\ & \ text {subject to} & z - \ sum_ {p \ in P} \ left (\ sum_ {i, j } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {para$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {para $i\in N$} && (\ text {$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {para $v\in V$} && (\ text {$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {para $v\in V$ e $p\in P$} \ end {align}

O subproblema de geração de coluna acabou $x$ e $y$ para cada $v\in V$ é, então, minimizar o custo reduzido de $\lambda^p_v$. Ou seja, minimizar$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ sujeito a $(x,y)$ formando um subtour viável a partir do depósito, com $\sum_i d_i y_i \le L$, Onde $L$ é a capacidade de cada veículo.

Conforme declarado lá, o subproblema pode ser reformulado como caminho mais curto elementar: Divida o depósito em uma fonte e um sumidouro e mova os pesos dos nós para os arcos: $\pi_v c_{i,j}−\alpha_i$ pelo peso do arco $(i,j)$ no subproblema do caminho mais curto elementar.

Segundo: Implementar o método acima. Eu recomendo tentar usar o VRPy, como sugerido por Kuifje aqui . Dessa forma, você não terá que implementar todas as operações de agências e preços do zero. Etapas detalhadas:

1. Dê uma olhada na documentação do projeto.
2. Dê uma olhada no código no GitHub.
3. Crie uma bifurcação ou baixe o projeto como .zip, de forma que você possa fazer alterações localmente.
4. Modifique o código referente ao subproblema , de forma que o depósito seja dividido conforme explicado acima.
5. Execute os experimentos, você pode seguir as instâncias de exemplo da documentação como aqui e aqui .
6. Deixe-nos saber como funcionou. E lembre-se de agradecer a VRPy e seus desenvolvedores em seu trabalho (seja um relatório de projeto, tese, publicação, etc), bem como respeitar os termos da licença da biblioteca no que diz respeito a modificações.

Answer 2

VRPy (v0.3.0) agora suporta esta opção: tudo que você precisa fazer é definir a minimize_global_spanopção ao Trueinstanciar o VehicleRoutingProblemobjeto:

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

Claro, seu gráfico $G$ tem que ser bem definido em primeiro lugar.

A formulação proposta por @RobPratt é implementada. Se você brincar com alguns problemas de brinquedo, verá que a formulação é fraca em comparação com a clássica (sem o makespan). É fácil ver que a restrição$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ in V$} $$ é responsável por isso.

Você também pode tentar a seguinte abordagem alternativa:

1. Resolva o problema sem a opção min_max

2. Consultar o maior período

3. Resolva novamente sem min_max, mas restrinja o problema de forma que cada rota tenha uma extensão menor do que a maior consultada em 2.

4. Se inviável, pare; caso contrário, vá para a etapa 2.

Tudo isso é direto com o ecossistema do VRPy. Diverta-se.