Algoritmo de geração de coluna

Question

Quero resolver um VRP com um algoritmo de geração de coluna. O objetivo do problema é a minimização do makespan. mas há um ponto no cálculo do tempo de chegada do veículo em cada nó. o veículo deve ser sincronizado com outro modo de transporte como um trem cuja rota é predeterminada antes de resolver o VRP acima mencionado. o trem pode passar de alguns nós por onde o veículo vai passar e nesses nós o tempo de chegada é máximo do tempo de chegada do trem e do veículo. Quero saber como devo resolver o subproblema de preços?

Answer 1

Se entendi seu problema corretamente, então a única diferença com a versão inicial (sem o trem) é que a função de tempo não é aditiva.

Por exemplo, digamos que o trem passa pelo nó $j$ na hora (dada) $t_j$, e você está calculando um caminho $p$ cujo último nó é $i$. O tempo total acumulado neste caminho é denotado por$\tau_p(i)$. $\Delta t_{ij}$ denota o tempo que leva para o veículo ir de $i$ para $j$. Se você deseja estender o caminho e adicionar nó$j$, então o tempo total acumulado para o caminho $p$, $\tau_p$, é aumentado da seguinte forma: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$

Se o trem chegar antes do veículo, o tempo total acumulado assume valor $\tau_p(i) + \Delta t_{ij}$, caso contrário, leva valor $t_j$.

Observe que isso é como ter janelas de tempo em seus nós de trem, com apenas um limite inferior: você pode apenas adicionar janelas de tempo $[t_j, +\infty[$ no nó $j$ e execute seu algoritmo de caminho mais curto com janelas de tempo (se você tiver uma em mãos).

Em outras palavras, a função de extensão de recurso (de tempo) não é aditiva. Isso é tratado, por exemplo, por cspy , uma ótima biblioteca python que calcula os caminhos mais curtos com restrições de recursos, onde você pode inserir sua própria regra de extensão de recurso personalizada (verifique os documentos onde esse exemplo é fornecido). VRPy , uma biblioteca python VRP para o VRP depende do cspy para calcular seus caminhos mais curtos para geração de colunas. Como o VRPy lida com janelas de tempo, você tem um bom ponto de partida!