ROUGH DRAFT authorea.com/118292
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Um algoritmo backpressure para o roteamento de entregas urbanas      

    1. INTRODUÇÃO

    Um algoritmo de roteamento backpressure refere-se a um método para o roteamento dinâmico de fluxo em uma rede multi-estágios utilizando-se gradientes de congestionamento. É um método de direcionamento do tráfego em uma rede de filas que busca atingir um throughput máximo da rede como um todo (Neely 2009). Primeiramente, foi utilizada em redes de dados e telecomunicações (Tassiulas 1992), mas pode ser aplicada a outros tipos de redes (Awerbuch 1993). Este algoritmo considera uma rede onde os clientes (veículos, jobs, pacientes, etc) pode visitar múltiplos nós de serviço na rede proposta.

    2. REDES DE FILAS

    Considere uma rede de filas multi-estágios com \(N\) nós (estágios). A rede opera em tempos discretos, denominados slots, \(t\in\{0,1,2,...\}\). O slot \(t\) representa o intervalo de tempo \([t,t+1)\). Em cada slot, novos clientes podem chegar a rede , e o plano de roteamento e de fluxo são realizados com o objetivo de entregar cada cliente ao seu destino requerido. Seja os clientes genéricos, \(c=\{1,...,N\}\), que serão destinados aos nós. Para \(n\in\{1,...,N\}\) e \(c\), seja \(Q_{n}^{(c)}(t)\) a quantidade de clientes no instante \(t\) no nó \(n\), também chamado de backlog. As unidades de \(Q_{n}^{(c)}(t)\) dependem do contexto do problema, podendo assumir unidades inteiras, ou fracionárias. Considera-se que \(Q_{n}^{(c)}(t)=0\) para todo \(c=\{1,...,N\}\) e todos os slots de tempo \(t\), por que os nós não armazenam nenhuma quantidade de clientes inicialmente.

    A cada slot de tempo, os nós enviam um fluxo de clientes aos outros nós, e estes são então removidos da fila do nó anterior, e adicionados a fila do nó posterior. Os clientes chegam de forma exógena a rede, e \(A_{n}^{(c)}(t)\) é definida como a quantidade de novos clientes que chegam ao nó \(n\) no tempo \(t\) que eventualmente pode ser roteado para o nó \(c\).

    Seja \(\mu_{ab}(t)\) a taxa de fluxo usada pela rede \(G\) no link \((a,b)\in G\) no slot de tempo \(t\), representando a quantidade de clientes que podem ser transferidos do nó \(a\) ao nó \(b\) no tempo \(t\). Portanto, \(\Gamma=[\mu_{ab}(t)]\) é a matriz de taxas de fluxos no tempo \(t\).

    Caracterização da rede de filas
    A dinâmica das chegadas
    Topologia da rede e taxas de fluxos
    Capacidade da rede