CONTRIBUIÇÃO AO PROBLEMA DE PROJETO DE REDES DE
TRÁFEGO: ALGORITMOS PARA CALCULAR UMA SOLUÇÃO
PEDRO CANALES GARCÍA
Tese apresentada ao Centro de Ciências e
Tecnologia, da Universidade Estadual do Norte
Fluminense, como parte das exigências para
obtenção do grau de Doutor em Ciências de
Engenharia.
Orientadora: Profa. Gudélia Morales Boluarte
CAMPOS DOS GOYTACAZES – RJ
FEVEREIRO – 2002
ii
CONTRIBUIÇÃO AO PROBLEMA DE PROJETO DE REDES DE
TRÁFEGO: ALGORITMOS PARA CALCULAR UMA SOLUÇÃO
PEDRO CANALES GARCÍA
Tese apresentada ao Centro de Ciências e
Tecnologia, da Universidade Estadual do Norte
Fluminense, como parte das exigências para
obtenção do grau de Doutor em Ciências de
Engenharia.
Aprovada em......................................................................
Comissão Examinadora:
Profa . Gudélia Morales Boluarte D.Sc., UENF (Presidente)
Prof. Amaranto Lopes Pereira D.Sc., UFRJ
Prof. José Ramón Arica Chávez D.Sc., UENF
Prof. Geraldo Galdino de Paula Júnior, D.Sc., UENF
iii
Agradecimentos
À Profa. Morales, minha orientadora, por sua dedicação na orientação deste
trabalho.
Ao
Prof.
Arica,
pelas
dicas,
observações
e
o
acompanhamento
no
desenvolvimento deste trabalho.
Aos membros de minha família, por sua infinita paciência em me esperar até
chegar ao final de meu trabalho.
À FENORTE pelo suporte financeiro prestado.
Aos profissionais e colegas que contribuíram com informações para o
desenvolvimento deste trabalho.
À Universidad Nacional de Ingeniería de Lima-Perú, pelo apoio financeiro y
liberação para realizar esta pesquisa na UENF.
iv
Tese apresentada ao CCT/UENF como parte das exigências para a obtenção do
grau de Doutor em Ciências de Engenharia.
CONTRIBUIÇÃO AO PROBLEMA DE PROJETO DE REDES DE TRÁFEGO:
ALGORITMOS PARA CALCULAR UMA SOLUÇÃO
Pedro Canales García
Fevereiro/2002
Orientadora : Profa. Gudelia Morales
Área de Concentração: Engenharia de Produção
RESUMO
Neste trabalho estuda-se um dos problemas de transporte conhecido como
Projeto de Redes de Tráfego (PRT). Este problema considera o interesse do
administrador do sistema de transporte, de melhorar o desempenho do sistema, e
o interesse dos usuários, de minimizar seus tempos (custos) generalizados de
viagem. O problema PRT é modelado como um problema conhecido em
otimização como de Programação de Dois Níveis Generalizado, onde no primeiro
nível minimiza-se uma função que representa o custo do sistema e no segundo
nível se resolve um problema de equilíbrio de tráfego (ET) modelado como uma
desigualdade variacional (DV).
Alguns resultados da teoria não diferenciável são considerados com o
intuito de ter uma alternativa de solução dos problemas PRT, pois nestes casos as
funções envolvidas são não diferenciáveis.
Para o cálculo de uma solução do PRT propomos um algoritmo que
denominamos de Projeto-Alocação e outro de Penalidades. Adicionalmente alguns
resultados computacionais sobre redes de tráfego de tipo acadêmico são
apresentados.
v
Thesis submited to the CCT/UENF in partial fulfillment of the requeriments for the
degree of Doctor of Sciences of Engineering
CONTIBUTION TO TRAFFIC NETWORK DESIGN PROBLEM:
ALGORITHMS FOR CALCULATE A SOLUTION
Pedro Canales García
February/2002
Advisor: Profa. Gudelia Morales Boluarte
Major Subjet: Production Engineering
ABSTRACT
This work studies the transportation problem know as Network Design Problem
(NDP). This problem consider the interest of the management transportation
system for improve the network performance, and the user’s interest minimum
travel time. The problem NDP is formulated as a problem know in mathematical
optimization as Generalized Bilevel Programming Problem, where the first level
minimize a function of the costs system and the second level solve the equilibrium
traffic problem, formulated as a variational inequality (VI).
Some results of the nondifferentiable theory are considered for alternative solutions
of the network design problem, hence functions envolved are nondifferentiable.
To obtention of a numerical solution of NDP, we consider an algorithm called
Design-Assignment and another considering one Penalties. We also present some
computational results on network traffic simulated.
vi
SUMÁRIO
Capítulo 1 – Introdução
1
Capítulo 2 – Referencial Histórico
7
Capítulo 3 – Alguns resultados da teoria diferenciável e não diferenciável
17
3.1 – Conceitos Básicos
18
3.2 – Condições de Otimalidade
26
3.3 – Linearização de Problemas sem Restrições
28
3.4 – Métodos para Problemas de Otimização não Diferenciável
31
3.4.1 – Métodos Sub-gradientes
31
3.4.2 – Métodos de Feixes
34
3.5 – A função Valor
38
Capítulo 4 – Formulação do Problema de Projeto de Redes de Tráfego
41
4.1 – Preliminares
41
4.1.1 – O Problema de Projeto de Redes de Tráfego (PRT)
42
4.1.2 – O fluxo de equilíbrio do usuário e o fluxo ótimo do sistema para
um modelo de dois níveis do PRT
43
4.2 – Formulação do Problema PRT
44
4.3 – Metodologia
47
Capítulo 5 – Algoritmo de Projeto-Alocação e de Penalidade
50
5.1 – Algoritmo Projeto-Alocação (P-A) para o projeto de redes de tráfego
51
5.2 – Adaptação do algoritmo de minimização da função gap, para resolver
um problema de equilíbrio de tráfego formulado como uma DV
52
5.3 – Sequência de problemas aproximados que resolvem o problema (P)
54
5.4 – Passos do algoritmo de minimização da função gap
54
vii
5.5 – Algoritmo de Penalidade para o problema PRT
55
5.6 – Teoremas de existência e unicidade da solução do problema de
equilíbrio de tráfego
59
5.6.1 – Existência e unicidade da solução no caso equilíbrio de tráfego
62
5.6.2 – Propriedade de monotonia estrita da função de tipo BPR
70
5.7 – Exemplos de Problemas de Tráfego
71
5.7.1 – Exemplo 1
71
5.7.2 – Resultados computacionais para o exemplo 1
73
5.7.3 – Exemplo 2
74
5.7.4 – Exemplo 3
75
5.7.5 – Exemplos para o problema PRT formulados como um programa
matemático de dois níveis generalizado (PDNG)
80
Capítulo 6 – Conclusões
94
Referências
97
viii
1
CAPÍTULO 1
Introdução
1 Os Problemas de Transporte
Ninguém duvida que o transporte é um sistema importante do mundo moderno
que envolve muitos problemas sociais, econômicos, ambientais e tecnológicos. Com o
desenvolvimento da tecnologia, cresceram ainda mais os desafios para serem
resolvidos neste sistema. Uma maior dificuldade acontece quando se trata de modelar
um problema que tome em consideração as condições de saturação da rede. Por
exemplo, quando a função de custo de viagem em uma via (arco) depende, além do
fluxo da própria via, dos fluxos das outras vias. Isto geralmente acontece em vias de
tráfego de mão dupla, ou pela formação de filas nas interseções sinalizadas, ou pelos
tempos de espera nas paradas, ou outros incidentes.
Nos últimos tempos, o incremento desmesurado de veículos motorizados tem
piorado o congestionamento no tráfego, o incremento dos tempos de viagens e de
espera nas paradas de ônibus, a insegurança dos usuários, etc. A demanda por serviço
é cada vez maior, entretanto a oferta de facilidades físicas não aumenta na mesma
proporção. Para acomodar níveis crescentes de demanda para viagens na rede,
usualmente se costuma aumentar a capacidade das vias já existentes ou, quando
possível, construir novas vias ou rotas. Nestes casos, um problema crucial é saber
como escolher a locação dessas vias de transporte (arcos), ou como aumentar a
capacidade delas sob orçamentos limitados do sistema. Para tomar uma decisão,
deverá ser considerado o interesse dos usuários que é, minimizar o custo total de
viagem. Este problema é conhecido como problema de Projeto de Redes de Tráfego
(PRT). Segundo Meng et al., (2000) este problema pode-se classificar em:
-
PRT discreto trata com o problema de achar locações ótimas das novas vias
(arcos) a serem adicionadas (nos modelos cada via é representada por variáveis
de decisão inteiras 0-1).
2
-
PRT contínuo determina a capacidade ótima a ser aumentada para um
subconjunto de vias (arcos) existentes (representadas por variáveis de decisão
reais positivas).
-
PRT misto combina ambos os problemas acima.
Outras classificações são possíveis, por exemplo, Chen e Alfa, (1991)
classificam o problema PRT da seguinte maneira:
a) PRT definido com funções objetivo lineares,
b) PRT definido com funções objetivo não lineares e as soluções satisfazem um critério
ótimo do sistema, e
c) PRT com funções objetivo não lineares e soluções que satisfazem um critério de
equilíbrio ótimo do usuário.
Além do problema PRT no transporte urbano de pessoas e bens, aparecem
outros problemas (atualmente motivo de inúmeras pesquisas) como o Controle do
Tráfego (CT), o Equilíbrio de fluxos de Tráfego (ET), e principalmente a Estimação da
matriz de viagem Origem/Destino (O/D). Destes problemas, um dos que tem chamado a
atenção dos pesquisadores desde a década dos 70, foi o problema de equilíbrio do
tráfego.
A idéia do equilíbrio de tráfego teve origem no ano 1924 quando Knight, deu
uma descrição simples e intuitiva de um postulado sobre escolha de rota pelos usuários
sob condições de congestionamento, ver Florian (1999), que “grosso modo” diz: Supor
que entre um par origem-destino existem duas rotas, uma das quais é de pobre
qualidade mas de ampla capacidade, entretanto a outra é de boa qualidade, embora de
capacidade muito estreita. Se um grande número de motoristas de caminhões opera
entre esse par O/D e tem liberdade para escolher uma das rotas, a tendência será uma
distribuição do número de motoristas de caminhões entre ambas rotas em tal proporção
que, o custo unitário de transporte será o mesmo para cada caminhão sobre ambas
rotas. Explicando, isto é assim porque no inicio, será preferida a rota de melhor
qualidade até que ela ficar saturada, então a rota de menor qualidade torna-se
igualmente procurada. Mais tarde em 1952, Wardrop formalizou a noção de equilíbrio
de tráfego e de minimização do tempo de viagem na seguinte proposição: No equilíbrio,
3
o custo médio de viagem das rotas que tem fluxo positivo são iguais, e igual ao custo
mínimo (este é conhecido como o primeiro principio de Wardrop).
O problema de ET consiste em encontrar os fluxos e tempos de viagem ou
custos generalizados de acordo com o primeiro principio de Wardrop. Os fluxos que
satisfazem este principio, chamam-se de fluxos ótimos do usuário.
Os primeiros modelos matemáticos para o problema de equilíbrio de tráfego foram
formulados pelo ano 1956 por Beckmann et al., como referido em Florian (1999).
Segundo Dafermos (1980), podem-se diferenciar duas abordagens para este
problema:
Modelo de equilíbrio de tráfego padrão (ou sem congestionamento), nele, a
função de custo de viagem em arcos, depende somente do fluxo no próprio arco, e a
demanda de viagem associada com um par origem/destino (O/D) pode ser constante ou
variável (caso seja variável chama-se de demanda elástica).
Modelo de equilíbrio de tráfego geral (ou com congestionamento), neste modelo
a função de custo de viagem em arcos depende, em geral, dos fluxos de outros arcos
da rede, e a demanda é considerada constante.
Em um problema PRT trata-se fundamentalmente de melhorar o desempenho de
um sistema de transporte. Considera-se que o administrador do sistema tem o interesse
de minimizar o custo de investimento na rede. Embora, o sistema não prescreva o
comportamento do usuário na escolha de rotas e modos de viagem, e com freqüência
essas escolhas entrem em conflito com o que seria ótimo para o administrador do
sistema. Assim, estes problemas podem ser modelados considerando uma classe de
problemas hierárquicos, compostos de dois níveis de decisão. São os modelos
conhecidos em otimização como Problemas de Programação de Dois Níveis, onde a
tomada de decisão do primeiro nível (nível superior, corresponde às decisões do
administrador) estará limitada pela tomada de decisão do segundo nível (nível inferior,
correspondente às decisões do usuário). Como veremos no seguinte capítulo, vários
modelos e conseqüentemente métodos de solução foram desenvolvidos para o
problema ET e PRT.
4
2 Objetivo da Tese
Neste trabalho, estuda-se um problema do transporte urbano conhecido como de
Projeto de Redes de Tráfego (PRT). Para este problema se faz uma formulação de um
modelo de Programação de Dois Níveis Generalizado, onde no primeiro nível uma
função T(f,s) representa o custo do sistema de transporte, que depende do fluxo f e da
capacidade s da rede. No segundo nível, é considerado um problema de equilíbrio de
tráfego, onde a função de custo de viagem é estritamente ou fortemente monótona.
Neste nível, o problema de ET é formulado como uma desigualdade variacional (DV).
Segundo a classificação de Meng et al., (2000), neste trabalho aborda-se o problema
PRT continuo ( i.e, as funções envolvidas são continuas em seus domínios de
definição), e o problema de equilíbrio de tráfego é o geral.
Para o cálculo de uma solução do PRT, foram propostos dois algoritmos. O
primeiro tem a estrutura do algoritmo chamado de Projeto-Alocação, Bell M.G. e Iida Y.
(1997), onde o problema de equilíbrio formulado como uma DV, é resolvido por uma
adaptação do algoritmo da minimização da função gap, Arica et al. (1996). O segundo
algoritmo de solução do PRT calcula aproximações ao valor ótimo da função objetivo do
PRT penalizando a função gap. Resultados numéricos de alguns testes computacionais
são reportados no último capítulo.
3 Importância do Trabalho
Como veremos no referencial histórico, existem diferentes formulações para o
problema PRT, e uma variedade de métodos para sua solução. Devido à característica
hierárquica do problema PRT, alguns pesquisadores consideram que uma formulação
de dois níveis para este problema é um modelo apropriado. Este tipo de modelo permite
ademais um avanço na procura da solução do PRT, a pesar que devido a sua grande
complexidade, constitue atualmente um desafio para os pesquisadores dedicados aos
problemas de transporte, Yang e Bell (2001).
Quando num problema PRT, a função de custo de viagem deve modelar fatos reais
como a interação de fluxos de arcos, a matriz Jacobiana desta função resulta não
5
simétrica. Neste caso, o problema de equilíbrio é modelado como uma DV, e não tem
uma formulação equivalente ao de minimização de uma função convexa. Nesse
contexto então, este trabalho é uma alternativa de solução de uma DV.
4 Estrutura da Tese
No capítulo 1, foi descrito o problema de transporte urbano abordado na tese, o
objetivo, sua importância e, a seguir finaliza-se com a descrição do corpo da tese.
No capítulo 2, apresentam-se comentários sobre enfoques, e abordagem
existente na literatura do problema de equilíbrio de tráfego, o problema de PRT, e suas
diferentes formulações e métodos de solução empregados.
No capítulo 3, apresentam-se as definições relacionadas, alguns resultados da
teoria de otimização não diferenciável e métodos de solução de um problema não
diferenciável necessários na verificação e justificativa do algoritmo proposto na tese
para resolver o problema PRT.
No capítulo 4, apresentam-se a formulação do PRT, sua abordagem como um problema
de programação de dois níveis generalizado, e metodologia de solução.
No capítulo 5, apresentam-se o algoritmo P-A e o algoritmo de Penalidades.
Exemplos de aplicação do algoritmo são testados. Dois exemplos são tomados da
literatura para testar o algoritmo na fase de equilíbrio, um terceiro exemplo é proposto
para o problema de equilíbrio numa rede onde a função de custo de viagem modela a
interseção de fluxos nos arcos. Para o problema de PRT são apresentados três
exemplos, um com uma função de custo de viagem de tipo BPR (uso da função gap
primal para resolver a DV), e os outros dois com uma função de custo de viagem
modelando a interação dos fluxos em vias da rede de mão dupla (uso da função gap
primal e a função gap dual para resolver a DV). Adicionalmente são relatados
resultados numéricos usando tabelas ilustrativas sobre os exemplos testados.
6
No Capítulo 6, apresentam-se as conclusões, recomendações e propostas de
pesquisas futuras.
7
CAPÍTULO 2
Referencial Histórico
A seguir apresentamos um histórico do problema de Projeto de Redes de
Tráfego (PRT) e métodos de solução relacionando-o com o problema de Equilíbrio de
Tráfego (ET). Existindo uma vasta literatura para estes problemas, aqui apenas
mencionaremos as que são de nosso interesse para o presente trabalho.
É conhecido que, sob a hipótese que o custo de viagem sobre uma via (arco de
uma rede) depende apenas do fluxo do próprio arco, a matriz Jacobiana da função de
custo de viagem, resulta simétrica e o problema do ET pode ser formulado como um
modelo de otimização convexa. Em geral, essa hipótese não é realista, então outras
formulações são necessárias. Na literatura, o problema do ET tem sido formulado como
um problema de programação não linear (PNL) por Beckman et al. (1956); como um
problema de Complementaridade Não Linear (CNL) por Aashtiani e Magnanti (1981);
como um problema de Ponto Fixo (PF), por Asmuth (1978); e, tanto Dafermos (1980),
Smith (1979), como Fisk e Boyce (1983) o formularam como uma Desigualdade
Variacional (DV).
A utilização da programação matemática para obter aproximações do equilíbrio de
tráfego (em particular urbano), originou-se pelo ano 1956, quando Beckman et al.
(1956) formularam um modelo para as condições de equilíbrio de tráfego, como sendo
as condições de otimalidade de um problema de otimização equivalente. Para este
modelo estabeleceram três hipóteses:
- Modo simples de viagem (isto é, supõe-se que o usuário viaja segundo um dos
modos, individual (carro, motocicleta, bicicleta, etc.), ou coletivo (ônibus, metrô, trem,
etc).
- Demanda entre cada par O/D dependendo do tempo mínimo de viagem.
- As funções de custo de viagem são separáveis, isto significa que o custo de viagem
em cada arco depende somente do fluxo total desse arco. Formulações posteriores
seguiram essas hipóteses, e métodos de solução para problemas de programação
8
matemática convexa foram aplicados com sucesso, por exemplo ver Aashtiani e
Magnanti, (1981).
A realidade mostrou que era necessário estender este modelo, para incluir
situações de tráfego como congestionamento e outros incidentes que acontecem nas
vias urbanas.
Foi assim que, em 1979 Smith formula um modelo para o problema de equilíbrio
como uma desigualdade variacional. Neste modelo se considera a interação entre os
fluxos dos diferentes arcos da rede, resultando a matriz Jacobiana da função de custo
de viagem não simétrica.
Resolver um problema de ET formulado por uma DV (no caso não simétrico), em
geral é muito complicado, motivo pelo qual o desenvolvimento de algoritmos eficientes
para a solução é ainda hoje, matéria de pesquisa para os pesquisadores em problemas
de transporte urbano.
Montero (1995) relata que os primeiros algoritmos aplicados à solução do
problema ET, no caso geral, na formulação de DV finito dimensional foram baseados
num modelo equivalente a problemas de ponto fixo (PF). Afirma também: (a) que estes
algoritmos são de difícil adaptação para um problema ET, devido principalmente ao
requerimento de uma grande capacidade de memória para execução do algoritmo, e (b)
que os diferentes métodos empregados para resolver um problema de ET geral,
formulado como uma DV, podem ser agrupados nas seguintes classes metodológicas:
1 Métodos de aproximação linear.
O esquema geral destes métodos algorítmicos pode-se expressar na seguinte forma:
Sejam x k∈K, K⊂R
n
sub-conjunto convexo e compacto, e f
k
: R
aplicação de aproximação para f no ponto xk . O seguinte ponto
n
→ R
n
uma
iterado x k+1 é
solução da desigualdade variacional
f k(x)(y – x) ≥0 ,
∀y∈K , isto é x k+1 satisfaz f k(x k+1)(y – x k+1) ≥0 ,
O método acima é chamado de aproximação linear se f
k
∀y∈K,
é expressado na forma
f k(x) = f(x k) + A k(x - x k), onde A k é uma matriz constante nxn na iteração k.
9
O método é chamado não linear se f k é não linear, por exemplo o f k(x) quadrático,
onde f k(x) = f(x k) + A k(x - x k) + (1/2)(x - x k)T H k(x - x k), onde A k e Hk são definidas a
partir da função f e são constantes na iteração k.
Entre estes métodos podem ser citados os seguintes:
Método de Newton, caso em que a função f é diferenciável, define-se A
k
como a
k
primeira derivada de f no ponto x .
Método quase-Newton, no qual Ak é uma aproximação da primeira derivada da função
f(x k).
Métodos de sobre-relaxação sucessiva, onde Ak pode-se assumir como Lk+(Dk/ w*),
ou Uk+(Dk/w*), com w*∈〈0,2〉, e Dk, Lk, U
k
são respectivamente a matriz diagonal,
triangular inferior e triangular superior da primeira derivada de f
k
em caso f possua
derivada.
Método de Jacobi linearizado, no qual Ak= Dk.
Métodos de projeção, nos quais se faz Ak=G para todas as iterações, onde para cada
k, a matriz G é alguma matriz simétrica fixa (Dafermos, 1980).
A denominação de projeção desta última família de métodos, é devida a uma simples
interpretação geométrica que se explica a seguir. Seja K um conjunto convexo e
fechado, e a matriz Ak = G simétrica definida positiva. Dado o
k+1
que resolve a DV é justamente a projeção do ponto (x
ponto x k , o vetor x
k
- G-1 f(x k)) sobre o
conjunto K, i. é
x k+1 = Proj K (x k - G-1 f(x k)).
Para um vetor z, y* = Proj K (z) é o único vetor em K que resolve o programa,
min z-y G = z-y* G
y∈ K
onde x G é a norma com relação a G, i. e, . G = (x T G x) ½.
Portanto, no presente caso o seguinte ponto iterado será
10
x k+1 := min (1/2) x k - G-1f(x k) - y 2G
y∈ K
2 Métodos de diagonalização
O que caracteriza esta família de métodos é o fato que, entre cada iteração
blocos de variáveis são retiradas, pois quando se aplica métodos de diagonalização a
desigualdades variacionais, estes tornam-se extensões dos métodos de Jacobi e
Gauss-Seidel para equações lineares e não lineares. Neste caso (diagonalização para
uma DV), o método corresponde à classificação (d) anterior já que em cada iteração a
função vetorial do custo de viagem é diagonalizada para produzir um problema
simétrico.
3 Métodos de decomposição simplicial
O fundamento destes métodos se baseia em assumir o conjunto K como um poliedro,
portanto, K pode ser representado por uma combinação convexa de seus pontos
extremos e direções extremas. Segundo o principio de decomposição de Dantzig-Wolfe
(1961), estes pontos extremos não são conhecidos previamente, embora sejam
identificados como as soluções básicas viáveis de um problema de programação linear
definido sobre o conjunto viável original K. Logo, cada ponto extremo achado é
associado a uma variável do problema mestre, e este é resolvido sobre a envoltória
convexa destes pontos extremos.
A seguir apresentam-se alguns detalhes de pesquisas sobre o problema de Equilíbrio
de Tráfego relacionando-o com a classificação anterior.
Um problema de programação de dois níveis, onde o segundo nível está formulado por
uma DV, vai ser chamado, como na literatura de programação matemática, de
Problema de Programação de Dois Níveis Generalizado (PDNG).
Num problema de PRT, formulado como de programação de dois níveis generalizado,
a solução da DV é a parte do problema de maior dificuldade. Outro método de solução
para a DV que utiliza uma função associada a ela, aparece pela primeira vez no
11
trabalho de Zuhovickii et al. (1969), onde se define uma função chamada função gap
associada à DV. Segundo Lo e Chen, (2000), a aplicação da função gap para resolver
um problema de equilíbrio na sua formulação de DV, foi feita primeiro no ano 1983 por
Smith. A função gap em geral é uma função não diferenciável (pois está definida como
o valor de uma minimização ou maximização) e/ou não convexa. Em Lo e Chen, (2000)
um
modelo de
equilíbrio
de
tráfego
é formulado como um
problema
de
complementaridade não linear (CNL), para o qual é definida uma função gap
diferenciável, associada ao problema a qual será apresentada mais na frente.
Os trabalhos a seguir apresentaram resultados sobre o problema de Equilíbrio de
Tráfego,
considerando
formulações
de
minimização
convexa
ou
como
uma
desigualdade variacional:
Dafermos, (1980): O trabalho considera um modelo geral do problema de equilíbrio
numa rede, onde o custo de viagem de cada arco depende do fluxo na rede, i. e., esta se considerando a interação entre os fluxos dos diferentes arcos. Usando uma
formulação do problema de equilíbrio como uma DV e a teoria relacionada estabelece
existência do fluxo de equilíbrio. Supõe-se que a função de custo de viagem tem a
forma especial C(f)= Gf+h, onde G é uma matriz semidefinida positiva. Em geral a
matriz G pode ser escolhida como a parte simétrica da matriz Jacobiana [ ∂ C(f)/∂f].
Com relação à classificação de Montero acima, não pode-se dizer que corresponda a
uma delas em especial.
Em Aashtiani e Magnanti, (1981): Os autores, usando o teorema de ponto fixo de
Brouwer estabelecem a existência da solução do problema de ET. Sob condições de
monotonia nas funções de custo e demanda, provam a unicidade dos fluxos e dos
tempos de viagem em arcos.
Florian M. e Spiess H., (1982): Este artigo apresenta condições suficientes para a
convergência dos algoritmos de diagonalização, para resolver o problema de alocação
do tráfego de equilíbrio.
12
Considerou uma função de custo de viagem em arcos não linear, que tem Jacobiana
não simétrica. Demonstrou um teorema de convergência local, para funções que só
dependem dos fluxos.
Nguyen e Dupuis, (1984): Este trabalho tratou um modelo para o problema ET
considerando diferentes modos de transporte e interação de fluxos de diferentes arcos.
Embora, para a análise restringiram-se ao caso do problema de um modo de transporte
só. A demanda considerada foi fixa e o conjunto de fluxos viáveis utilizado foi um
poliedro compacto e convexo. A formulação do problema de ET foi feita por uma DV,
sendo a função (custo de Viagem) que define a DV, uma função continua e estritamente
monótona.
Para resolver o problema utilizaram uma função do tipo conhecida como função
gap associada à DV, a que neste caso é definida como uma minimização da forma
g(u)= min{ C ( x), x − u } ,
x∈Ω
resultando a função
g
côncava e não positiva. Então, o
problema se transforma em achar o zero desta função. O processo de solução consiste
em resolver uma seqüência de problemas de aproximação, cada um dos quais tem um
número finito de restrições. Os autores afirmam que para a convergência do algoritmo
somente é requerida a monotonia estrita e a continuidade da função de custo, embora
seja uma convergência fraca em relação à convergência de outros métodos.
Smith, (1992): Este trabalho apresenta um modelo dinâmico para a determinação dos
fluxos de equilíbrio num período pico em uma rede urbana congestionada, e inclui
restrições de capacidade. O modelo respeita a disciplina FIFO (o primeiro que entra é o
primeiro que sai) de filas de tráfego nas vias, e a capacidade de saída nos arcos.
Métodos para a determinação dos fluxos dinâmicos são fornecidos, os que envolvem
equações diferenciais parciais para a formulação do chamado modelo simples contínuo.
Joaquin e Fernandez, (1993): Os autores fazem uma formulação do problema de
alocação de tráfego usando o conceito de rota de trânsito. Consideram o fenômeno de
congestionamento como concentrado nos pontos de parada, pelo que os tempos de
13
viagem dependem também dos tempos de espera. A formulação foi feita como uma
desigualdade variacional e para sua solução usaram o método de diagonalização.
Philippe, (1993): Este artigo apresenta um modelo de equilíbrio de tráfego com alto grau
de congestionamento. Considera várias vias de ingresso a uma rede e uma saída só.
Levando em consideração que os usuários atuam de modo racional na presencia de
pedágios, formula o problema como de minimização convexa.
Codina (1994): Neste trabalho considera-se um modelo para alocação de tráfego
dinâmico numa rede com vários destinos. O fluxo dinâmico do modelo foi considerado
uma extensão do modelo contínuo para fluxos compostos por diferentes classes de
bens, tendo iguais características de propagação. Sob a hipótese que a velocidade de
propagação dos fluxos é constante, o modelo foi aproximado por outro de controle
ótimo.
Hong et al., (2000): No trabalho, se faz uso de uma função gap diferenciável, proposta
por (Facchine e Soares, 1995) para transformar a formulação de complementaridade
não linear do problema de equilíbrio, a um problema equivalente de programação
matemática sem restrições. Nesta formulação, as variáveis de decisão são os fluxos em
rota e os custos de viagem O/D. Por ser de interesse a função gap associada à CNL
proposta neste trabalho, é apresentada a seguir:
Seja
ψ:R
2
→ R , definida por ψ(a,b)=
a 2 + b 2 − (a + b) , que tem a propriedade
ψ(a,b) = 0 ⇔ a ≥ 0 , b ≥ 0, a b=0; e define-se ϕ (a,b)=(1/2) ψ 2(a,b).
Então, a função gap associada ao problema de CNL é definida por
G : R n → R n, G(x) =
n
∑ ϕ ( x , F ( x)) ,
i =1
i
i
onde F : R n → R n , F(x)=(F i (x)) ni=1 .
A seguir apresenta-se um resumo dos trabalhos pesquisados que estão relacionados
ao problema de projeto de redes de tráfego (PRT) e a dois níveis:
14
Marcotte, (1984): O autor formula o problema PRT como sendo um problema de
programação de dois níveis generalizado. Sob hipóteses de diferenciabilidade,
separabilidade e convexidade sobre a função objetivo do primeiro nível, e considerando
uma função de tipo BPR para representar o custo de viagem do problema de ET,
transforma o problema para uma minimização convexa de dois níveis. Calcula soluções
usando métodos de natureza heurística, sendo que nosso trabalho considera o
algoritmo de Projeto-Alocação que é de natureza exata.
Fisk, (1987): O trabalho mostra a forma como uma formulação de dois níveis para a
estimação da matriz de viagem, pelo método de máxima entropia, proposto por
Willumsen, o qual considera no segundo nível um modelo de alocação de tráfego, como
por exemplo SATURN (Simulated and Assignment of Traffic on Road Network Urban),
ver Van Vliet (1982), permite transformar o problema para outro de um nível só. O
problema ET neste trabalho é formulado como uma DV. Isto caracteriza o modelo como
de programação de dois níveis generalizado. O autor faz uma analise dos
procedimentos de solução. Neste trabalho não se considera o problema de melhorar o
desempenho da rede através do incremento das capacidades dos arcos da rede. Isto
marca a diferença com a nossa proposta na tese.
Nguyen, (1987): O Trabalho desenvolve um esquema teórico-gráfico para redes de
tráfego de grande porte, e provê uma metodologia para resolver o problema ET. São
apresentados formulações equivalentes de DV para o problema ET. São discutidos
algoritmos (como o que denomina algoritmo de direções viáveis, e outro de algoritmo do
hiper-caminho mínimo) para o cálculo dos fluxos de equilíbrio. Não são fornecidos
resultados computacionais.
Ben-Ayed, et al., (1998): Os autores apresentam uma formulação de dois níveis para o
problema PRT. Fazem uma análise para o problema considerando os casos côncavo e
convexo da função do líder, e linear a função do seguidor. As restrições no nível inferior
são lineares. Para calcular a solução empregam um método de linearização por partes
da função objetiva do líder, a qual é aproximada por pequenos segmentos que unem
pontos em acordo com a partição do domínio. Não reportam resultados computacionais.
15
Michael et al. , (1999): Este trabalho apresenta um algorítmico para a estimação da
matriz de viagem origem/destino, e o controle de sinais de tráfego em redes viarias
congestionadas. Ambos dos problemas são formulados como programas de dois níveis,
sendo o segundo nível um problema de equilíbrio estocástico do usuário. Nos dois
níveis os problemas são de minimização convexa, e as funções de custo de viagem de
tipo BPR (Bureau of Public Roads). Exemplos teste são apresentados.
Suh, (1999): O autor faz uma formulação de dois níveis para o controle de sinais de
tráfego e para a obtenção dos fluxos de equilíbrio. O problema de equilíbrio é formulado
como uma DV. A função de mérito no nível superior é não convexa, embora
diferenciável, pelo que só pode-se atingir soluções locais. Usa o método de projeção do
gradiente para determinar a direção de descida, logo os passos de avanço ótimos são
dados nessa direção mantendo viavilidade, o que permite obter pontos que satisfazem
as condições de Karush-Kuhn-Tucker os que são identificados como ótimos locais.
Ressaltamos que nossa proposta de dois níveis neste trabalho considera no nível
superior, o problema de minimizar uma função de custo de viagem e investimentos,
podendo ser esta função não convexa e não diferenciável, neste último caso, deve-se
aplicar a teoria desenvolvida no capítulo 3 sobre problemas de otimização não
diferenciável.
Meng et al. , (2000): Os autores caracterizam o problema PRT por um modelo de
programação de dois níveis. O nível superior representa o problema de minimizar o
custo total do sistema, e o nível inferior é um problema de otimização convexa que
consiste em determinar o vetor de fluxo de equilíbrio do usuário (deterministico ou
estocástico). A formulação de dois níveis do PRT é transformado para um problema de
um nível só, através do uso de uma função marginal do segundo nível, isto é, para o
problema de equilíbrio do usuário. Prova-se que esta função marginal é continuamente
diferenciável, pelo que a formulação resulta num problema de otimização não convexa,
embora diferenciável. O problema é resolvido aplicando um método de Lagrangiano
aumentado para o nível superior, localmente convergente. A direção de descida é
achada em cada iteração pelo método pratico conhecido como de alocação tudo ou
16
nada. Reportam-se resultados numéricos que são comparados com exemplos já
existentes na literatura. Com relação a nosso trabalho, formula-se o problema de
equilíbrio como uma DV o que permite considerar a interação de fluxos dos arcos, o
que não é possível numa formulação de otimização convexa.
17
CAPÍTULO 3
Alguns resultados da Teoria diferenciável e não diferenciável
Neste capítulo são apresentamos algumas definições e resultados necessários da
analise diferenciável e não diferenciável, e a relação entre eles. São descritos
brevemente alguns métodos de otimização não diferenciável (o método sub-gradiente e
o método de linearização). Basicamente, como nos métodos de PNL, apresenta-se a
forma como estes métodos geram direções de descida. Na seção 3, se introduze o
conceito de função valor que é utilizado para transformar um problema de programação
matemática de dois níveis em um problema de programação matemática de um nível
só, que resulta um problema não diferenciável.
A teoria clássica de otimização teve seus melhores resultados assumindo condições de
diferenciabilidade para todas as funções envolvidas. Apesar de que a hipótese de
diferenciabilidade não se apresente completamente apropriada para aplicações
práticas, devido a que funções que modelam fenômenos da vida real, são, em geral,
não continuas e/ou não diferenciáveis nas suas definições. Por exemplo, na definição
de preços de um produto, estão condicionados ao volume de venda, o mesmo acontece
com as taxas de impostos, etc. A busca de modelos apropriados para representar estas
situações reais, levou ao desenvolvimento da análise não diferenciável, a partir dos
anos 70.
Em problemas de otimização, conseguiram-se resultados importantes quando para as
funções envolvidas se consideraram propriedades de convexidade. Por esta razão, a
teoria não diferenciável foi desenvolvida primeiro para funções convexas.
Uma interpretação geométrica da derivada de uma função qualquer em um ponto, é a
possibilidade de alcançar uma linearização local (Ver Figura 1), no sentido que o
hiperplano gerado pela derivada da função no ponto, o gradiente é tangente ao gráfico
18
da função nesse ponto, é uma boa aproximação à função numa vizinhança do ponto de
tangência. Esta idéia foi generalizada para funções convexas não diferenciáveis
definindo o conceito de sub-gradiente e sub-diferencial.
Geometricamente, um sub-gradiente num ponto do gráfico de uma função, é um vetor
tal que o hiperplano nesse ponto, gerado por esse vetor é uma aproximação à função,
isto é, aproxima-se a f nesse ponto (embora essa aproximação possa ser melhorada
com o cone tangente como veremos depois).
(∇f(x),1)
T
(∇f(x),-1)
x0
x1
x2
x3 -ε
x3 x3 + ε
Fig. 1 O hiperplano T no ponto (x3 ,f(x3)) é uma aproximação inferior à parte convexa da
função f na vizinhança (x3 -∈ , x3 +∈ ). A função f é não convexa para x∈[x0,x2].
Para lidar com funções convexas não diferenciáveis, são necessários alguns conceitos
prévios que relacionamos em continuação.
3.1 Conceitos Básicos
Definição 3.1 Seja C um sub-conjunto não vazio de R n .
1. C é um conjunto convexo se para quaisquer pontos x e y em C,
19
(1-λ)x+λy ∈C , para todo λ∈[0,1].
2. C é um cone se λc∈C para qualquer c∈C e qualquer λ ≥ 0 ,
(1-λ)x+λy ∈C , para todo λ∈[0,1].
Definição 3.2 Uma função f : R n → R se diz convexa, se dados x,y em Rn , cumprese:
f(λx +(1-λ)y) ≤ λf(x)+(1-λ)f(y), para todo λ∈[0,1].
Se a desigualdade estrita se cumpre para x≠y e para todo λ∈(0,1), então f se diz
estritamente convexa.
Uma classe de funções que aparecem em muitas aplicações, caracterizadas por ter
uma taxa de variação limitada em vizinhanças de um ponto, denomina-se de funções
Lipschitz em torno de um ponto.
Definição 3.3 Uma função f : R n → R se diz Lipschitz em torno do ponto x∈Rn, com
constante K, se existe ε > 0 tal que
f(y)-f(z) ≤ K y-z , ∀ y,z∈B(x;ε),
onde B(x;ε) = { y∈R n/  y-x <ε } representa uma vizinhança do ponto x.
O teorema seguinte mostra a relação entre uma função convexa sobre R
n
e sua
variação limitada em cada ponto.
Teorema 3.4 Seja f: R
n
→ R uma função convexa. Então para qualquer x∈Rn, f é
Lipschitz em torno do de x.
Prova: Ver Teorema 2.1.2, Makela, (1992).
A seguir se define a extensão de derivada de uma função convexa não diferenciável.
Definição 3.5 Seja f: R n → R uma função convexa. O sub-diferencial de f num ponto
x∈Rn é o conjunto
20
∂C f(x)={ξ∈Rn / f(y) ≥ f(x) + 〈ξ,y-x〉 , ∀y∈R n}.
Cada ξ∈∂C f(x) é chamado um sub-gradiente de f em x, e a notação ∂C f(x) refere-se ao
conjunto sub-diferencial de uma função convexa.
Em continuação se apresenta a derivada e o relacionamento com o sub-gradiente de
uma função convexa.
Definição 3.6 Seja f: R
n
→ R. A derivada direcional de f em x , na direção do vetor
v∈ R n, é definida como
f '( x; v) = lim
h↓0
f ( x + h v) − f ( x)
,
h
se este limite existe.
Observação 3.7 Um resultado do cálculo diferencial de varias variáveis refere que:
quando f é diferenciável em x, a derivada direcional pode-se expressar como
f ’(x;v) = ∇ f(x)T v ,
onde ∇ f(x)∈R n representa o gradiente da função f em x.
Teorema 3.8 Seja f: Rn → R convexa. Então, para cada x∈R cumpre-se
i) f ’(x;v)=max {〈ξ,v〉 / ξ∈∂C f(x)}, ∀ v∈R n
ii) ∂C f(x)={ ξ∈Rn / f ’(x;v) ≥ 〈ξ,v〉 , ∀ v∈R n},
iii) ∂C f(x) é um conjunto não vazio, compacto e convexo tal que ∂C f(x)⊂ B(0;K) , onde K
é a constante de Lipschitz de f em x.
Prova: Teorema 2.1.5, Makela e Neittaanmaki (1992).
21
Observação 3.9 Quando f é convexa e diferenciável tem-se ∂C f(x)={ ∇ f(x)} e
f(y) ≥ f(x) + ∇ f(x)T(y-x) , ∀ y∈Rn
A seguinte propriedade mostra como se calcula o valor de uma função convexa em um
ponto usando a família de aproximações lineares ao redor de um ponto não
diferenciável x.
Teorema 3.10 Seja f: R n → R convexa. Então para toda y∈R n,
f(y) = max {f(x) + 〈ξ x ,y-x〉 / x∈R n , ξ x∈∂C f(x)}
A prova a seguir é alternativa à do Teorema 2.1.7, em Makela e Neittanmaki (1992).
Prova:
Sejam y, x∈R n e ξ x∈ ∂C f(x), quaisquer. Então
f(y) ≥ f(x) + 〈ξ x , y - x 〉 ,
⇒
∀ y∈R n
f ( y ) ≥ max { f ( x) + ξ x , y − x }, x ∈ R n qualquer fixo,
ξ x ∈∂C f ( x )
então,
f ( y ) ≥ max { f ( x) + ξ x , y − x , x ∈ R n }
ξ x ∈∂ C f ( x )
(a)
Quando em particular x=y , se tem:
max { f ( x) + ξ x , y − x , x ∈ R n } ≥ f ( y )
ξ x ∈∂C f ( x )
De (a) e (b)
f(y) = max {f(x) + 〈ξ x ,y-x〉 / x∈R n , ξ x∈∂C f(x)}.
(b)
22
Definição 3.11 O cone normal do conjunto convexo C, no ponto x ∈ C , onde C denota
o fecho de C, é definido como
NC (x):={z∈R n/〈 z , x –y 〉 ≥ 0 , ∀ y∈C}.
Observação 3.12 Existe o cone normal ainda para pontos que não pertencem ao
conjunto convexo C, i.e., quando x ∈ C, NC (x) =φ.
Definição 3.13 O cone tangente ao conjunto convexo C, no ponto ponto
x ∈C
é
definido como
TC (x):={v∈R n/〈 v , z〉 ≤ 0 , ∀ z∈ NC (x)}.
TC (x) e NC (x) são cones convexos.
Os elementos de NC (x)
e
TC (x) são chamados vetores normais e tangentes
respectivamente.
C
TC(x)
X
NC(x)
Fig. 2 Cones tangente e normal ao conjunto C convexo e fechado no ponto x
23
Definição 3.14 O cone tangente (de Clarke) a um conjunto φ ≠G ⊂R
n
qualquer, no
ponto x ∈ G é o conjunto seguinte (ver Figura 3):
TG(x):={v∈R n / se t i ↓ 0 e x i → x , x i∈G ⇒ ∃ v i → v , com (x i +t iv i )∈G, ∀ i }.
O cone normal a G no ponto x é o conjunto
NG(x):={w∈R n / 〈 w , v〉 ≤ 0, ∀ v∈ TG(x)}.
TG(x)
x
NG(x)
Fig. 3 Cones tangente e normal ao conjunto G aberto e não convexo no ponto x ∈ G
O fato de que para funções Lipschitz não convexas, não necessariamente existam as
derivadas direcionais ordinárias, leva-nos a considerar algumas generalizações dos
conceitos de derivada direcional e do sub-diferencial de funções convexas. Neste caso
o sub-diferencial de f no ponto x, será denotado simplesmente por ∂ f(x).
Definição 3.15 (Clarke, 1983). Seja f : R
n
→ R uma função Lipschitz ao redor do
ponto x∈R n. A derivada direcional generalizada de f em x, na direção de v∈Rn é
definida por
24
f 0 ( x; v) = lim sup
y → x; t ↓ 0
f ( y + tv) − f ( y )
,
t
onde lim sup g ( y ) = inf[sup{g ( y ) / y ∈ B ( x; ε )}].
y→x
ε >0
Observação 3.16 Da definição no caso f diferenciável, tem-se
f 0 (x,v) ≥ f ’ (x,v)
Teorema 3.17 Seja f : R
n
→ R uma função Lipschitz ao redor do ponto x, com
constante de Lipschitz K. Então,
i)
A função v → f 0(x;v) é positivamente homogênea, sub-aditiva sobre R n e
f 0(x ;v)≤ Kv
ii)
f 0(x ;-v) = (-f )0(x ;v)
Prova: Ver Proposição 2.1.1, em Clarke (1993) e Makela (1992).
Definição 3.18 Seja f : R n → R Lipschitz ao redor do ponto x∈R n. O Sub-diferencial
de f no ponto x é o conjunto
∂ f(x):={ξ∈R n/ f o(x;v) ≥ 〈ξ , v〉 , ∀ v∈ R n}.
Cada elemento ξ∈∂ f(x) é chamado um sub-gradiente de f em x, ou um gradiente
generalizado, pelo que o conjunto ∂ f(x) será também chamado de conjunto gradiente
generalizado.
O operador ∂ f(.) pode-se considerar uma aplicação ponto - conjunto,
n
∂f (.) : R n → 2 R , que associa a cada x ∈ R n um subconjunto de R n .
25
Proposição 3.19 Seja f Lipschitz ao redor do ponto x, com constante de Lipschitz K.
Então,
1) ∂ f(x) é um conjunto não vazio, convexo, compacto tal que ∂ f(x)⊂ B(0;K)
2) f o(x;v) = max {〈ξ , v〉 /ξ∈ ∂ f(x)} , ∀ v∈ R n.
Prova: Ver Proposição 2.1.2, em Clarke, (1993).
Observação 3.20 Quando f é Lipschitz ao redor do ponto x e diferenciável em x, então
∇ f(x) ∈∂ f(x).
Com efeito, se ∇ f(x)∉ ∂ f(x) ⇒∃ vo∈R n / f o(x;vo)< 〈∇ f(x);vo〉 ⇒
f o(x;v) < f ‘(x;vo). O que contradiz f o(x;v) ≥ f ’ (x;v), ∀ v∈R n.
Teorema 3.21 Se f é continuamente diferenciável em x, então f é localmente Lipschitz
em x e ∂ f(x)={∇ f(x)}
Prova: Ver Teorema 3.1.7, em Makela, (1992).
O seguinte teorema mostra que o sub-diferencial de funções somente Lipschitz ao redor
de um ponto é uma generalização do sub-diferencial das funções Lipschitz convexas
num ponto.
Proposição 3.22 Se a função f :R n → R é convexa e localmente Lipschitz no ponto x.
Então,
a) f o(x;v) = f ‘ (x;v) , ∀ v∈R n , e
b) ∂ f(x) = ∂C f(x)
Prova: Ver Proposição 2.2.7, em Clarke, (1983).
Definição 3.23 O epigrafo de uma função f :R n → R é o seguinte subconjunto de
Rnx R :
epi f :={(x,r) ∈ R n x R / r ≥ f(x) }.
26
Proposição 3.24 O epigrafo de uma função convexa f :R n → R é um conjunto fechado
de R n x R. O epigrafo da função v → f ’(x;v) é um cone fechado.
Prova: Ver Teorema 2.3.7, em Makela, (1992).
epi f
f
Tepi f
Hiperplanos de suporte do epi f, no
(x,f(x))
ponto (x,f(x)) são da forma
f(x) + 〈ξ, y – x)〉, ξ∈∂ f(x)
(ξ,-1)∈N epi f
Fig. 4 O epigrafo de f e o cone normal a epi f . Note que Tepi f (x,f(x)) pode ser
considerado uma aproximação poliedral a epi f no ponto (x,f(x)).
Proposição 3.25 Se a função f :R n → R é convexa, então
∂C f(x) = {ξ∈R n / (ξ ,-1)∈N epi f (x,f(x))}
Prova: Teorema 2.3.9, Makela e Neittaanmaki (1992).
3.2 Condições de otimalidade
Nesta seção apresentam-se condições necessárias para o mínimo local, de um
problema de otimização sem restrições. Considera-se que a função a minimizar é
27
Lipschitz ao redor dos pontos de interesse. Para o caso de funções convexas estas
condições também são suficientes e o mínimo resulta ser um mínimo global.
Teorema 3.26 Seja f :R n → R Lipschitz ao redor do ponto x. Se x é um mínimo local
de f , então
0 ∈∂ f(x) , e
f o(x;v) ≥ 0, ∀ v∈R n
Prova: Ver Teorema 2.3.2, em Clarke, (1983).
Proposição 3.27 Se f :R n → R é uma função convexa, então as seguintes condições
são equivalentes:
1) A função f atinge sue mínimo global no ponto x,
2) 0 ∈∂C f(x),
f ‘(x ;v)≥ 0 , ∀ v∈R n
Prova: Ver Teorema 5.1.2, em Makela, (1992).
Para um problema de otimização com restrições, tem-se:
Proposição 3.28 Se f :R n → R é Lipschitz ao redor do ponto x e atinge seu mínimo
local sobre o conjunto G ⊂ R n no ponto x, então 0 ∈∂ f(x) + NG(x).
Prova: Ver Teorema 5.1.6, em Makela, (1992).
Proposição 3.29 Se f :R n → R é convexa e G ⊂ Rn um conjunto convexo, então as
seguintes condições são equivalentes:
1) 0 ∈∂C f(x) + NG(x)
2) f atinge seu mínimo global sobre G no ponto x.
Prova: Ver Teorema 5.1.7, Makela (1992).
28
3.3 Linearização de Problemas sem restrições
Nesta seção se definem algumas noções de linearização de funções Lipschitz. Estas
linearizações permitem uma aproximação local linear por partes à função. Esta
aproximação será usada em métodos de otimização para gerar principalmente uma
direção de descida para um ubproblema geral:
(P):
min f(x) , x∈R n
Definição 3.30 Seja f :R n → R uma função Lipschitz ao redor de cada ponto x∈Rn, e
ξ∈∂f(x) um sub-gradiente arbitrário de f no ponto x. A ξ-linearização de f no ponto x é a
função f –ξ (.) :R n → R definida por
f –ξ (y) :=f(x) + 〈ξ , y - x〉 , ∀ y∈R n,
e a linearização de f em x é a função f =(x;.) :R n → R definida com
f =(x ;y) = max { f –ξ (y) / ξ∈∂ f(x)}, ∀ y∈R n.
f –ξ1 (y;x1)
f –ξ3 (y;x3)
f
(ξ1,-1)
f – ξ2 (y;x2)
x1
x2
x3
Fig. 5 Uma função f e uma ξ-linearização em cada um dos pontos x1, x2 , x3
29
epi f
f
f =(y; x1)
x1
x2
Fig. 6 A linearização de f em relação ao ponto x1 .
epi f
f
f =(y; x2)
x2
Fig. 7 A linearização de f em relação ao ponto x2 .
30
f =(y;x)
epi f
x
Fig. 8 A linearização de f em relação ao ponto x.
Teorema 3.31 Seja f : R
n
→ R Lipschitz ao redor do ponto x. Então, a função de
linearização f =(.; x) de f é convexa e
1) f =(x ; x) =f(x) ;
2) f =( y;x) =f(x) + f o(x;y – x) , ∀ y∈R n ;
3) ∂C f =(x ; x) = ∂ f(x).
Prova: Ver Teorema 5.2.2, em Makela, (1992).
Teorema 3.32 Seja f : R n → R uma função convexa. Então,
1) f(y) = max { f =(y ; x) / x∈R n } , para cada ponto y∈R n;
2) f =( y; x) ≤ f(y) , ∀ y∈R n ;
3) epi f (.) ⊂ epi f =(. ; x).
Prova: Ver Teorema 5.2.3 em Makela, (1992).
Teorema 3.33 Seja f : R n → R Lipschitz ao redor do ponto x. A direção d∈R n é uma
direção de descida para f em x, se qualquer uma das seguintes proposições se
verifica,
1) f o(x ; d) < 0 ;
2) 〈ξ , d〉 < 0 , ∀ξ∈ ∂ f(x) ;
31
3) d é uma direção de descida para f =(. ; x) no ponto x.
Prova: Ver Teorema 5.2.5, em Makela, (1992).
3.4 Métodos para problemas de Otimização não diferenciável
Nesta seção são apresentados dois métodos para calcular a solução de um problema
de otimização não diferenciável. Segundo Makela e Neittaanmaki (1992), os métodos
para otimização não diferenciável podem ser divididos em duas classes principais: os
métodos de sub-gradientes e os métodos de feixes. Para estes métodos, supõe -se que
as funções do problema são continuas e Lipschitz ao redor dos pontos considerados, e
que pode-se avaliar cada função e conhecer um sub-gradiente arbitrário em cada ponto
considerado. É claro que as funções não precisam ser diferenciáveis ou convexas.
Primeiro se apresenta uma breve descrição de um método sub-gradiente e de um
método de feixes, enfatizando principalmente a forma como são geradas as direções de
descida.
3.4.1 Métodos de Sub-gradientes
A idéia fundamental do método de sub-gradientes é generalizar o método para
problemas diferenciáveis, substituindo, até onde for possível, o gradiente pelo subgradiente.
Seja o seguinte problema não diferenciável:
(P):
minimizar f(x)
(3.1)
s. a . x∈R n
A generalização do método do gradiente conduziria a substituir o gradiente pelo subgradiente. Assim, se ξ k∈∂ f(x k) é um sub-gradiente, então uma direção de descida
determinada pelo sub-gradiente seria
32
dk = −
ξk
.
ξk
(3.2)
Sabe-se que no caso diferenciável, a direção oposta do gradiente é uma direção de
descida. Seguidamente os tamanhos do passo de avanço são encontrados
minimizando a função objetivo nessa direção, entanto a norma do sub-gradiente vai
para zero. Infelizmente, no caso não diferenciável, isto não necessariamente é assim.
Por exemplo, a função valor absoluto sobre os reais. Esta função atinge seu mínimo
global em zero, que é um ponto de não diferenciabilidade, e tanto no ponto zero como
numa vizinhança do zero um sub-gradiente é 1 ou –1, ambos diferentes de 0. Uma
outra dificuldade, é que não é aplicável o critério de parada padrão, pois um subgradiente arbitrário não fornece informação para usar o critério de ótimo ∇ f(x)=0. Por
outro lado, nem sempre d k=-ξ
k
, com ξ k∈∂ f(xk) é uma direção de descida para f a
partir de x k. Por exemplo, consideremos a função f(x1,x2) = 3x1-2)+x2 - 3, cujas
curvas de nível são mostradas na Figura 9. Observamos que a direção oposta do subgradiente ξ=(1,1)∈∂ f (2,6),não é uma direção de descida.
X2
ξ =(1,1)
6
-ξ
ponto mínimo
x*
3
x1
2
Fig. 9 Curvas de nível de f, a direção - ξ não é de descida.
Estes fatos, levam a fazer uma escolha prévia do tamanho do passo t k , para evitar a
busca linear e facilitar o critério de parada. Assim, dado um ponto inicial x 0, fazemos
33
k=1, e escolhemos o tamanho de passo t k > 0 apropriado, então definimos o próximo
ponto como,
xk +1 := xk − tk
ξk
,
ξk
onde ξ k ∈ ∂f ( xk ).
(3.3)
A seguinte proposição da uma justificação teórica para uma escolha possível do
tamanho do passo.
Proposição 3.34 Seja x* uma solução do problema P, (3.1). Supor que x
solução. Escolhendo t k , tal que
0 < tk < 2
[ f ( xk ) − f ( x*)]
ξk
k
não é
, temos que
x k+1 – x*  < x k – x* .
Prova: Ver Lemaréchal, (1989).
Observação 3.35 Para obter convergência da seqüência {x
k
}, é necessário que o
tamanho do passo cumpra:
t k ↓ 0 quando k → ∞.
Algumas dificuldades podem aparecer. Por exemplo, a redução do tamanho dos
passos poderia ser lenta, ou, se S = ∑ ∞k=0 t k é finita, a seqüência {x k} tem um limite
x - , mas se
min x k – x* > S, então x -∉X*
x*∈X*.
(onde X* é o conjunto de pontos mínimos de f ).
Para garantir convergência global devem cumprir-se as seguintes condições:
t k ↓ 0 quando k → +∞ e ∑ ∞k=0 t k = +∞.
Ver Makela, (1992), e Shor, (1985) e (1998).
34
3.4.2 Métodos de Feixes
Dado o problema
P, (3.1), a seguinte hipótese é comum em otimização não
diferenciável: em cada ponto x∈R n pode-se avaliar a função f(x) e pelo menos um subgradiente ξ∈∂ f(x) .
As seguintes tarefas são características dos métodos de feixes:
1-Os sub-gradientes das iterações passadas podem ser reunidos em um conjunto que
chama-se feixes de subgradientes;
2-Desde que as direções fornecidas pelos sub-gradientes não são necessariamente
direções de descida, a busca linear é substituída pela realização do que vai-se chamar
de um passo serio ou um passo nulo, dependendo da diminuição da função objetivo,
segundo a regra a seguir:
Seja y
k+1
= x
k
+ t
k
d
k
,
para algum t
k
>0 , d
k
é a direção do sub-gradiente
dk∈co{ξk} e ξ k+1∈∂ f(yk+1) . Então, se f(yk+1) ≤ f(x k) - δ k , para algum δ k>0, fazemos
um passo serio: x k+1 := y k+1 .
Em outro caso, fazemos um passo nulo: x k+1 := x k .
Em ambos os casos ξ k+1 deve ser adicionado ao pacote de feixes.
3.4.2.1 Método do Plano de Corte Generalizado de Kiwiel.
Este método de feixes baseia-se no método clássico de plano de corte. Vamos
considerar o método para o caso de funções convexas. A idéia fundamental, é formar
uma aproximação linear por partes à função objetiva usando a linearização gerada
pelos sub-gradientes. O método permite encontrar uma direção de descida
iteração k.
Definição 3.36 Seja f : R n → R e ξ∈∂ f(y),
i)A linearização de f no ponto y, f –(. ;y ) : R n → R, é definida por
d
k
na
35
f –(x; y) = f(y) + 〈ξ , x-y〉 , x∈R n.
ii) O erro de linearização se define como α (x ; y) = f(x) - f –(x; y).
Quando f é convexa, α ( y; x) ≥ 0 (ver Figura 10).
f
f –( x; y)
f(x)
α (y; x)
y
x
Fig. 10 O erro de linearização α ( y; x) para uma função convexa no ponto x.
Observação 3.37 Pelo Teorema 3.28-1, uma função convexa f tem a representação,
f(x) = max { f –(y ;x) / ξ∈∂ f(y) , y∈R n} ,
x∈R n
Já que nesta representação, é preciso conhecer os conjuntos sub-diferenciais
para cada y∈R n, considera-se somente alguns pontos auxiliares yj∈R
n
∂f(y)
e os sub-
gradientes ξ j∈∂ f(yj ) , para j∈Jk ⊆ {1,2,...,k}, J k≠φ.
A seguir definimos uma aproximação linear por partes para a função f na iteração k,
como segue
36
f k=(x):= max { f –( x; y) / j∈Jk } , ∀x∈R n, (ver Figura 11).
f 3=(x)
f
y1
y2
y3
Fig.11 A aproximação linear por partes f 3=(x) à função f usando pontos auxiliares
Lema 3.38 Para todo ponto x∈R n e j∈Jk temos
1) f k=(x) ≤ f(x),
2) f k=(yj ) = f(yj ),
3) f k=(x) = max{−α ( y j ; xk ) + ξ j , x − xk } + f ( xk )
j∈J k
Prova: Ver Lema 2.3.1.1, Makela, (1992).
Vamos usar a aproximação linear por partes f
k=
da função f para gerar uma direção
de descida.
No caso diferenciável, quando o ponto x k ∈R
n
não é ótimo, então existe uma direção
0≠d ∈R n tal que f ’(x k;d) < 0.
Pelo desenvolvimento de Taylor truncado de primeira ordem, tem-se que
f ‘(x k;d) = f(x k + d ) – f(x k).
Assim, o objetivo é encontrar uma direção d k∈R n tal que f(x k + d ) < f(x k).
O problema de encontrar esta direção d k a partir do ponto x
como:
k
, pode ser formulado
37
min f (xk + d) – f(xk).
(3.4)
d∈R n
Como no ponto (xk + d) as funções f e f k= coincidem, então podemos substituir f(xk +
d) por f k=(x k + d). Assim, obtemos o seguinte problema:
min f k=(xk + d) – f(xk)
(Q):
(3.5)
d∈R n
Pelo Lema 3.38-3,
f k=(x) = max{−α ( y j ; xk ) + ξ j , x − xk } + f(x k) , e fazendo x - x k = d,
j∈J k
f k=(x k + d) = max{−α ( y j ; xk ) + ξ j , d } + f(x k)
j∈J k
Substituindo no problema Q, obtemos:
min f k=(xk + d) – f(xk) = min max {-α kj + 〈ξ j , d 〉 }
d∈ R n
onde
(3.6)
d∈Rn j∈Jk
-α kj = α (xk ;yj )
definindo v := max {-α kj + 〈ξ j , d 〉 },
j∈Jk
transforma-se o problema Q para o problema de plano de corte com um número finito
de restrições lineares
(PC):
minimizar
v
(3.7)
(d,v)∈Rn+1
s. a. -α kj + 〈ξ j , d 〉 ≤ v ,
∀ j∈Jk
Para assegurar solução única do problema Q, (Makela, 1992), adicionamos um termo
de penalidade, (1/2) d
2
à função do problema. Obtém-se
minimizar f k=(xk + d) + (1/2) d
d∈ R n
2
– f (xk)
(3.8)
38
e de modo equivalente, temos o problema
minimizar v + (1/2) d
2
(3.9)
(d,v)∈Rn+1
s. a. -α kj + 〈ξ j , d 〉 ≤ v ,
∀ j∈Jk
Por dualidade, este problema equivale a encontrar os multiplicadores λkj para j em Jk
que resolvem o problema,
( PD) :
1
min
λ
2
s. a .
2
∑λ
j∈J k
j
ξ j + ∑ λ j α kj
j∈J k
∑ λ j = 1,
j∈Jk
λ j ≥ 0,
∀j∈Jk
(3.10)
Se os multiplicadores λkj resolvem o problema PD na iteração k, então obtêm-se a
direção de busca
d k = − ∑ λ kj ξ j .
(3.11)
j∈J k
3.5 A função valor
Nesta seção se introduz o conceito de função valor e algumas de suas
propriedades.
Estas funções aparecem em problemas de otimização que tem estrutura de problemas
de programação de dois níveis (PDN).
Um programa matemático de dois níveis é um problema de otimização no qual uma das
restrições está definida pelas soluções de um outro problema de otimização.
Os problemas que podem ser modelados como um problema de Programação de Dois
Níveis (PDN), tem algumas características como:
- Apresentam estrutura hierárquica nas tomadas de decisões, por exemplo: decisões
gerenciais nas empresas em relação aos departamentos de produção; nos bancos e
39
suas agencias, políticas de juros em relação à clientela; nos sistemas de transporte, na
administração em relação aos usuários, etc.
- As decisões são feitas em dois níveis, e não necessariamente são concordantes.
Quando existe acordo ou comunicação entre os níveis, se diz que se trata de um caso
cooperativo de PDN.
- Cada nível tem controle somente sobre algumas variáveis, e as decisões do segundo
nível são executadas depois e de acordo com as decisões do primeiro nível.
O problema matemático que deu origem o PDN foi proposto por H. Stackelberg em
1952, formulado para um modelo econômico (Shimizu et al., 1997).
O problema de dois níveis tem a seguinte formulação:
(PD N )
m in F ( x , y )
(3 .1 2 )
(x,y )
s .a .
G ( x , y ) ≤ 0 , o n d e y r e s o lv e
m in f ( x , y )
( 3 .1 3 )
y
s. a . g(x,y) ≤ 0
(x,y)∈AxB
onde f, F : R n x R m → R,
G : R nx Rm → Rp ,
g : R n x R m → R q , e A⊂Rn , B⊂R m
.
Observar que, no problema PDN o problema do nível superior minimiza apenas na
variável x. Com freqüência o problema do nível superior chama-se de problema do líder,
e o problema do nível inferior, de problema do seguidor. Assim, x é chamada variável
(ou parâmetro) de decisão do nível superior, e o y a variável de decisão do nível
inferior.
A formulação do PDN faz necessário definer os seguintes conjuntos:
Conjunto viável do problema do seguidor
40
S(x):= { y∈R n/ g(x,y) ≤ 0, (x,y)∈AxB }.
Conjunto de soluções ótimas do seguidor
Y(x):= argmin { f(x,y) / y∈S(x)}={ y*∈B / f(x,y*) =min f(x,y) , y∈S(x)}.
Conjunto viável do problema de dois níveis (ou conjunto das reações racionais)
ψ = {(x,y*) / G(x,y*) ≤ 0, y*∈Y(x)}.
O problema PDN pode ser formulado de outra forma, definindo uma função associada
ao problema do nível inferior, denominada de função valor (ou função marginal).
A função v : R n → R∪{- ∞, +∞} definida por:
v( x) = min f ( x, y )
y∈B
é conhecida como função valor, e quando S(x)=φ então v(x)= +∞.
A função valor, em geral, é não convexa e/ou não diferenciável, ainda que as
funções f e g
do problema sejam convexas e/ou diferenciáveis. Considerando a
definição da função valor, o problema PDN pode agora ser formulado como um
problema equivalente de um nível só:
(PDN-V):
min F(x,y)
(3.14)
(x,y)
s. a .
G(x,y) ≤ 0
f(x,y) - v(x) ≤ 0
(3.15)
(x,y) ∈ AxB
O problema PDN-V em geral, é um problema não convexo e/ou não diferenciável. Para
sua solução pode-se aplicar a teoria e métodos de otimização não diferenciável, como
por exemplo os descritos na seção anterior, Bard (1999).
41
CAPÍTULO 4
Formulação do Problema de Projeto de Redes de Tráfego
Neste capítulo se apresenta a formulação do problema de transporte abordado neste
trabalho, chamado de Projeto de Redes de Tráfego (PRT). Como foi exposto no
CAPÍTULO 1, o problema de projeto de redes de tráfego a ser considerado é o PRT
continuo. Embora, segundo Bell e Iida, (1997) essa classificação não é absoluta, pois o
variável continua que representa a capacidade de arco pode ser usado para remover
arcos de uma rede. Na tese, se considera a variável de capacidade contínua para
permitir pequenas mudanças destas capacidades na rede.
4.1 Preliminares
Neste trabalho se considera um sistema de transporte sob a administração de um
decisor, que identificaremos como o administrador da rede. Em geral o administrador
tem objetivos específicos, os que podem ser dar segurança no transporte, evitar
congestionamentos, controlar a poluição do ar, etc. Pode-se resumir estes objetivos
afirmando que o interesse do administrador é otimizar investimentos para dotar a rede
de um melhor desempenho.
Dizemos, usuário da rede a todo aquele que trafega pela rede fazendo uso de
diferentes modos de transporte.
A seguinte notação será utilizada:
fi : fluxo sobre o arco i
si : capacidade do arco i
f = (fi)
m
i=1
, vetor de fluxos sobre arcos
s =(si) m i=1 , vetor das capacidades dos arcos.
42
Uma função C : RmxRm → Rm , que representa os tempos generalizados (custos) de
viagem sobre arcos que assume-se uma aplicação contínua. Se f =( f1 ,...,fm)∈R m é um
vetor de fluxo na rede, então o custo total de viagem será definida por:
〈 f ,C(f,s)〉 = f1.C1(f,s) + ...+ fm.Cm(f,s) = ∑ mj=1 fj Cj(f,s),
(4.1)
Para cada arco i da rede , associa-se também uma função Ii: R → R, que representará
uma função de custos de investimentos para o arco i, dependendo da capacidade si
sobre o arco. Assume-se esta função crescente em relação à variável si e como em
Migdalas (1995), é considerada linear. Logo, define-se uma função real de variável
vetorial q: R m → R, com
q(s) = ∑ m i=1 Ii (si ).
(4.2)
O fato de ser definida q desse modo vai dar à função o nome de função separável
sobre arcos. A função q representa de um modo geral, o capital investido e os custos
de operação sobre a rede.
Considerando as notações acima então a função do custo total de viagem na
rede pode ser exprimida de forma mais enxuta
T(f,s) = ∑ m i=1 [ Ii(si) + fi . Ci(f,s) ] = 〈 f , C(f,s)〉 + q(s)
(4.3)
4.1.1 O Problema de Projeto de Redes de Tráfego
De modo geral, como acabamos de ver, o administrador (ou planejador) dos transportes
tenta minimizar uma função T(f,s), que representa o custo total do sistema (custo de
viagem e de investimentos). Esta função depende do fluxo e da capacidade da rede. O
fluxo f pode ser obtido sob determinadas hipóteses teóricas e técnicas.
43
No caso em que os usuários escolhem (escolha que pode ser feita sob duas hipóteses
de comportamento do usuário: determinístico ou estocástico) suas rotas e modos de
viagem no interesse de minimizar seus custos individuais de viagem, o fluxo resultante
é chamado fluxo de equilíbrio do usuário. Os custos em rotas (ou arcos) associados a
esses fluxos, são chamados de custos de equilíbrio, e são caracterizados pelo fato que
nenhum usuário pode melhorar seu custo de viagem escolhendo unilateralmente outra
rota (ou modo). Como o fluxo de equilíbrio é conseqüência da escolha da rota e modo
de viagem do usuário, não necessariamente corresponde à maneira mais eficiente de
usar a rede de transporte, (do ponto de vista do interesse social, que é o de minimizar o
custo total do sistema). Por isto, o administrador tenta influenciar as decisões dos
usuários através de medidas de controle (por exemplo, impondo limites de velocidade,
pedágios, sinais de tráfego, etc.), ou melhorando as rotas (maior capacidade, menor
poluição, maior segurança, etc.) e desta forma fazer algumas rotas mais atrativas do
que outras. Quando se encontra o custo total mínimo do sistema, o nível de fluxo
correspondente é chamado fluxo ótimo do sistema.
4.1.2 O Fluxo de equilíbrio do usuário e o fluxo ótimo do sistema para um
modelo de dois níveis do PRT
O problema de projeto de redes de tráfego (PRT), formulado como um problema de
programação matemática de dois níveis, no primeiro nível minimiza-se a função do
custo total do sistema, e no segundo nível resolve-se o problema de equilíbrio do
usuário. A solução do problema do segundo nível (problema de equilíbrio do usuário),
isto é, o fluxo ótimo do usuário f, não necessariamente minimiza a função do primeiro
nível (problema do líder ou administrador). Neste caso, o administrador tentará obter
outro fluxo, para o qual apresentará um novo plano reajustando sua variável de
decisão, a capacidade s, afetando assim os usuários. No caso que a função do
administrador seja minimizada, o processo termina. Caso contrario, o processo
continua. É neste processo, que o fluxo de equilíbrio do usuário tende para o fluxo
ótimo do sistema.
44
Quando a escolha das rotas e modos de viagem por parte dos usuários é feita baseada
somente na percepção, e sob a hipótese do pleno conhecimento das condições das
rotas (como por exemplo, qualidade das vias, sinalização, congestionamento, poluição,
pedágios, etc.), os usuários tem comportamentos semelhantes em relação a essa
escolha. O fluxo resultante é conhecido como fluxo determinístico ótimo do usuário (e o
modelo que permite achar esse fluxo, é chamado de problema de equilíbrio
determinístico do usuário). Se a informação previa sobre as condições das rotas não é
suficiente, cada usuário terá percepções diferentes sobre os tempos generalizados de
viagem das rotas. Isto quer dizer que uma mesma rota poderia ter, para diferentes
usuários, diferentes tempos generalizados de viagem. O fluxo resultante desta forma é
chamado de fluxo estocástico ótimo do usuário (o modelo para determinar esse fluxo é
chamado de problema de equilíbrio estocástico do usuário, que se caracteriza por
considerar funções de probabilidade na escolha de rota e modo de viagem). Cabe
mencionar que o problema de equilíbrio aparece em outros contextos, por exemplo, na
Teoria de Jogos, em Economia (Bastos,1999 ) e em Desenho de Estruturas.
4.2 Formulação do problema PRT
Quando se faz uma formulação do problema de Projeto de Redes de Tráfego contínuo,
se modela, de um lado, o interesse do administrador de minimizar o custo total do
sistema; de outro lado, o usuário escolhe rotas O/D levando em consideração a
minimização do seu tempo (generalizado) de viagem.
Em resumo, o problema de projeto de redes de tráfego, consiste em: determinar
um vetor de capacidades s- ≥ 0 e um vetor de fluxo de tráfego f* que resolvem a
desigualdade variacional
〈 C(f*,s- ) , f - f*〉 ≥ 0,
∀ f ∈Ω
(4.4)
tal que o par (f*,s-) minimize a função T definida na relação (4.3). O problema então,
se diz que é formulado como problema de programação de dois níveis generalizado. Na
literatura, este modelo também é chamado Problema de Programação Matemática com
45
uma Restrição de Equilíbrio, ou Problema de Dois Níveis Generalizado, Morales,
(1997), e tem a forma seguinte:
(PDNG):
minimizar T(f,s) = 〈 f , C(f,s)〉 + q(s)
(4.5)
f,s≥ 0
s. a .
f ∈Ω
resolve:
〈 C(f ,s ) , g - f 〉 ≥ 0 ,
∀ g∈Ω,
(4.6)
onde Ω é o conjunto de fluxos viáveis da rede que satisfazem restrições de:
de conservação de fluxo, e
b) de não negatividade, apresentadas a seguir.
Na seguinte formulação das restrições, os índices i, j, k denotarão nós origem
ou destinos. Para k∈O e i∈N, temos:
a) ∑ j∈Ei f kij - ∑ j∈Ii f kji =
∑ l∈D d il ,
se i=k∈O
- d kl
,
se i∈D
0
,
se i∉O∪D ,
b) f kij ≥ 0 , ∀ i, j, k ,
onde
O : conjunto de nós origem
D : conjunto de nós destinos
N: conjunto de nós na rede de transporte
Ei= { j / o arco (i,j) sai do nó i }
Ii = { j / o arco (j,i) ingressa no nó i }
dkl :demanda de viagem O/D entre os nós k∈O e l∈D
f kij : fluxo que provêm do nó k∈O e percorre o arco (i,j)
N : conjunto de nós na rede de transporte, N⊇O∪D.
46
Observar que, condição (a) relaciona demandas e fluxos sobre arcos do percurso de
uma rota que envolve uma origem ou um destino k, além de respeitar a condição de
passagem só.
A solução do problema de equilíbrio de tráfego (a desigualdade variacional (4.6))
é única, no caso em que fixada uma capacidade s -, a função C resulte estritamente
monótona em relação à variável de fluxo f, isto é, se cumpre que,
〈 C(f1,s -) –C (f2 ,s-) , f1 –f2 〉 > 0 , para qualquer par (f1,f2)∈Ω, f1 ≠ f2 ,
Cabe mencionar que, em geral, a função de custo do sistema,
T(f,s) = 〈 f , C(f,s)〉 + q(s)
é não convexa. Embora, sob hipóteses restritivas para C, como por exemplo, que as
funções componentes Ca
para cada arco a, dependam somente do fluxo fa e da
capacidade sa do próprio arco (do qual resulta que sua Jacobiana é simétrica), que
cada função Ca seja positiva, crescente, continuamente diferenciável e convexa; e que
a função q(s) seja convexa, então T resulta também convexa. Neste caso, o problema
de achar o ótimo do sistema é um problema de programação convexa.
Neste trabalho, para a aplicação do algoritmo de Projeto-Alocação (ver seguinte
seção) para resolver o PRT, se considera o caso mais geral, onde a função C tem
Jacobiana na simétrica (fato que permite modelar a interação de fluxos em arcos da
rede), é estritamente ou fortemente monótona, e a função objetiva T(f,s) do líder é
continua, diferenciável, embora não necessariamente convexa.
47
4.3 Metodologia
No problema Projeto de Redes de Tráfego contínuo, formulado como um Problema de
Dois Níveis Generalizado (4.5)-(4.6), onde a Desigualdade Variacional modela um
problema de equilíbrio de tráfego, considera-se para o Equilíbrio de Tráfego (ET), tanto
o modelo padrão como o modelo geral. Sabe-se que no caso geral, não é possível uma
representação do ET como um problema de otimização convexa, pelo que a formulação
do PRT como PDNG é apropriada e inevitável.
Na formulação de PRT como um PDNG, dada uma capacidade s, deve-se resolver a
DV para achar o fluxo de equilíbrio correspondente. Como assinalado por Marcotte,
(1984), a solução da DV sempre foi a parte mais complicada de resolver, e da literatura
existente pode-se dizer que ainda hoje a maioria dos modelos de ET evita uma
formulação de DV.
Na presente tese, para resolver o problema PRT propomos um algoritmo que tem um
esquema iterativo denominado de Projeto-Alocação (P-A), e outro de natureza de
penalidades. No algoritmo de P-A, fixada uma capacidade na função do líder, o
problema de equilíbrio de tráfego (a DV 4.6) é solucionado utilizando um algoritmo que
é uma adaptação para o caso do ET, do algoritmo encontrado no trabalho de Arica et
al., (1996), e que, para resolver uma DV usa a definição de função gap associada à
DV.
As seguintes são definições necessárias para o método de solução de um PRT
proposto neste trabalho.
Dado um vetor s- de capacidades dos arcos, a função gap: R
m
→R, associada à
desigualdade variacional (4.6) é definida como
gap s − ( f ) = sup{〈C(f ,s- ) , f - g〉 , g∈Ω },
onde s- é um parâmetro fixo na definição da função gap.
Esta função é não negativa e indica uma certa medida do afastamento entre o fluxo
atual f e o fluxo de equilíbrio, solução da DV.
Aqui, Ω é um conjunto convexo compacto dos possíveis fluxos, então o cálculo do
supremo pode ser substituído pelo cálculo do máximo, i.e.
48
gap s − ( f ) = max{〈C(f ,s- ) , f - g〉 , g∈Ω }.
(4.7)
Observação 4.1 A solução da DV (4.6) no problema PDNG fornecerá características
não convexas e não diferenciáveis ao modelo PRT, o que fica evidenciado ao empregar
a função gap associada à desigualdade variacional, pois é um caso de função valor, ver
seção 3.5, pág. 37.
As seguintes propriedades da função gap são estabelecidas em Larsson e Patriksson
(1993), e Morales (1996):
gap s − ( f ) ≥ 0, ∀ f∈Ω , s-> 0 ;
(4.8)
gap s − ( f ) =0 se, e somente se, f resolve a DV (4.6) .
(4.9)
Desde que gap s − ( f ) ≥ 0, um algoritmo que minimize a função gap permitirá achar o
zero desta função, isto é, em um processo iterativo achar-se-ia uma aproximação a dito
zero.
Assim, o algoritmo de Projeto-Alocação de minimização da função gap permitirá
resolver a DV, e a solução (vetor de fluxos de equilíbrio), por sua vez, será usada no
nível superior para determinar uma aproximação ao vetor ótimo de capacidades.
Em Marcotte e Dussault (1989), apresentam-se as funções gap primal e gap dual
definidas como:
gapP ( x) = max F ( x), x − y ,
(4.10)
e gapD ( x) = max F ( y ), x − y .
(4.11)
y∈φ
y∈φ
Pela Propriedade (4.9), tem-se que uma desigualdade variacional (DV) pode ser
resolvida pela seguinte sequência de problemas de aproximação, associados à função
gap P (x), ver seção (5.4),
49
( Pk ) :
min α
( x ,α )
s.a. F ( x), x − y j ≤ α ,
j = 1,..., k .
Analogamente, associados à função gap dual gapD(x), podem-se utilizar os problemas
de aproximação seguintes:
( Pk ) :
min α
( x ,α )
s.a. F ( y j ), x − y j ≤ α ,
j = 1,..., k .
Destas duas funções, Arica et al. (1996) utiliza a formulação gap dual para resolver
uma desigualdade variacional definida por uma aplicação Ponto- Conjunto.
Observação 4.2 Utilizando as idéias de Arica et al. (1996) para resolver uma DV, neste
trabalho se resolve o problema de equilíbrio de tráfego formulado como uma DV,
fazendo notar que nos problemas Pk cada restrição é não linear.
Observação 4.3
No caso que a desigualdade variacional esteja definida por uma
aplicação Ponto a Ponto, o método de solução usando as funções gap primal e gap
dual garantam convergência global ao ponto de mínimo que é o valor zero, Larsson e
Patriksson (1993).
50
CAPÍTULO 5
Algoritmo de Projeto – Alocação e de Penalidade
Neste capítulo, apresenta-se a descrição do algoritmo de Projeto – Alocação (P-A) para
calcular uma aproximação da solução do modelo de programação de dois níveis
generalizado do problema de Projeto de Redes de Tráfego (PRT).
Neste modelo, o segundo nível representa um problema de equilíbrio de tráfego (ET), e
está modelado por uma desigualdade variacional (DV), o que permite considerar o caso
de interação de fluxos de diferentes arcos da rede. Considera-se o caso, como já foi
assinalado, de uma matriz Jacobiana da função tempo de viagem generalizado não
simétrica, então o problema de ET não tem uma formulação equivalente com um
problema de otimização, isto é feito com o intuito de fazer uma modelagem mais geral
do problema.
Também será apresentado um método (aqui será chamado de método da minimização
da função gap) para resolver o problema de ET formulado como uma DV, que é uma
adaptação do algoritmo em Arica et al. (1996), para resolver uma DV, e as
demonstrações dos teoremas de convergência, existência e unicidade da solução de
alguns casos do problema de ET.
Cinco exemplos serão apresentados no final do capítulo, os dois primeiros testam o
método da minimização da função gap, comparando-o com exemplos da literatura em
quanto ao número de iterações que se emprega para encontrar o fluxo de equilíbrio de
tráfego. Um terceiro exemplo para o problema ET considera uma função que modela a
interação dos fluxos em arcos. Para o problema de PRT, formulado como um problema
de dois níveis generalizado o qual é mostrado a seguir, se propõem dois exemplos, e
se encontra uma aproximação ao par solução (f,s) do problema, onde f é o vetor de
fluxo e s é o vetor das capacidades. Na formulação do problema de ET, no caso sem
51
interação de fluxos entre arcos, a função que define a DV é uma função do tipo BPR
(Bureau of Public Roads) que tem a propriedade de ser estritamente monótona, e para
o caso com interação de fluxos, a função é fortemente monótona.
Lembrar que o problema de Projeto de Redes de Tráfego neste trabalho é formulado
como um Programa matemático de Dois Níveis Generalizado (PDNG), e tem a forma
seguinte:
(PDNG)
min T ( f , s )
(5.1)
( f , s )≥0
s.a. f∈Ω resolve:
〈 C(f,s) , g - f 〉 ≥ 0 ,
∀ g∈Ω,
(5.2)
onde T ( f , s ) = f , C ( f , s ) + q ( s)
5.1 Algoritmo Projeto-Alocação (P-A) para o Projeto de Redes de Tráfego
Este algoritmo na sua estrutura considera-se formado por duas fases. A fase de
equilíbrio (ou do segundo nível) e a fase do líder (ou do primeiro nível).
Na fase de equilíbrio, para um vetor de capacidades fixo, o algoritmo de minimização da
função gap,
encontra uma aproximação ao zero dessa função, o que resulta uma
aproximação ao fluxo de equilíbrio do usuário.
Na fase do líder, com um fluxo de equilíbrio fixo encontrado na fase de equilíbrio, o
algoritmo encontra uma nova capacidade. Uma iteração do algoritmo de P-A consta das
duas fases
Seja V o valor da função objetivo T(f,s) a ser atingido pelo administrador.
Passo (0) - Escolher um vetor s- de capacidades positivas, isto é s- = (s-i) e
s-i >0, i = 1,...,m , e um número ε > 0, que é o parâmetro de precisão usado no
algoritmo.
Passo (1) - Resolver a desigualdade variacional (5.2):
Encontrar f∈Ω , tal que
〈C(f ,s- ) , g - f 〉 ≥ 0, ∀ g∈Ω.
52
Seja f* solução da DV (5.2).
Passo (2) –Resolver o problema do líder (L):
(L):
minimizar T(f*,s) = 〈 f* , C(f* ,s)〉 + q(s)
(5.3)
s≥ 0
Seja s* a solução de (L).
Se
T(f*,s -) ≤ V, então PARAR. A solução do problema PDNG é (f*,s-) . Em outro
caso, fazer s- ← s* e ir ao Passo (1).
Observação 5.1
O vetor fixo de capacidades
s
-
representa o plano inicial do
administrador.
Observação 5.2 A desigualdade variacional no Passo 1, será resolvida pelo método do
algoritmo da minimização da função gap, apresentado mais adiante.
Observação 5.3
No Passo 2, o valor
V
da função objetivo do líder, pode ser
interpretado como o monto do investimento do qual o administrador dispõe para fazer
melhorias na rede de tráfego. No algoritmo, o valor V será usado para compará-lo com
os valores de T(f,s) obtidos nas iterações e parar o processo iterativo quando se
cumpra que T(f*,s -) ≤ V. A estimação do valor de V a priori pode ser feita considerando
um resultado em Marcotte (1984) que detalhamos na observação (5.16)
5.2 Adaptação do algoritmo de minimização do gap, para resolver um
problema
de equilíbrio de tráfego formulado como uma DV.
Lembremos as propriedades (4.8) e (4.9) da função gap mencionadas no Capítulo 4. A
relação (4.9) é a seguinte: gap s − ( f *) =0 se, e somente se, f* resolve a DV (4.6). Esta
53
relação permite formular o problema do cálculo da solução da DV como o seguinte
problema de minimização equivalente:
f * resolve a DV ⇔ min gaps− ( f ) = gaps− ( f *)
f ∈Ω
Por tanto, a minimização de
= 0.
(5.4)
gaps − ( f ) , f ∈ Ω, fornecerá o fluxo de equilíbrio ótimo
f*∈Ω..
O problema de minimização (5.4) se resolve empregando um artifício conhecido no
ambiente da programação matemática. Este consiste em utilizar a seguinte variável
auxiliar:
α = gap s − ( f ) = max { 〈C( f,s-) , f - g 〉, g∈Ω }
(5.5)
para transformar o problema (5.4) , no seguinte problema equivalente:
(P):
min α
(5.6)
( f ,α )∈R n+1
s. a . o fluxo f ∈Ω satisfaz
〈C( f,s-) , f - g 〉 ≤ α ,
∀ g∈Ω.
(5.7)
O Problema (P) que aparentemente apresenta uma restrição só, é conhecido como de
programação semi-infinita, pois tem de ser satisfeita para cada elemento g∈Ω , isto é,
possui infinitas restrições. Pode ser resolvido utilizando uma seqüência de problemas
aproximados como mostrado em Arica, et al. (1996). Deste modo, o passo (1) do
algoritmo P-A, o de resolver a DV consistirá em resolver o problema (P) por
aproximações sucessivas.
Na seguinte seção apresentamos a seqüência de problemas, que por aproximações
sucessivas resolvem o problema (P).
54
5.3 Sequência de problemas aproximados que resolvem o problema (P)
Dados
(Pk):
{g i }ik=1 ∈ Ω, considere o seguinte problema:
min α
(5.8)
( f ,α )∈ R n+1
s. a . o fluxo f ∈Ω satisfaz
〈C( f,s-) , f – g i 〉 ≤ α ,
i = 1,2,...,k.
(5.9)
O problema (Pk) é chamado problema aproximado ao Problema (P).
O algoritmo no processo de solução, calculará em cada iteração o valor da função gap
no vetor f de fluxo atual, para o qual encontra o vetor g que fornece esse valor. Os
pontos gerados por estes problemas além de se aproximar da região viável, também se
aproximam do conjunto solução. Por esta razão, o critério de parada é a viabilidade do
par solução (f*, α * ) para o problema (P) (Lema 2.1, Arica et al., 1996).
5.4 Passos do Algoritmo da Minimização da função gap
Passo (0). Escolher um fluxo viável g 1∈Ω. k:=1.
Passo (1). Resolver o problema
(Pk):
min α
(5.10)
( f ,α )∈ R n+1
s. a . o fluxo f ∈Ω satisfaz
〈 C( f,s-) , f – g 1 〉 ≤ α ,
i = k.
Seja (f k, αk ) a solução de Pk . Para f k encontrar o fluxo g k+1∈Ω tal que
(5.11)
55
gap s− ( f k ) = max { 〈 C(f k, s -), f k - g〉 } = 〈 C(f k, s -), f k – g k+1 〉
g ∈Ω
(5.12)
Passo (2)
Se
gap s − ( f k ) ≤ α k ,
(5.13)
o par (f k, αk) é viável para o problema P. Então PARAR, o par (f k, αk) é solução
ótima do problema P. Caso contrario, montar o problema Pk+1
(Pk+1):
min α
(5.14)
( f ,α )∈ R n+1
s. a . o fluxo f ∈Ω satisfaz
〈C( f,s-) , f – g i 〉 ≤ α ,
i = 1,2,...,k, k+1,
(5.15)
Fazer k:=k+1 e voltar ao Passo 1.
Observar que:
- No Passo (0), é fácil conseguir um fluxo que satisfaça a viabilidade, isto é g 1∈Ω.
- Todas as restrições são não lineares, e em cada problema aumentam segundo o
valor de k .
- No Passo (2), o Critério de Parada significa que tem-se encontrado uma aproximação
ao zero da função gap, em conseqüência f
k
será uma solução de equilíbrio da DV,
que neste caso é única.
5.5 Algoritmo de Penalidade para o problema PRT
Uma metodologia que é usada para resolver problemas de dois níveis sugere penalizar
às restrições de maior complexidade. Incorporando esta técnica aos resultados e
propriedades da função gap, (4.8) e (4.9) apresentadas no capítulo 4; chega-se a
mostra que o problema de dois níveis generalizado (PDNG) é equivalente ao problema
(Pgap) que por sua vez será aproximado pelo problema (Pµ). Assim
56
( Pgap ) :
min T ( f , s )
( f ,s ) ≥ 0
s.a. gap ( f , s ) = 0.
Onde gap ( f , s ) = max C ( g , s ), f − g .
g∈Ω
Dado µ > 0, o problema (Pgap) pode-se formular como:
min T ( f , s ) + µ gap 2 ( f , s ) .
( Pµ ) :
( f ,s ) ≥ 0
Utilizando o Teorema 9.2.2, Capítulo 9, Bazaraa et al. (1979), pode-se assegurar que :
Se (f µ ,s µ ) ≥ 0 é tal que
T ( f µ , sµ ) = min T ( f , s ) + µ gap 2 ( f , s ) ,
f ,s ≥ 0
então, dado (f - ,s - ) limite de qualquer subseqüência convergente de {f µ ,s µ }µ≥ 0 , temse que (f - ,s - ) é solução ótima do problema (Pgap) e gap(f - ,s - ) = 0.
Por outro lado, dado µ >0, temos que se cumpre a seguinte equivalência:
( Pµ ) : min T ( f , s ) + µ gap 2 ( f , s ) ⇔ ( P1µ ) : min T ( f , s ) + µ α 2
( f , s ) ≥ 0, α
( f ,s ) ≥ 0
s.a. C ( g , s ), f − g ≤ α , ∀ g ∈ Ω.
Para resolver o problema semi infinito (P1µ) considera-se então, que para cada µ fixo e
dado {g1 , ... , gk } ∈Ω, se calcula (f µk+1 ,s µk+1 , α µk+1 ) solução de
( P1µ ) k : min T ( f , s ) + µ α 2
( f , s ) ≥ 0,α
s.a. C ( gi , s ), f − gi ≤ α , i = 1,..., k
57
µ
µ
µ
então, T ( f k +1 , sk +1 ) + µ (α k +1 ) ≤ T ( f *, s*) + µ gap ( f *, s*), ∀( f *, s*) ∈ Ω x Ω. .
2
2
A seguinte proposição, estabelece a relação entre (f
µ
k+1
, s
µ
k+1
, α
µ
) solução de
k+1
(P1µ)k , e a solução de (Pµ).
Proposição 5.4
(f
µ
k+1
, s
µ
k+1
, α
Seja (f µk+1 , s µk+1 , α µk+1 ) solução do problema (P1µ)k . Então, se
µ
k+1
) é viável para o problema (P1µ) , tem-se que (f
µ
k+1
, s
µ
k+1)
é
solução de (Pµ).
Prova
Seja (f µk+1 , s µk+1 , α µk+1 ) solução de (P1µ)k . Então,
C ( g j , skµ+1 ), f kµ+1 − g j ≤ α kµ+1 , j = 1,..., k .
Suponha que (f µk+1 , s µk+1 , α µk+1 ) é viável para o problema (P1µ) , mas não é ótimo
para (Pµ). Então, existe um ponto (f*, s*, α*) com f*, s* ≥ 0, tal que
i)
ii)
〈 C(g,s*), f* - g 〉 ≤ α* , ∀ g∈Ω, e
T(f* ,s*) + µ α* 2 < T(f µk+1 ,s µk+1 ) + µ (α µ k+1) 2
Desde que (i) vale para todo g ∈Ω , em particular vale para g i∈Ω , i=1,...,k; i. e.
(f* ,s* , α*) é viável para (P1µ)k ; mas, de (ii), temos que existe um ponto viável para
(P1µ)k , com valor da função objetivo menor, que é uma contradição.
Portanto, fica provada a proposição
O Algoritmo de Penalidades
Note-se que, se
(f
µ
k+1
, s
µ
k+1
, α
equivalentemente para (P1µ), temos que
µ
k+1
)
não é viável para o problema (Pµ),
58
gap ( f kµ+1 , skµ+1 ) = max C ( g , skµ+1 ), f kµ+1 − g = C ( g k +1 , skµ+1 ), f kµ+1 − g k +1 > α k +1.
g∈Ω
Portanto, o ponto
(f
µ
k+1
, s
µ
k+1
, α
µ
k+1
) não é viável para o problema
( P1µ ) k +1 : min T ( f , s ) + µ α 2
( f , s ) ≥ 0,α
s.a. C ( gi , s ), f − gi ≤ α , i = 1,..., k + 1.
Destes resultados, podes-se formular o seguinte algoritmo para resolver o problema
(P1µ) que é equivalente a (Pµ).
Passos do Algoritmo
Passo (0): Determinar uma penalidade µ>0 apropriado, ε >0 parâmetro de tolerância
e um ponto g 1 ∈Ω . Fazer k:=1.
Passo (1): Resolver o problema:
( P1µ ) k : min T ( f , s ) + µ α 2
( f , s ) ≥ 0,α
s.a. C ( gi , s ), f − gi ≤ α , i = 1,..., k .
Seja (f µk+1 , s µk+1 , α µk+1 ) solução de (P1µ)k .
Passo (2): (TESTE DE PARADA)
Se gap(f µk+1 , s µk+1) - α µk+1  ≤ ε , PARAR, o ponto (f µk+1 , s µk+1 , α µk+1 ) é solução do
problema (Pµ).
Em outro caso, fazer k:=k+1 e ir para o Passo 1.
Observar que:
- No Passo (0), não é difícil conseguir um fluxo que satisfaça a viabilidade, isto é,
g 1∈Ω.
- No Passo (1), o problema (Pµ)k é problema diferenciável sendo resolvido por qualquer
pacote de programação não linear e será uma aproximação de tipo do problema (P1µ).
59
- No Passo (2), o Critério de Parada significa encontrado uma aproximação ao zero da
função gap, em conseqüência f
k
será uma solução de equilíbrio da DV, que neste
caso é única.
- Não se menciona no algoritmo as repetições necessárias do mesmo para outros
valores do parâmetro µ conducentes a obter as condições do Teorema 9.2.2, Bazaraa
et al. (1979).
5.6 Teoremas de Existência e Unicidade da solução do problema de Equilíbrio de
Tráfego
O algoritmo iterativo de Projeto – Alocação (P-A) pode-se considerar composto de duas
fases: a fase de minimização (problema do líder), e a fase de cálculo do fluxo de
equilíbrio (problema do usuário).
Lembrar que a formulação do PDNG é a seguinte:
(PDNG)
Min T( f,s)
(5.16)
f,s ≥ 0
s. a . f ∈ Ω resolve a desigualdade variacional
〈 C( f,s) ,g-f 〉 ≥ 0 ,
(5.17)
∀ g ∈ Ω.
O algoritmo proposto, na fase de equilíbrio, resolve a (DV)
(5.17) mediante um
algoritmo de tipo planos de corte em Arica et al. (1996), que usa o conceito de função
gap associada a DV (foi feito uma adaptação para o caso do problema de ET).
Sob a hipótese de monotonia estrita para a função de custos de viagens
C : ℜ
n
xℜ
n
→ ℜ
n
, ver Dafermos (1980) e também Aastiani e Magnanti (1981)
estabeleceram a unicidade da solução da DV. Sob hipóteses de continuidade e não
negatividade das componentes da função C, foi mostrada existência da solução por
Aashtiani
e
Magnanti
(1981)
usando
uma
formulação
como
problema
de
complementaridade não linear (CNL), que é equivalente à DV. Neste trabalho,
60
fornecemos demostrações dos teoremas para o caso de demanda fixa (chamada de
demanda não elástica, ver seção 5.5.1).
O algoritmo que resolve a DV, procede a encontrar um zero da função gap resolvendo
uma sequência de problemas aproximados com um número finito de restrições, porem
crescentes, determinados por um esquema de planos de corte.
O Teorema 2.3 em Arica et al. (1996) garante a convergência do algoritmo no caso de
uma aplicação ponto-conjunto, monótona maximal, convexa e fechada. No caso do
problema PDNG , a função C é ponto a ponto, estritamente monótona como função
da variável dos fluxos f∈Ω , e continua em relação à variável das capacidades s∈Ω
(onde
Ω é um conjunto compacto ). Assim, o Teorema 2.3, neste caso, também
garante que, para cada s fixa, a sequência de pontos { f k} gerada pelo algoritmo
converge a um único ponto limite f* , o qual é solução da DV. Uma demonstração do
teorema, para este caso é apresentado mais na frente.
O algoritmo P-A na fase do líder, usa como dado o vetor de fluxos f k obtido na iteração
k-1 na fase de equilíbrio. Na iteração k o algoritmo acha o vetor das capacidades s
k
(líder) e o correspondente fluxo f k+1 (equilíbrio).
Assim, sendo f k a solução da DV encontrada na (k-1)-éssima iteração, o algoritmo P-A
na fase do líder resolve o problema:
min T( f k,s)
(5.18)
s∈Ω
Sendo sk a solução do problema (5.18), o algoritmo P-A procede a resolver o problema
de equilíbrio para achar o fluxo f
problema PDNG.
k+1
. Acha-se então, o par viável ( f
k+1
, sk) para o
O processo iterativo é repetido até encontrar uma aproximação
( f*, s*) do problema PDNG.
A seguir apresentamos uma reformulação e prova do teorema 2.3 em (Arica et al.,
1996) para o caso de uma aplicação C ponto a ponto, estritamente monótona, que
define a DV.
61
Teorema 5.5. Seja Ω⊂R
n
um conjunto convexo e compacto e C:ΩxΩ → Ω , uma
aplicação que define a DV, estritamente monótona. Então, a sequência { f k, α k } gerada
pelo algoritmo da minimização da função gap
contém uma sub- sequência que
converge a uma solução do problema
min gap s − ( f )
(5.19)
f ∈Ω
Prova
Dado
g1∈Ω ,
o algoritmo de minimização do gap gera uma sequência da forma
{(f k,αk)} tal que
gaps− ( f k+1) = C( f k+1, s− ), f k+1 − gk+1 = max C( f k+1, s− ), f k+1 − g , ∀k
g∈Ω
(5.20)
para algum g k+1∈Ω .
Sabemos, do Lema 2.1, Arica et al. (1996), que (f k+1, αk+1) é solução do problema
(P):
min
α
(5.21)
(f,α)∈R n+1
〈C(f,s -), f - g〉 ≤ α , ∀g∈Ω,
se
gaps− ( f
k +1
) = C( f
k +1
, s− ), f
k +1
− g k +1 ≤ α k +1 .
(5.22)
Suponha-se que dada qualquer sub-sequência de { f k, α k }, (5.22) não é satisfeita, i.e.,
existe ε >0, tal que
gaps − ( f j ) > α j + ε > α j , ∀j
De Morales (1997), temos que
i.e.,
gaps− ( f
k +1
) + C( f
k +1
C ( f k +1 , s − ) ∈ ∂ gaps − ( f k +1 ),
, s− ), g − f k +1 ≤ gaps− (g), ∀ g .
Então, g=f j , usando (5.20), temos que
(5.23)
62
gaps − ( f k +1 ) − C ( f k +1 ), f k +1 − f
j
≤ gaps − ( f j ) = C ( f j , s − ), f j − g j , ∀ j = 1,..., k .
Então, de (5.23), para j=k+1 , e a desigualdade anterior, cumpre-se que
0<ε< gaps − ( f k +1 ) - αk+1 ≤ 〈 C( f j,s- ), f j- g j〉 +〈 C( f k+1,s -),f k+1- f j〉 - αk+1 ,∀ j=1,...,k,
Logo, desde que (f k+1,αk+1) é viável para (Pk) e a desigualdade de Schwartz, temos que
ε < 〈 C( f j,s-) , f j- f k+1〉 + 〈 C( f k+1,s -) , f k+1- f j 〉 , ∀ j=1,..., k
= 〈 C( f j,s -) - C( f k+1,s -) , f j- f k+1 〉 ,
∀ j=1,..., k
≤ C( f j,s -) - C( f k+1,s -)   f j- f k+1 ,
∀ j=1,..., k
Como C(Ω) é compacto, existe K >0 tal que  C(f,s -) ≤ K, ∀ f∈Ω.
Então,
 f j- f k  ≥ ε / 2K ,
∀ j=1,..., k ,
(5.24)
o que contradiz o fato de ser Ω compacto. Portanto, existe uma sub-sequência de
{(f k,αk)} convergente a um ponto ( f*,α*) que satisfaz (5.22).
5.6.1 Existência e Unicidade da solução do caso ET
A seguir prova-se o teorema de existência e unicidade da solução do problema de
equilíbrio do tráfego, sob hipóteses de demanda fixa e interação de fluxos dos arcos. A
formulação a considerar para este problema é uma desigualdade variacional e formará
uma restrição do problema PRT objetivo central da tese. Alguns resultados prévios que
necessitamos serão apresentados a seguir.
Observação 5.6 As condições de equilíbrio de Wardrop podem ser representadas por
uma DV, Aastiani e Magnanti (1981). Nesse trabalho também formulam-se as
condições de equilíbrio de Wardrop como um problema de Complementaridade Não
Linear.
Observação 5.7 Segundo a Proposição 2.1, em Harker e Pang (1990), tem-se que: Se
X é um cone convexo e F : R
n
→ R
n
uma aplicação. Então, o ponto x*∈X é uma
63
solução do problema de complementaridade não linear
F(x*).x* = 0, F(x*) ≥ 0 , se e
somente se x* é solução da D. V. F(x*).(x-x*) ≥ 0, ∀x∈X.
As condições de equilíbrio de tráfego de Wardrop, a satisfação da demanda e a não
negatividade, podem-se formular no seguinte modelo, ver Aashtiani e Magnanti (1981):
(E1):
(Cp (h) – u i) hp = 0 ,
Cp (h) – u i ≥ 0 ,
∑ hp – d i = 0 ,
∀ p∈Pi e i∈I
(5.25)
∀ p∈Pi e i∈I
(5.26)
∀ p∈Pi e i∈I
(5.27)
h ≥0 , u ≥0
(5.28)
onde:
h=(hp) p∈P ∈ R n1 , é o vetor de fluxos em rotas,
I : conjunto de pares Origem-Destino (O/D) na rede ( I = n2
,
é o número de
elementos em I ),
Pi é o conjunto de rotas no par i origem-destino; P=∪Pi é o conjunto de rotas na rede,
i∈I ( P =n1 ),
u = (ui )
i∈ I
∈R
n2
, é o vetor de tempos de viagem mínimos generalizados, nos pares
O/D i ,
Cp : R n1+ → R+ , é a função de tempo de viagem generalizado para a rota p,
di : é a demanda de viagem para o par O /D i , e se assume constante para cada i∈I.
A : conjunto de arcos na rede.
A seguir, se considerará que a rede é fortemente conexa, isto é, que para qualquer par
de nós, existe pelo menos um arco que une o par.
Observação 5.8 Um caso especial do problema de equilíbrio (E1), é o modelo aditivo,
que consiste em definir o tempo de viagem na rota p separável por arcos como
64
Cp(h) = ∑ δap C ia(h) ,
∀ p∈Pi , i∈I ,
(5.29)
a∈A
onde A é o conjunto de arcos da rede, e δap =1 , se o arco a∈p, e δap=0 em outro
caso, e
C
i
a
:R
n1
→ R+ , é a função de tempo de viagem generalizado no arco a, no
par O/D i.
Observação 5.9 A relação 5.25 expressa o fato que no equilíbrio, as rotas com fluxo
positivo tem custo de viagem igual ao custo mínimo. A relação 5.26, diz que todos as
demais rotas terão custo de viagem maior o igual ao custo mínimo. A relação 5.27
estabelece a satisfação da demanda de viagem no par i O/D através das rotas p∈Pi .
Deseja-se expressar as condições (E1) na forma de equações de complementaridade,
para o qual fazemos as seguintes notações:
Seja x=(h,u)∈Rn , onde n=n1 + n2 ,
(5.30)
f p(x) = Cp(h) – u i , ∀ p∈Pi e i∈I ,
(5.31)
g i(x) = ∑ hp – di ,
(5.32)
∀ i∈I
p∈Pi
F(x)=[ f p(x) , g i(x)]p,i ∈Rn ,
p∈Pi , i∈I ,
(5.33)
Usando a notação acima, podemos expressar o modelo (E1) na forma,
(E2):
f p(x) hp= 0 ,
∀ p∈Pi , i∈I ,
(5.34)
f p(x) ≥ 0 ,
∀ p∈Pi , i∈I ,
(5.35)
g i(x) ui = 0 ,
∀ i∈I
(5.36)
g i(x) ≥ 0 ,
∀ i∈I
(5.37)
65
x≥0
(5.38)
Proposição 5.10 Supor que para toda p∈P , Cp : R n1+ → R+ , é uma função positiva.
Então, o sistema de equilíbrio (E1) é equivalente ao sistema de complementaridade
(E2).
Prova. Ver Proposição 4.1, em Aashtiani e Magnanti (1981).
Na prova do teorema de existência usaremos uma transformação
φ, que permite
transformar o sistema de complementaridade não linear (E2) do problema de equilíbrio
de tráfego, em um problema de ponto fixo de Brouwer, ver Kosniowski (1992).
Seja φ : R n → R n , uma aplicação definida através de suas componentes, como
φ j (x) = [x j – F j(x)] + , j=1,...,n ,
onde
[y] + = max {0,y}.
(5.39)
Então x* é um ponto fixo de φ , isto é,
x* é solução do problema de complementaridade:
x ≥ 0 , F(x) ≥ 0, xt F(x) = 0 ⇔ x* =
φ(x*), Aashtiani e Magnanti (1981).
5.6.1.1 Existência da solução
Nas condições acima estabelecidas da formulação do problema ET refere-se o seguinte
resultado:
Teorema 5.11 Seja Cp : R n1+ → R , uma função continua não negativa para cada rota
p∈P. Então o problema de complementaridade não linear (E2) tem uma solução.
Prova.
66
Seja Gi : R n1+ → R , a função definida por
Gi (h) = ∑ hp , que representa a
p∈Pi
soma dos fluxos nas rotas p para o par i O/D. Provaremos que o seguinte problema
de complementaridade, tem solução:
(E3):
(Cp (h) – u i) h p = 0 ,
∀ p∈Pi e i∈I
(5.40)
(Gi (h) – d i) u i = 0 ,
∀ p∈Pi e i∈I
(5.41)
Cp (h) – u i ≥ 0 ,
∀ p∈Pi e i∈I
(5.42)
G i (h) – d i ≥ 0 ,
∀ p∈Pi e i∈I
(5.43)
h p ≥ 0 , u i≥ 0 ,
∀ p∈Pi e i∈I
(5.44)
Seja K1 > 0 tal que K1 > max i∈I d i , e supor que K2 ≥ K1
tal que
K 2 > max
p∈P
(5.45)
max C p (h)
(5.46)
0 ≤ h ≤ K1e
onde e=(1,...., 1)∈R n1 .
Notar que K1 existe por ser o máximo de constantes di , ∀ i∈I positivas, e K2 existe
porque Cp (h) é continua sobre um conjunto compacto.
Define-se uma aplicação continua
φ : B → B , por
φ p(h,u) = min { K1 , [h p + u i - Cp(h)] + } ,
∀ p∈Pi , ∀ i∈I , e
(5.47)
φ i(h,u) = min { K2 , [u i + d i – Gi (h)] + } ,
∀ i∈I.
(5.48)
onde
B = { (h,u) / 0 ≤ h ≤ K1e , 0 ≤ u ≤ K2 ê } , e ê =(1,...,1)∈Rn2
Pelo teorema de ponto fixo de Brouwer, ver Kosniowski (1992): Se ψ: S⊂R
n
→S , é
uma aplicação continua em S, onde S é um subconjunto convexo compacto de Rn,
então existe um ponto x0 ∈S tal que ψ(x0) = x0 .
67
Assim, tem-se que φ tem um ponto fixo (ĥ,û); isto é, a nossa hipótese a considerar é,
ĥ p = φ p(ĥ p , û ) e û i = φ i (ĥ,û) , ∀ p∈Pi , ∀ i∈I .
(5.49)
Provemos que este ponto fixo (ĥ,û) é solução do problema de complementaridade
(E3); para isto mostraremos que para toda p∈Pi e toda i∈I , tem-se
ĥ p =[ĥ p + û i – Cp(ĥ)] + , e
ûi = [ûi + di – Gi (ĥ)] +.
(5.50)
Notar que û i < K2 , ∀ i∈I, pois de não ser assim, existiria algum i tal que û i = K2
e como
K2 > max
max Cp(h) ,
p∈P 0≤h≤K1e
então
K2 - Cp(h) > 0 e ĥ p + û i – Cp(ĥ) > ĥ p
ĥ p =φ p(ĥ p ,û ) = min { K1 ,[ĥ p + û i – Cp(ĥ)] +} , então ĥ p = K1 ,
Como
ainda
K1 > max di
e
Gi(ĥ) = ∑ ĥ p
p∈Pi
Gi(ĥ) > ĥ p = K1> d i ⇒ Gi (ĥ) > d i ⇒ [ûi + di –Gi (ĥ)] < ûi.
então
Sendo que
então
ûi = φ i (ĥ,û) = min {K2 ,[ûi + di – Gi (ĥ)]+} =ûi + di – Gi (ĥ) ,
û i =0 , o que contradiz ûi= K2 > 0.
ûi = [ûi + di – Gi (ĥ)] +
Portanto
(5.51)
Agora, quando ĥ p = K1 para algum i∈I e p∈Pi , então Gi (ĥ) > d i e ûi=0,
como
Cp(ĥ) ≥ 0 , então ĥ p + û i – Cp(ĥ) ≤ ĥ p .
Logo, para ter
obtém-se
ĥ
p
+ û i – Cp(ĥ) = φ i (ĥ,û) = ĥ
p
= K1> 0 , deve ser Cp(ĥ) = 0. Daqui,
68
ĥ p =[ ĥ p + û i – Cp(ĥ)] +.
(5.52)
Considerando os casos ĥ p > 0 ou ĥ p = 0 , e û i > 0 ou e û i = 0, vemos que o par (ĥ,û)
resolve o problema de complementaridade (E3). Portanto, pelo Teorema 1 em Fisk e
Boyce (1983), tem-se que x=(ĥ,û) é solução da desigualdade variacional
〈C(x), y-x〉 ≥ 0 , ∀x∈R n .
5.6.1.2 Unicidade da solução
As condições de equilíbrio do tráfego, podem ser formuladas como em Aashtiani e
Magnanti (1981), do modo seguinte:
(∆t C(f) - Λ u) h = 0
(E4):
(5.53)
∆t C(f) - Λ u ≥ 0
onde ∆
(5.54)
Λh–d=0
(5.55)
h≥0, u≥0
(5.56)
é a matriz de incidência arco/rota, Λ é a matriz de incidência O-D/rota,
f =∆ h é o vetor de fluxos em arcos, d∈Rn2 o vetor fixo de demanda, e
C: R A → R A ,
(5.57)
é a função de tempo generalizado de viagem em arcos.
Se fazemos,
definida por
x=(h,u) t. A aplicação
F : Rn+ → Rn ,
F(x) = (∆t C(f) - Λ u , Λ h – d) ,
resulta não negativa. Assim, o sistema (E4)
(5.58)
(5.59)
é uma versão de um modelo de
complementaridade não linear semelhante a (E3).
Observação 5.12 Em (5.59), a expressão ∆t C(f) representa o vetor de custos em rota,
e Λ h é a soma dos fluxos em rotas para satisfazer a demanda de viagem.
69
Teorema 5.13 Suponha-se que a aplicação C é estritamente monótona em relação à
variável do vetor de fluxos em arcos. Então o par (f,u) é solução do problema de
complementaridade (E4).
Prova.
Suponha-se que x1=(h1, u1) e x2=(h2, u2) , x 1 ≠ x 2 , são duas soluções do problema de
equilíbrio (E4).
De x1 ≥ 0 , x2 ≥ 0 , F(x1) ≥ 0 e F(x2) ≥ 0 obter-se
x1 F(x1) - x2 F(x1) - x1 F(x2) + x2 F(x2) = (x1 - x2) (F(x1) - F(x2)) ≤ 0,
substituindo
x1 , x2 , F(x1) e F(x2) , na desigualdade acima ,
(h1 - h2 , u 1 - u2) (∆t C(∆ h1) - Λ u 1 - ∆t C(∆ h2) +Λ u 2 , Λ th 1 – d - Λt h 2 + d) =
= (h1 - h2) (∆t C(∆ h1) - Λ u 1 - ∆t C(∆ h2) +Λ u 2) + (u 1 - u2) (Λ th 1 – Λt h2 ) ≤ 0
Simplificando, tem-se
(∆ h1 - ∆ h 2) t (C(∆ h 1) - C(∆ h 2) ≤ 0 , ou
(f 1 – f 2 ) (C(f 1) – C( f 2)) ≤ 0.
Como C é estritamente monótona, então
(f 1 – f 2 ) (C(f 1) – C( f 2)) = 0., daqui f 1 = f 2 .
(5.60)
A unicidade do fluxo f implica que o tempo de viagem C a (f) sobre cada arco a
também é único, isto é equivalente a que o tempo generalizado de viagem em rota
Gp(h) , também é único para cada rota e cada par O/D i.
Como d > 0 e ∑ hp = d , então hp > 0, para algum p∈Pi e cada par i O/D .
p∈Pi
Logo Gp(h) = ui . Obtendo-se, deste modo que o vetor u é único
.
70
5.6.2 Propriedade de Monotonia estrita da função do tipo BPR
Nesta seção apresenta-se a prova da propriedade de que a aplicação C do tipo BPR, é
estritamente monótona. Este fato dará mais uma garantia da unicidade da solução à DV
definida sobre um conjunto X que não necessariamente é um cone.
Proposição 5.14 Seja X ⊂ Rm um conjunto compacto e convexo. Se F:X → Rm é
uma aplicação estritamente monótona. Então, a solução x*∈X da desigualdade
variacional
〈 F(x*), x -x*〉 ≥ 0 , ∀ x∈X,
é única.
Prova. Ver Teorema 1.6 Auslender, (1976).
Proposição 5.15 Uma aplicação do tipo BPR da forma
C = [Ci (fi , s-i)=τ i(1+ δ( fi /s-i ) β)] mi =1 ,
definida em Ω⊂ Rm sub-conjunto compacto e convexo, é estritamente monótona em
relação à variável f, isto é, verifica
〈 C(f,s - ) – C(h,s - ), ( f – h)〉 > 0, ∀ f ≠ h em Ω,
onde s- é o vetor das capacidades.
Prova
Como C(f,s - ) = (τ1 (1+ δ( f1 /s-1 ) β),. . ., τ m(1+ δ( fm /s-m ) β)),
C(h,s - ) = (τ1 (1+ δ( h1 /s-1 ) β),. . ., τ m(1+ δ( hm /s-m ) β)), então
〈C(f,s - ) - C(h,s - ), (f – h)〉 = 〈[ (τ1 (1+ δ( f1 /s-1 ) β), . . ., τ m(1+ δ( fm /s-m ) β)) -
(τ1 (1+ δ( h1 /s-1 ) β),. . ., τ m(1+ δ( hm /s-m ) β))], (f1 –h1 ,..., fm –hm)〉
= ∑mi = 1 (δ τ i /s- β i )( f βi – h βi )( f i – h i ).
(5.61)
71
Deve-se provar que ( f βi – h βi )( f i – h i )> 0.
Desde que ( f βi – h βi )= ( f i – h i ) ( f β -1i + f β -2i h i + ... + f i h β -2i + h β -1i )
De (5.68), 〈 C(f,s - ) – C(h,s - ), ( f – h)〉 =
= ∑mi = 1 (δ τ i /s- β i ) ( f β -1i + f β -2i h i + ... + f i h β -2i + h β -1i )( f i – h i )2
e ∑mi = 1 (δ τ i /s- β i ) ( f β -1i + f β -2i h i + ... + f i h β -2i + h β -1i )( f i – h i )2 > 0.
Portanto a função
C do tipo BPR é estritamente monótona. Em conseqüência,
aplicando a proposição 5.14, existe um único ponto de equilíbrio para a DV.
5.7 Exemplos de Problemas de Tráfego
A seguir apresentam-se os exemplos. No caso do problema de equilíbrio de tráfego o
método para resolvé-lo é o de minimização da função gap. O primeiro exemplo é para
um problema de ET onde não há interação dos fluxos de arcos, neste caso o problema
de ET é formulado via uma DV, sob as hipóteses de demanda fixa e a função de tempo
de viagem do tipo BPR. A comparação do número de iterações é feita em relação ao
exemplo que se encontra em Kriseida (1998).
Para todos os exemplos, o algoritmo foi rodado usando o aplicativo MATLAB versão
5.1, num micro computador Pentium II- 366 Mb de RAM.
5.7.1 Exemplo 1
A função do tipo BPR neste caso tem a forma
C i ( f i,s i) = τ i (1 + δ (f i / s i) β,
onde C i ( f i,s i) : é a função de tempo de viagem no arco i ,
τ i : é o tempo de viagem de fluxo livre ( corresponde a fluxo zero),
f i : é o fluxo no arco i ; δ : é uma constante chamada parâmetro da via, e β ∈ Z + .
72
A rede seguinte tem um par O/D, três arcos que conectam o par de O para D. A
demanda de O para D é de 10, os tempos de fluxo livre são 10, 20, 25 respectivamente,
e o vetor das capacidades s- é fixado em s- = (2, 4, 3).
A rede mostra-se na Figura 5.1seguinte:
C i (f1, s-1 )
C 2 (f2, s-2 )
Origem
O
Destino
D
C 3 (f3, s-3 )
Fig. 5.1 Rede com um só par O/D, três vias que a conectam e as funções de tempo
generalizado de viagem.
Pelos dados considerados, a função de tempo generalizado é a seguinte:
C(f, s- ) = (10(1 + (0.15/16) f14 ), 20(1 + (0.15/256) f24 ), 25(1 + (0.15/81) f34 )),
onde se assume δ =0.15, e β=4.
O conjunto Ω dos fluxos viáveis é um conjunto convexo e compacto, é o seguinte:
Ω = { f∈R3 / f1 + f2 + f3 = 10, (f1, f2 , f3 ) ≥ 0 , f ≠ 0 }.
O problema da desigualdade variacional a resolver é: determinar um fluxo f*∈Ω , tal
que se cumpra
(DV):
10(1 + (0.15/16) f*14 )(g1 –f *1)
+ 20(1 + (0.15/256) f*24 ) (g2 –f*2)
+ 25(1 + (0.15/81) f*34 )(g3 –f*3) ≥ 0 ,
∀ g∈Ω
73
A função gap associada à DV, é
gaps − ( f ) = max{10(1 +
g∈Ω
0.15 4
0.15 4
0.15 4
f1 )( f1 − g1 ) + 20(1 +
f 2 )( f 2 − g 2 ) + 25(1 +
f3 )( f3 − g3 )
16
256
81
Encontrar o fluxo f* tal que gaps − ( f ) =0, é equivalente a resolver o problema seguinte:
(G)
min gaps− ( f )
f∈Ω
Isto equivale a resolver o problema conhecido como problema semi-infinito
min α
(P)
( f , α )∈ R 4
s. a . o fluxo f∈Ω satisfaz
(10(1+(0.15/16)f14)(f1-g1)+20(1+(0.15/256)f24)(f2 –g2)+
25(1+(0.15/81)f34)(f3 –g3)) ≤ α ,
∀g∈Ω
A solução do problema P pode ser aproximada iterativamente, resolvendo problemas
de programação Pk não lineares, com k restrições
(Pk )
min α
( f ,α )∈ R 4
s. a . o fluxo f∈Ω satisfaz
(10(1+(0.15 /16)f14)(f1 -g i1 )
+20(1+(0.15 / 256)f24)(f2 –g i2)
+25(1+(0.15 / 81)f34)(f3 –g i3)) ≤ α ,
i=1,...,k.
5.7.2 Resultados computacionais para o exemplo 1
Escolheu-se um vetor inicial de fluxos f=(2.5, 3. 5, 4.), um valor αo=2, e g1∈Ω , como
sendo o fluxo g1 = (1.0, 6.0, 3.0). O valor limite para α próximo de zero, se considerou
igual a 10 -3, e se observou que na primeira iteração, esse valor foi atingido.
74
A tabela 1 a seguir, resume os resultados comparativos do método da Minimização da
Função Gap (F-Gap), em relação aos métodos Médias Sucessivas (MS), Aproximação
Linear (AL), Frank e Wolfe (F-W), em quanto aos fluxos de equilíbrio, tempos
generalizados de viagem, e número de iterações obtidos por esses diferentes métodos.
Observar a rapidez do método de minimização da função gap (G-Gap).
Método
Fluxo de equilíbrio
Empregado
Tempo generalizados
No. De
de viagem
Iterações
M-S
f*MS =(3.61, 4.65, 1.74)
(25.92, 25.48, 25.42)
45
A-L
f*AL =(3.59, 4.66, 1.75)
(25.57, 25.53, 25.43)
15
F-W
f*FW =(3.59, 4.70, 1.71)
(25.60, 25.70, 25.40)
5
F-Gap
f*FG =(3.58, 4.65, 1.77)
(25.40, 25.48, 25.45)
3
Tabela 1 Fluxos de equilíbrio, custos e número de iterações dos diferentes métodos
5.7.3 Exemplo 2
O seguinte exemplo do problema de equilíbrio encontra-se em Dafermos, (1980),
considera o caso de interação dos fluxos de arcos. A demanda de viagem é fixa, na
origem A é de 210 e em B de 120, a função de tempo de viagem é
C(f)=(10f1 +5f4 +1000, 15f2+5f5+950, 20f3+3000, 20f4+2f1+1000, 25f5+f2+1300).
A rede tem um par O/D, duas faixas de sentidos opostos e uma de um sentido só, como
se mostra na Figura 5.2
75
C4(f4, f1 )
C1(f1, f4 )
C5(f5, f2 )
A
B
C2(f2, f5 )
C3(f3 )
Fig. 5.2 Rede de tráfego com interação de fluxos em dois vias
Neste exemplo a função C(f) tem Jacobiana não simétrica e é fortemente monótona. Os
fluxos devem cumprir f1 +f2 +f3 = 210 , e f4 +f5 = 120, fi ≥ 0, i=1,...,5. A tabela 2 fornece
os resultados comparativos do método da minimização da função gap em relação ao
método de Dafermos, (1980).
Método
f*1
f*2
f*3
f*4
f*5
DAF
Fluxo
120.00
90.00
0.00
70.00
50.00
10 Iter.
Custo
2550.00
2550.00
3000.00
2640.00
2640.00
F-Gap
Fluxo
119.9999
4 Iter.
Custo 2549.9999
90.0000
2550.00
0.0001
70.0000
3000.0002
2639.9998
50.0000
2640.00
Tabela 2 Fluxos, custos e iterações no caso de interação de fluxos.
5.7.4 Exemplo 3
O seguinte exemplo é inédito, pode-se considerar uma extensão do exemplo 2, onde se
considera que todas as vias apresentam interação de fluxos em arcos. Neste caso a
função de custo de viagem considerada é a seguinte:
76
C(f) =(10f 1 + 5f 4 +1000;15 f 2 + 5 f 5 + 850;20f 3 + 8f 6 + 3000;
20f 4 + 2f 1 + 2000;25f 5 + f 2 + 2300;10f 6 + 5f 3 + 800).
A demanda de viagem é d AB = 350 e d BA = 300. A rede se mostra na Figura 5.3.
C4(f4, f1 )
C1(f1, f4 )
C5(f5, f2 )
A
B
C2(f2, f5 )
C6 (f6, f3)
C3(f3 )
Fig. 5.3 Rede de tráfego com interação de fluxos nas três vias
5.7.4.1 Iterações
Para rodar o programa o fluxo inicial se escolheu como o vetor
f = [ 90 180
g1 = [100
80 110
100
150
90 100], o valor de α igual a 2, e
80
90
130] . Para o teste de parada se escolheu uma
tolerância de ε = 0.00001 e se comparou com a expressão
utilizou a relação αk - gap(f k) ≤ ε .
Iteração 1
αk - gap(f k) , isto é se
77
Solução do problema P1 . Primeiro candidato a fluxo de equilíbrio
f 1 = [ 90.0 180.0 80.0 110.0 90.0 100.0], α1 = 0.0001.
Cálculo do gap (f 1) = max { 〈 C(f 1), f 1 - g〉 , g∈Ω }. Obtêm-se
g 2 = [349.9998
0.0001
0.0001
0.0001
0.0001 299.9998].
Avaliação da função gap(f 1)
gap(f 1) = 9.8250e+005
Teste de viabilidade. Conferir se
gap(f 1) ≤ α1 .
No caso, verificar se α1 - gap(f 1) = -9.8250e+005 ≤ ε = 0.00001. CONTINUAR.
Iteração 2
Solução do problema P2 que tem uma restrição a mais que P1 .
f 2 =[214.2709 114.6906 21.0385 75.4478 14.7348 209.8174], α2 = 0.0001.
Cálculo do gap (f 2) = max { 〈 C(f 2), f 2 - g〉 , g∈Ω }. Obtêm-se
g 3 = [0.0001 349.9998
0.0001
0.0001 299.9998
0.0001]
2
Avaliação da função gap(f )
gap(f 2) = 3.7266e+005
Teste de viabilidade. Conferir se
gap(f 2) ≤ α2 .
No caso, verificar se α2 - gap(f 2) = -3.7266e+005 ≤ ε = 0.00001. CONTINUAR.
Iteração 3
Solução do problema P3 que tem duas restrições a mais que P1 .
f 3 = [216.8460 129.0742
4.0798 53.1005 39.5791 207.3205], α3 = 0.0001.
Cálculo do gap (f 3) = max { 〈 C(f 3), f 3 - g〉 , g∈Ω }. Obtêm-se
g 4 = [0.0001 349.9998
0.0001
0.0001 0.0001 299.9998].
Avaliação da função gap(f 3)
gap(f 3) = 1.5748e+005
Teste de viabilidade. Conferir se
gap(f 3) ≤ α3 .
78
No caso, verificar se α3 - gap(f 3) = -1.5748e+005 ≤ ε = 0.00001. CONTINUAR.
Iteração 4
Solução do problema P4 que tem três restrições a mais que P1 .
f 4 = [ 203.1848 146.8151
0.0001 34.5554 30.4795 234.9651], α4 = 0.0001.
Cálculo do gap (f 4) = max { 〈 C(f 4), f 4 - g〉 , g∈Ω }. Obtêm-se
g 5 = [0.0001 349.9998
0.0001 299.9998
0.0001
0.0001].
Avaliação da função gap(f 4)
gap(f 4) = 1.5652e+004
Teste de viabilidade. Conferir se
gap(f 4) ≤ α4 .
No caso, verificar se α4 - gap(f 4) = -1.5652e+004 ≤ ε = 0.00001. CONTINUAR.
Iteração 5
Solução do problema P5 que tem quatro restrições a mais que P1 .
f 5 = [ 202.1644 147.8355 0.0001 37.1862 28.0087 234.8052], α5 = 0.0001
Cálculo do gap (f 5) = max { 〈 C(f 5), f 5 - g〉 , g∈Ω }. Obtêm-se
g 6 = [0.0001 349.9998 0.0001 0.0001 0.0001 299.9998].
Avaliação da função gap(f 5)
gap(f 5) = 9.0140e-005
Teste de viabilidade. Conferir se
gap(f 5) ≤ α5 .
No caso, ver se α5 - gap(f 5) = 9.8596e-006 ≤ ε = 0.00001. PARAR, o vetor f 5 é o
fluxo de equilíbrio ótimo do usuário. Assim,
f * = f 5 = [ 202.1644 147.8355 0.0001 37.1862 28.0087 234.8052].
Os custos unitários de viagens nos arcos são:
Custo = 1.0e+003 * [ 3.2076, 3.2076, 4.8784, 3.1481, 3.1481, 3.1481].
79
A Tabela 3 seguinte resume os resultados obtidos para este exemplo. Os valores
iniciais considerados foram: fluxo=(90, 180, 80, 110, 90, 100); α = 2; ε = 0.00001;
g 1 = (100, 100, 150, 80, 90, 130).
Iter.
1
Fluxos
fk
g k+1
90
349.9998
180
0.0001
80
0.0001
110
0.0001
90
0.0001
100
2
αk
gap (f k )
α k - gap (f k )
0.0001
982500
982500
0.0001
372660
372660
0.0001
157480
157480
0.0001
15652
15652
299.9998
214.2709
0.0001
114.6906
349.9998
21.385
0.0001
75.4478
0.0001
14.7348 294.9998
3
209.8174
0.0001
216.8460
0.0001
129.742
349.9998
4.0798
0.0001
53.1005
0.0001
39.5791
0.0001
207.3205 299.9998
4
203.1848
0.0001
146.8151
349.9998
0.0001
34.5554
0.0001
299.9998
80
30.4795
0.0001
23.9651
0.0001
Iter. Fluxos
fk
5
g k+1
αk
gap (f k )
α k - gap (f k )
202.1644
0.0001
0.0001
0.000009
0.000009
147.8355
349.9998
0.0001
0.0001
37.1862
0.0001
28.0087
0.0001
234.8052
299.9998
Como cumpre-se:
0.000009 < 0.00001
PARAR.
Fluxo de equilíbrio
f*
Custo de
202.1644
Equilíbrio: C
147.8355
3207.6
0.0001
3207.6
37.1862
4878.4
28.0087
3148.1
234.8052
3148.1
3148.1
Tabela 3. Fluxos, custos de equilíbrio e valores da função gap
81
5.7.5 Exemplos para o problema de PRT formulado como um Programa
Matemático de Dois Níveis Generalizado (PDNG)
Nos exemplos a seguir, na fase de equilíbrio, para a solução do problema de encontrar
o fluxo ótimo do usuário (solução da DV) utiliza-se o método da minimização da função
gap.
Observação 5.16 Seja (f -,s -) solução do problema
min T ( f , s )
( f , s )≥0
(f,s)∈Ω x Ω,
e (f*,s*) solução do problema de dois níveis PRT, onde T(f,s) é a função objetivo do
administrador e Ω é o conjunto viável dos fluxos e capacidades. Então, se cumpre que
T(f -,s -) ≤ T(f*,s*) ≤ T(f(s -),s -), Marcotte, (1984).
O resultado acima permite escolher previamente um valor da função objetivo do
administrador, o T(f,s), o qual, nos exemplos será usado como critério para obter uma
solução do problema PRT, isto é, uma solução que satisfaz tanto aos usuários como ao
administrador. No exemplo 4 seguinte, se escolheu o valor V=540, que encontra-se
entre os valores inferior (470.3205) e superior (14 195.00) de T(f,s). Assim, quando na
iteração k tem-se T(f k,s k) ≤ V, o ponto (f k,s k) será uma solução do problema PRT.
Mais detalhes sobre o cálculo dos valores inferior e superior de T(f,s) serão
apresentados no exemplo 5.
Exemplo 4
A seguir propomos o seguinte exemplo. Este refere-se a um problema de Projeto de
Redes de Tráfego (PRT). Nele, considera-se uma rede que tem dois pares O/D: O1-D1;
82
O1-D2, com demandas dO1
D1
= 20 e dO1
D2
= 15 , em veículos por minutos. As
variáveis de decisão são o fluxo e a capacidade. A rede mostra-se na Figura 5.4
seguinte:
a2
D1
a1
a3
O1
a4
a5
a6
a8
a7
D2
a9
Fig. 5.4 Rede de tráfego com dois pares O/D, cinco rotas e nove arcos.
As rotas O/D são: O1-D1;
r1: a1 , a2
r2: a1 , a3 , a4
O1-D2;
r3: a5 , a6
r4: a6 , a7 , a8
r5 : a7 , a9 .
83
Os tempos de fluxos livre estão dados no vetor ϒ =(10, 12, 18, 8, 15). Para começar a
execução do algoritmo de P-A , na fase de equilíbrio, o Líder fixa o vetor das
capacidades em rotas como o vetor s0 =[15, 5, 12, 2, 1] , se escolhe α0=2, e
g1=[7, 13, 4, 7, 4]. A função C(f,s) de tempos generalizados de viagens em rotas é de
tipo BPR, onde o custo sobre cada rota depende apenas do fluxo e da capacidade da
própria rota, a função é

f 4 
C ( f i , s i ) =  p i (1 + 0.15 4i ) 
, e a função que representa custos de investimentos
s i  i =1,...,5

se definiu como
q(s) = s1 + s2 + s3 + s4 + s5 . Aqui, deve-se ter presente que para obter o custo real de
investimento, após ter obtido o vetor S, se deve empregar um fator de conversão para a
correspondente unidade monetária.
Na fase de equilíbrio (solução da desigualdade variacional pelo método da minimização
da função gap) considerou-se uma tolerância de ε = 0.01.
Primeira iteração do algoritmo de P-A
Fase de Equilíbrio. Após quatro iterações encontrou-se o fluxo de equilíbrio ótimo do
usuário
f
1
* = [16.7382
3.2618
10.2970
3.5161
1.1868 ] , e os custos de viagem no
equilíbrio como o vetor Custo=[12.3257 12.3260 19.4638 19.4638 19.4638].
Fase do Líder. Minimização da Função do Líder. Com f
1
* fixo encontra-se o vetor
solução das novas capacidades
s1 = [16.6374 3.3626 10.7030 3.1076 1.1894].
O valor da função do líder (L) no ponto viável (f 1 *, s0) é LD = 573.4727.
Como LD>V . Continuar.
84
Segunda iteração do algoritmo de P-A
Com s0 = s1 , repetimos a fase de equilíbrio. Após quatro iterações encontrou-se o
fluxo de equilíbrio ótimo do usuário
f
2
* = [18.1990 1.8010 8.2310 5.4004 1.3686] , e os custos de viagem no equilíbrio
como o vetor Custo=[12.1476 12.1481 18.9444 18.9444 18.9444].
Fase do Líder. Minimização da Função do Líder. Com f
2
* fixo encontra-se o vetor
solução das novas capacidades
s 2 = [18.1384
1.8616
8.7301
4.8703 1.3996].
O valor da função do líder (L) no ponto viável (f 2 *, s1) é LD = 562.1178.
Como LD>V . Continuar.
Terceira iteração do algoritmo de P-A
Com s0 = s2 , repetimos a fase de equilíbrio. Após quatro iterações encontrou-se o
fluxo de equilíbrio ótimo do usuário
f
3
* = [ 19.5075
0.4925
5.1175
8.3401
1.5424], e os custos de viagem no
equilíbrio como o vetor Custo=[12.0068 12.0088 18.3188 18.3188 18.3188].
Fase do Líder. Minimização da Função do Líder. Com f
3
* fixo encontra-se o vetor
solução das novas capacidades
s 3 = [19.4896
0.5104
5.6047
7.7665
1.6288].
O valor da função do líder (L) no ponto viável (f 3 *, s2) é LD = 549.9188.Como LD>V .
Continuar.
Quarta iteração do algoritmo de P-A
Com s0 = s3 , repetimos a fase de equilíbrio. Após três iterações encontrou-se o fluxo
de equilíbrio ótimo do usuário
85
f
4
* = [19.9990
0.0010
0.0619
13.1902
1.7479], e os custos de viagem no
equilíbrio como o vetor Custo=[11.6631 12.0000 18.0000 17.9836 17.9836].
Fase do Líder. Minimização da Função do Líder. Com f
4
* fixo encontra-se o vetor
solução das novas capacidades
s 4 = [19.9990
0.0010
0.07507
12.3878
1.8614].
4
O valor da função do líder (L) no ponto viável (f , s3) é LD = 538.0164.
Como LD < V, este é um
valor que satisfaz o interesse do administrador, em
conseqüência a solução correspondente do problema projeto de redes de tráfego (PRT)
é o par (f *,s *) = (f 4 *, s4).
A seguir, pela formula (fluxo em arcos) = (matriz arco/rota)x(fluxo em rota), obtêm-se o
vetor de fluxos de equilíbrio em arcos, seguinte:
u*=[20.0000, 19.9957, 0.0043, 0.0043, 0.0011, 8.7868, 14.9989, 8.7857, 6.2132].
Observação 5.17 Nas iterações, para cada vetor de capacidade s fixo, o algoritmo
encontra rapidamente o fluxo de equilíbrio f, e fornece os custos de viagens
correspondentes. Os resultados são apresentados na Tabela 4.
Dados iniciais: capacidade s o = (15, 5, 12, 2, 1); αo = 2; ε = 0.01 ; g1=(7, 13, 4, 7, 4);
escolheu-se o valor comparativo V = 540. A função de tempo de viagem foi de tipo
BPR.
Iter. Equilíbrio
fk
1
Custos
C(k)
Líder (capac.)
sk
16.7382
12.3257
16.6374
3.2618
12.3260
3.3626
10.2970
19.4638
10.7030
3.5161
19.4638
3.1076
T(f k , sk-1)
573.4727
86
1.1868
Iter. Equilíbrio
fk
2
3
4
19.4638
Custos
C(k)
1.1894
Líder (capac.)
sk
18.1990
12.1476
18.1384
1.8010
12.1481
1.8616
8.2310
18.9444
8.7301
5.4004
18.9444
4.8703
1.3686
18.9444
1.3996
19.5075
12.0068
19.4896
0.4925
12.0068
0.5104
5.1175
18.3188
5.6047
8.3401
18.3168
7.7665
1.5424
18.3168
1.6288
19.9990
11.9661
0.0010
12.0000
0.0010
0.0619
18.0000
0.0750
13.0902
18.0000
12.3878
1.7479
18.0000
1.8614
19.999
T(f k , sk-1)
562.1178
549.9188
538.0164
Como cumpre-se:
538.0164 < V.
PARAR.
Fluxo de equilíbrio Custos de equilíbrio
f*
Custos
Capacidades
Valor ótimo do
Ótimas: s*
Administrador
T(f*, s*)
19.9990
11.9661
19.999
87
0.0010
12.0000
0.0010
0.0619
18.0000
0.0750
13.0902
18.0000
12.3878
1.7479
18.0000
1.8614
538.0164
Tabela 4. Solução do problema PRT com função de custo de tipo BPR
Exemplo 5
Lembrar que da Observação 5.15, no ponto solução (f*,s*) do problema PRT se cumpre
T(f -,s -) ≤ T(f*,s*) ≤ T(f(s -),s -). No cálculo do valor inferior, obteve-se como resultado o
vetor de fluxo f - =(0.0236, 73.0288, 6.9476, 49.9990, 0.0010) e o vetor de capacidades
s -=(1.0592, 75.6909, 5.2499, 51.8377, 0.1623), correspondendo o valor
T(f -,s -)=5 319.90. No cálculo do valor superior, considerou-se a capacidade s – achada
e resolveu-se o problema de equilíbrio para encontrar o fluxo f(s -) associado. Obtevese f(s -) = (2.6356, 66,8446, 10.5198, 49.6681, 0.3319), o valor correspondente foi
T(f(s -),s -)=21 157. Portanto, escolheu-se V=8000.
Em geral, é possível que o valor T(f*, s*) seja igual ao valor superior T(f -,s -). Por isto,
para fazer com que o critério de parada
T(f k,s k) ≤ V na iteração k seja cumprida,
pode-se escolher o valor de V igual ou suficientemente próximo do valor superior.
Neste exemplo que propomos, as demandas de viagem são d
AB
=80 e d
AB
=50, e se
considera a seguinte função de custo generalizado de viagem, a qual tem Jacobiana
não simétrica:
C = [ p 1(1 +
f12
s 12
+2
f 42
s 42
), p 2 (1 + 3
p 4 (1 + 3
f 42
s 42
+5
f 22
s 22
f 12
s 12
+
f 52
s 52
), p 3 (1 +
), p 5 (1 + 4
f 52
s 52
f 32
s 32
+
),
f 22
s 22
)].
88
A rede para o exemplo é a seguinte:
via 1
C4
via 2
C1
A
C5
B
C2
via 3
C3
Fig. 5.5 Par origem-destino conectados por três vias, duas das quais são de mão dupla
Como se pode observar, a função de custo generalizado de viagem expressa o fato da
rede ter duas vias de mão dupla, pelo que a interação dos fluxos nessas vias deve ser
modelado através das funções de custo de viagem tanto da origem A em direção ao
destino B como de B para A. Por exemplo, na via 1, o custo de viagem expressa a
interação dos fluxos 1 e 4, e na via 2 se expressa a interação dos fluxos 2 e 5.
Neste exemplo, como no caso do exemplo 4, se escolheu V=8000 como o valor da
função objetivo do líder que satisfaz o interesse do administrador.
89
Os tempos de fluxo livre estão dados no vetor τ = (10, 12, 18, 8, 15), a capacidade
inicial s0 = (23, 38, 19, 14, 36), g 1= (27, 38, 15, 20, 30), e α0 = 2. A função dos custos
de investimentos é I(s)= s1 + s2 + s3 + s4 + s5 , e na fase de equilíbrio a tolerância é de
ε = 0.01.
Primeira iteração
Fase de Equilíbrio.
Após seis iterações o fluxo de equilíbrio ótimo do usuário
1
encontrado é f * = [17.7199 35.8292 26.4509 19.0292 30.9708], e os custos de
viagem em rotas o vetor Custo=[52.8857 52.8857 52.8857 76.0826 72.7421].
Fase do Líder. Minimização da função do administrador. Com f 1* fixo encontra-se o
vetor solução das novas capacidades, o qual resulta o vetor
s
1
=[20.2120
39.1437
20.6443
25.5238
24.4762],
e o valor da função do
administrador avaliado no ponto viável (f 1*, s0) é lid=T(f 1*, s0) = 8061.5 > V. Continuar.
Segunda iteração
Fase de Equilíbrio.
Com s0 = s
1
fixo repetimos a fase de equilíbrio. Após cinco
iterações o fluxo de equilíbrio ótimo do usuário encontrado é
f 2* = [30.3654 24.5717 25.0630 19.7374 30.2626], e os custos de viagem em rotas o
vetor Custo=[44.5300 44.5301 44.5300 112.6330 112.6330].
Fase do Líder. Minimização da função do administrador. Com f 2* fixo encontra-se o
vetor solução das novas capacidades, o qual resulta o vetor
s2 =[21.1381 22.3068 36.5551 41.6680 8.3320], e o valor da função do administrador
avaliado no ponto viável (f 2*, s1) é lid=T(f 2*, s1) = 9324.1 > V. Continuar.
Terceira iteração
90
Fase de Equilíbrio.
Com s0 = s
2
fixo repetimos a fase de equilíbrio. Após cinco
iterações o fluxo de equilíbrio ótimo do usuário encontrado é:
f 3* = [22.2014 16.0707 41.7279 42.1068 7.8932], e os custos de viagem em rotas o
vetor Custo=[41.4547 41.4548 41.4547 76.6334 76.6334].
Fase do Líder. Minimização da função do administrador. Com f 2* fixo encontra-se o
vetor solução das novas capacidades, o qual resulta o vetor
S3 =[27.2898
22.2405
30.4697
39.4328
3
10.5672],
e o valor da função do
2
administrador avaliado no ponto viável (f *, s ) é lid=T(f 3*, s2) = 7280. Como se
cumpre T(f 3*, s2) = 7280 < 8000, o par (f 3*, s2) é uma solução do problema PRT.
Os resultados apresentam-se na Tabela 5, seguinte:
Dados iniciais: so = (23, 38, 19, 14, 36); αo = 2 ; ε = 0.01 ; g1=(27, 38, 15, 20, 30), e o
valor comparativo V=8000. A função de custo de viagem é não simétrica.
Iter.
Equilíbrio
f
k
Custos
Líder
Valor da função
C(k)
(capacidade)
Administrador:
k
s
1
2
3
17.7199
52.8857
20.2120
35.8292
52.8857
39.1437
26.4509
52.8857
20.6443
19.0292
76.0826
25.5238
30.9708
72.7421
24.4762
30.3654
44.5300
21.1381
24.5717
44.5301
22.3068
25.0630
44.5300
36.5551
19.7374
112.6330
41.6680
30.2626
112.6330
8.3320
22.2014
41.4547
27.2898
16.0707
41.4548
22.24.2405
T(f k, s k -1)
8061.5
9324.1
7280
91
41.7279
41.4547
30.4697
42.1068
76.6334
39.4328
7.8932
76.6334
10.5672
Custo de
Capacidades
Valor ótimo do
equilíbrio
ótimas
administrador
7280 < V. Parar
Fluxo f*
Tabela 5. Solução do problema Projeto de Redes de Tráfego (PRT) com função de
custo de viagem não simétrico (uso da função gap primal)
Observação 5.18 Nas iterações, para cada vetor de capacidade s fixo, o algoritmo
encontra rapidamente o fluxo de equilíbrio f, e os custos de viagens correspondentes
são obtidos. Por outro lado, se observa que os vetores s das capacidades, tem um
comportamento mais irregular, o qual foi notado quando se tento utilizar como critério
de parada do algoritmo P-A na fase do líder, a proximidade destes vetores.
Exemplo 6
Neste exemplo, para encontrar fluxos e capacidades ótimas, e os custos de equilíbrio
usa-se o método de penalidades. Considera-se uma rede com interação de fluxos em
vias de mão dupla. As demandas de viagem são dAB =80 e dB A=50, o parâmetro de
penalidade µ = 200, o vetor de tempos de fluxo livre
p=[16, 25, 18, 8, 11], o
parâmetro de tolerância ε = 0.0015, e a função de custos generalizados de viagem
seguinte:
C = [ p 1(1 +
f12
s 12
+
f 42
s 42
), p 2 (1 + 4
p 4 (1 + 3
f 42
s 42
f 22
s 22
+5
+
f 12
s 12
f 52
s 52
), p 3 (1 +
), p 5 (1 + 4
f 52
s 52
f 32
s 32
+
),
f 22
s 22
)].
92
Após cinco iterações obteve-se os seguintes resultados:
Custos de Equilíbrio: 19.1527 26.1801 19.1527 12.7300 12.7300
Fluxos de equilíbrio: 0.001 0.001 79.998 49.9989 0.0011
Capacidades ótimas: 0.1295 0.0187 316.1180 112.6532 0.0056
Valor da função objetivo do Líder: T=2 597.7
Estes valores foram atingidos com o valor da função gap de: gap=0.0006022, e o valor
de: α = 0.0018. A Tabela 6 apresenta os resultados do exemplo 6.
Valores iniciais: g 1 = (27, 38, 15, 20, 30); µ = 200; ε = 0.0015 ; α o = 2.
C(k)
T(f k, s k)
αk
g( f k ,s k)
Difer.
1 79.91221
17.5608
3522.6
2x10-6
0.4516
0.4516
0.0010
25.3207
0.0869
18.9219
0.9603
11.8976
49.0397
11.5487
2509.1
1x10-8
195.1054
195.1054
k
( f k , s k)
256.2207
0.1026
0.3841
57.8796
439.5631
2
0.0010
17.212
0.0010
36.9894
79.9980
19.651
49.9990
9.8187
0.0010
26.6641
93
0.1587
0.0047
264.1484
181.7087
0.0017
3
0.0010
17.2115
0.0010
28.5163
79.9980
19.6509
49.9990
9.8175
0.0010
13.7205
2509.2
3x10-7
195.1448
195.1448
0.3372
0.0059
264.1492
181.7094
0.0043
k
( f k , s k)
C(k)
T(f k, s k)
αk
g( f k ,s k)
Difer.
4
0.0010
19.1527
2597.7
0.0018
0.0033
0.0014
0.0010
26.1462
79.9974
19.1527
49.9990
12.7300
0.0010
12.7300
0.1294
0.0322
316.1200
112.6500
0.0051
94
5
0.0010
19.1527
0.0010
26.1801
79.9980
19.1527
49.9980
12.7300
0.0011
12.7300
2597.7
0.0018
0.0006
0.0012
0.1295
0.0187
316.1180
112.6532
0.0056
(f * ,s*)
c*
T(f*,s*)
Tabela 6. Solução do problema PRT pelo algoritmo de Penalidades (gap dual)
CAPÍTULO 6
Conclusões
O problema de projeto de redes de tráfego (PRT) contínuo considerado na tese é
reconhecido como um dos problemas mais difíceis segundo Meng et al., (2000), e
constitui um desafio para os profissionais da engenharia de transporte. A principal
95
dificuldade decorre da formulação utilizada como um modelo de programação de dois
níveis, considerado por sua complexidade computacional um problema NP-difícil. Este
modelo é em geral, um problema de programação não convexo e não diferenciável por
esta a razão, somente se garante soluções locais sob hipóteses de continuidade
diferenciabilidade das funções envolvidas.
Na tese, se formulou o problema PRT como um problema de programação
matemática de dois níveis generalizado. Este modelo adotado para o problema PRT
considerou-se uma boa opção para descrever tanto a característica hierárquica do
problema quanto uma representação mais geral do fenômeno de equilíbrio de tráfego.
Assim tem-se, no segundo nível uma desigualdade variacional (DV) modelando o
problema de equilíbrio ótimo do usuário (caráter determinístico) e no primeiro nível
representando os interesses do administrador da rede. Para resolver a (DV) foi
adaptado um algoritmo baseado na técnica de planos de corte, (Arica et al., 1996 e
1997) para o caso do problema de equilíbrio de tráfego. Esta técnica se usa com
conceito de função gap dual associada à desigualdade variacional. A função gap
estende o conhecido conceito da Programação Linear que fornece a diferencia entre o
valor ótimo e o valor aproximado de um problema de PL. A função gap dual (gap primal)
se define como a função valor de uma família de problemas de programação linear (não
linear) com restrições.
Associada à DV considerou-se uma aplicação de custo generalizado de viagem
estritamente monótona (ou fortemente monótona) inspirado na função de tipo BPR.
Com esta hipótese foi possível obter em cada iteração soluções únicas da DV (os fluxos
ótimos do usuário). Baseados na informação do fluxo ótimo, um dos algoritmos
desenvolvidos chamado de Projeto-Alocação, simplifica a tomada de decisão do
administrador, pois apenas terá de minimizar sua função de custos com uma única
variável de decisão, o vetor de capacidade, deixando fixo o vetor dos fluxos. Os
resultados numéricos obtidos de fluxos de equilíbrio nos diferentes testes realizados,
para resolver a (DV), mostraram-se coerentes em relação ao Principio de Equilíbrio de
Wardrop, isto é, que no estado de equilíbrio de tráfego, as rotas mais caras não levam
fluxo.
96
Formulou-se e Implementou-se em Matlab, sem dificuldades, dois algoritmos que
aproximam soluções ao problema PRT: o algoritmo de Projeto-Alocação e um algoritmo
de Penalidade. Para o primeiro algoritmo é necessário estimar o valor da função
objetivo do administrador (isto é, a quantidade orçamental para investir na melhoria da
rede), que é usado como referência no teste no parada. Este valor encontra-se
garantido, pois sempre será possível achar um limite inferior e um limite superior do
valor da função objetivo, dependente das restrições do modelo, Marcotte (1981).
Nos exemplos testados tanto para o problema de equilíbrio, como para o
problema de Projeto de Redes de Tráfego, foram consideradas funções de custo de
viagem generalizado, que modelam o caso de uma rede com interação de fluxos, isto é,
uma situação onde a rede tem vias de mão dupla que é um caso real comum nas redes
urbanas.
No algoritmo de Penalidades, para resolver o problema PRT utilizou-se a função
gap dual. Neste algoritmo, não se fixa nenhum das variáveis (fluxo e capacidade) no
processo de solução, e como o algoritmo de Projeto-Alocação, tem natureza de planos
de corte. Ambos dos algoritmos mostraram-se rápidos em atingir as soluções. Em
quanto à complexidade, o problema de Projeto de Redes de Tráfego pertença ao tipo
de problemas classificados como de NP - difícil.
Outra das dificuldades em um problema PRT, vem de considerar no equilíbrio
uma aplicação que representa o custo generalizado de viagem para modelar a
interação de fluxos, sendo que a função objetiva do administrador, em geral é não
convexa. Embora, o método do algoritmo de P-A apresentado na tese é uma opção
para se aproximar a uma solução do problema, ainda nos casos assinalados, como foi
mostrado nos exemplos.
No problema de Projeto de Redes de Tráfego, a abordagem de Dois Níveis
Generalizado para o PRT
feita na tese, permite considerar o caso geral para o
problema de equilíbrio de tráfego, fornecendo uma solução que é de interesse tanto do
97
administrador como dos usuários. Neste contexto, a Tese aporta uma contribuição para
a abordagem destes problemas envolvendo situações bem próximas da vida real.
Propostas de Pesquisas Futuras
Como já foi assinalado, são muitos os problemas de transporte que no momento
preocupam aos pesquisadores na área do transporte. Estes problemas são complexos
na sua formulação e na abordagem da solução, alguns deles propomos como
pesquisas futuras ou continuação do presente trabalho.
Problema de Projeto de Redes de Tráfego contínuo estocástico, onde o
problema de equilíbrio considera no modelo uma função de probabilidade para a
escolha de rota e/ou modo de viagem.
Problema de Projeto de Redes de Tráfego discreto determinístico, onde o
problema do administrador considera a possibilidade de adicionar novas vias na rede.
Problema de Projeto de Redes de Tráfego com demanda elástica e efeitos de
congestionamento. Neste caso a função de custo generalizado de viagem terá
Jacobiana não simétrica e a função de demanda dependerá do custo mínimo de viagem
entre cada par origem-destino.
Algumas das propostas de trabalho acima assinalados, podem-se formular como
programas Matemáticos de Dois Níveis Generalizado. Isto permitiria, como no caso do
trabalho pesquisado, modelar fatos mais em concordância com a realidade.
98
Referências
Aashtiani H.Z. Magnanti, T., (1981). “Equilibria on a Congested Transportation
Network”, SIAM J. Algebraic Discrete Methods 2, 213-226.
99
Arica J., Morales G., Scheimberg S., (1996) “A Cutting Plane Algorithm to solve the
Generalized Variational Inequality Ploblem for convex constrain set”, No.
12/ 96,
LCENG/ CCT / UENF
Arica
J.,
Morales,
G.,
Scheimberg
S.,
(1997)
“Desigualdades
Variacionais
Generalizadas. Um Algoritmo de Planos de Corte”, XX CNMAC da Sociedade Brasileira
de Matemática Aplicada e Computacional, Gramado, 1997.
Asmuth R.L., (1978) “Traffic Network Equiluibria”, Ph.D. Thesis, Stanford University.
Auslender A., (1976) Optimisation: Méthodes Numériques, MASSON S.A.
120 Bd
Saint-Germain, Paris-6
Bard J. F., (1999) “Practical Bilevel Optimization: Algorithms and Applications”. Kluwer
Academic Publishers.
Bastos C. A., (1999), “Equilíbrio Geral Calculável: Um Algoritmo de Planos de Corte
para uma Formulação Variacional”, Tese de Mestrado, LEPROD/Universidade Estadual
do Norte Fluminense –RJ.
Bazaraa M.S., Sherali H.D., Shetly C.M., (1979), “Nonlinear Programming: Theory and
Algorithms”, John Wiley & Sons, Inc. , New York.
Beckmann, M.J., Mc Guire C.B., e Winsten C.B., (1956) “Studies in the Economics of
Transportation”, Yale University Press, New Haven.
Bell M.G. e Iida Y., (1997), Transportation Network Analysis , John Willey & Sons, New
York.
Bem-Ayed O., Boyce D. e Blair C., (1998), “A General Bilevel Linear Programming
Formulation of the Network Design Problem”, Transportation Research. B Vol. 22B, No.
4, pp. 311-318.
100
Chen M. E Alfa A.S., (1991), “A Network Design Algorithm using a Stochastic
Incremental Traffic Assignment Approach”, Transportation Science 25, pp 215 – 224.
Claude B. , (1994), “Topological Spaces”. Dover Publications, INC. Mineola, New York
Clarke F. H., (1983), “Optimization and Nonsmooth Analysis”. John Wiley & Sons, New
York.
Chiou S.-W., (1999), “Optimization of
Area Traffic Control for Equilibrium Network
Flows”. Transportation Science. Vol. 33, No .3.
Codina, E. e Barcelos, J., (1995), “A System Optimal Traffic Assignment Model wifh
Distributed
Parameters”.
Departamento
d’Estadística
i
Investigació
Operativa.
Universidad Politécnica de Catalunya, Spain.
Dafermos S. C., (1980) “Traffic Equilibrium and Variational Inequalities”, Transportation
Science, 14, 42-54.
Dantzig G. B. Wolfe D. (1961) “The Descomposition Algorithm for Linear Programs”,
Econometric, 29(4) pp. 767-778.
De Cea, J., Fernandez E., (1993), “Transit Assignment for Congested Public Transport
Systems: An Equilibrium Model”, Transportation Science, Vol. 27, No 2.
Fisk C., Boyce D., (1983), “Alternative Variational Inequality Formulations of the
Equilibrium Travel-choice Problem”, Transportation Science 17, 454-463.
Fisk, C., (1987), “On Combining Maximum Entropy Trip Matrix Estimation with User
Optimal Assignment”, Transportation Reserch, B Vol. 22B, No 1. pp. 69-79.
Florian, M. (1999), Untangling Traffic Congestion, ORMS.
101
Florian, M., Spiess, H., (1982) “The Convergence of Diagonalization Algorithms for
Network Equilibrium Problems”, Transportation Research, B 16B, 447 – 483.
Harker P. T., Pang J. S., (1990) ”Finite Dimensional Inequality and Nonlinear
Complementarity Problems:
A survey Of Theory, Algorithms and Applications”,
Mathematical Programming 48, pp. 161-220. North-Holland.
Jehiel P., (1993) “Equilibrium on a Traffic Corritor with Several Congested Modes”,
Transportation Science, Vol. 27, No 1.
Kosniowski A., (1992) “Topologia Algebraica”, Editorial Reverté, S. A.
Kriseida C., (1998) “Gerenciamento Dinâmico de Tráfego por Indução dos Fluxos de
Equilíbrio no caso da ocorrência de um Incidente”, Tese M.Sc. UFRJ- COPPE.
Larsson T., Patriksson M., (1994) “A class of gap function for variational inequalities”,
Matematical Programming 64, pp. 53-79.
Lemaréchal, C. e Hiriart-Urruty J.B. (1993), “Convex Analysis and Minimization
Algorithms II. Advanced Theory and Bundle Methods”,
Springer Verlag Berlin
Heidelberg
Lo H., (1999), “A Novel Traffic Signal Control Formulation”, Transportation Research
Part A 33, 433-448.
Lo H., Chen, A., (2000) Traffic Equilibrium Problem with route specific costs:
Formulation and Algorithms, Transportation Research, Part B 34, 494-513.
Lou Z-Q., Pang J-S, Ralph D., Wu S-Q., (1996) “Exact Penalization and Stationary
Condition of Mathematical Programs with Equilibrium Constraints”. Mathematical
Programming 75, pp. 19-76.
102
Makela M., Neittaanmaki P., (1992) “Nonsmooth optimization”, Published by Word
Scientific Publishing Co. Pte. Ltd.
Marcotte P., (1984) "Network Design Problem with Congestion Effects: A case of Bilevel
Programming", Matematical Programming 34, 142-162 North- Holland.
Marcotte P., Dussault J., (1989) “A Sequential Linear Programming Algorithm for Solving
Monotone Variational Inequalities”, SIAM J. Control and Optimization, Vol. 27, No 6,
1260-1278, November.
Migdalas A., (1995), “Bilevel Programming in Traffic Planning: Models, Methods and
Challenger”, Journal of Global Optimization, 7: 381-405.
Meng Q., Yang H., e Bell M., ( 2000) “An equivalent continuously differentiable model
And a locally convergent algorithm for the continuous network design problem”,
Transportation Research Part B: Methodological Volume 35, Isue 1, page 83-105.
Michael J.M., Xiaoyan Z., Dirk V.V.,(1999) “Bilevel Programming Approach for Trip
Matrix Estimation and Traffic Control Problems with Stochastic user Equilibrium Link
Flows”, Transportation Research, Part B 35, 23 – 40.
Morales G., (1997) “O Problema de Programação Matemática com restrições
Generalizadas de Equilíbrio”, Tese de Doutorado, COPEE/ Sistemas, UFRJ.
Montero L., (1995) The Traffic Assignment Problem: Resolution Algorithms. State of the
Art Survey (II).
Nguyen S., Pallottino S., (1987) “Equilibrium Traffic Assignment for Large Scale Transit
Network”, Elsevier Science Publishers B.V. (North-Holland).
103
Nguyen S., Dupuis C., (1984) “An Efficient Method for Computing Traffic Equilibria in
Network with asynmetric Transportation Costs”, Transportation Science, 18, 185– 202.
Pang J.S., Chan D. (1982), “Iterative Methods for Variational and Complementary
Problems”.
Mathematical
Programming 24,
284-313,
North-Holland,
Publishing
Company.
Peng J. M., (1997) “Global Method for Monotone Variational Inequality Problems with
Inequality Constraints”. Journal of Optimization Theory and Aplications: Vol. 95, No 2. pp
419-430.
Smith M. J., (1979) “The existence Uniqueness and Stability of Traffic Equilibria”,
Transportation Research, Vol. 13B, pp. 295-304.
Shor N. Z., (1985) “Minimization Methods for Non Differentiable Functions”. SpringerVerlag. New York.
Shor, N.Z., (1998) “Nondiferentiable Optimization and Polynomial Problems”, ISBN 07923-2785-3.
Smith M. J., (1992) “A New Dynamic Traffic Model and the existence and calculation of
dynamic user equilibrium on congested capacity-constrained roads networks”,
Transportation Research, Vol. 27B, No 1, pp. 49-63.
Shimizu K., Ishizuka Y., Bard J.F., (1997) “Nondiferentiable and two level mathematical
programming”. Kluwer Academic Publishers.
Suh W.C., (1999) “Optimization of area traffic control for equilibrium network flows”,
Transportation Science, Vol. 33, No 3.
Vyacheslav , Kalashnikov V., Kalashnikova N. I. (1996), “Solving Two-Level Variational
Inequality”, Journal of Global Optimization 8: 289-294.
104
Van V.D., (1982) ”SATURN - a modern assignment model. Traffic Engineering and
Control”, 23:578-581.
Wardrop J. G. (1952), “Some theoretical aspects of road traffic research”, Proceedings
of thee Institute of Civil Engineers, Part II 1, 325-378.
Yang H., Bell, M., (2001) “An equivalent continuously diferentiable model a locally
convergent algorithm for the continuous network design problem”. Transportation
Research Part B: Methodogical Vol. 35, Isue 1, pp83-105.
Yang H., Yagar, S. (1995) “Traffic Assgnment and Signal Control in Saturated Road
Network”. Transportation Research - A . Vol. 29A , No . 2, pp. 125-139.
Ye, J.J., Zhu, D.L., (1995), “Optimality Conditions for Bilevel Programming Ploblems”,
Optimization, 33, pp 9-27.
Zuhovickii, S., Poliak R. A., Primak M. E., (1969), “Two Methods of Search of
Equilibrium of n Person-concave-Games”, Soviet Math. Dokl. 10, 2.