Upload
makala
View
49
Download
0
Embed Size (px)
DESCRIPTION
Un algoritmo basado en Programación Lineal para el problema del cartero rural privatizado. Julián Aráoz Elena Fernández Departament d’Estadística i Investigació Operativa, UPC. España Oscar Meza Departamento de Computación y Tecnología de la Información, - PowerPoint PPT Presentation
Citation preview
Un algoritmo basado en Programación Lineal para el problema del cartero rural privatizado
Julián Aráoz
Elena Fernández
Departament d’Estadística i Investigació Operativa, UPC. España
Oscar Meza
Departamento de Computación y Tecnología de la Información, Universidad Simón Bolívar. Venezuela
1. El problema del Cartero Rural Privatizado (PRPP)
2. Un modelo para (PRPP)
2.1 Restricciones.
2.2 Algunas propiedades.
3. Separación de las restricciones.
4. Heurística para PRPP
5. Algoritmo.
6. Experiencia Computacional.
7. Comentarios. Trabajo futuro.
be: beneficio por servir e
ce : costo de recorrer e
d
E
D
C
B A9 6
7
3
9
6
42
7
0 9
9
9
0
0
90
9
d
E
D
C
B A9 - 7
9 - 3- 4- 2
- 79 - 4
9 - 7
Aristas con demanda
Problema del cartero Rural Privatizado (PRPP)
Problema del cartero Rural Privatizado (PRPP)
Dado un grafo G = ( V, E) con un vértice distinguido d (el depósito) y dos funciones:
Encontrar un recorrido cerrado C* que maximice el valor de
donde C es un recorrido cerrado que pasa por d, puede atravesar varias veces una misma arista, y te es el número de veces que la arista e se atraviesa en C.
Beneficio: b: Eℝ
Costo: c: Eℝ
- PRPP fue propuesto en:
Aráoz, J., E. Fernández, C. Zoltan. Privatized Rural Postman problems. Computers and Operations Research. En prensa.
- PRPP es NP-Hard
Ce
eee ctb
caso otroen 0
vezprimerapor recorre se arista si1 exe
vez.primera la de después atraviesa se que vecesde número : eye
e = be - ce
''' Ee
eeEe
ee ycxMax
• Todos los nodos tienen grado par:
• Conectividad de las aristas recorridas con el depósito.
• ye’’ 1
• ye’’ xe’
Relaciones de Dominancia
G’=(V, E’E’’)
Un modelo para PRPP........
x( ’ (v) \ F’ ) + y( ’’ (v) \ F’’ ) x( F’ ) + y( F’’ ) - | F’ F’’ | + 1
v
’’(v)\F’’
’(v)\F’
F’ F’’
vV, F ’ ‘(v), F ’’ ’’(v), | F ’ F ’’| impar.
• Implicadas por las desigualdades de cocircuito
x (’ (v)) + y (’’ (v)) 0 mod 2
v V
Los nodos tienen grado par
F. Barahona and M. Groeschel. On the cycle polytope of a binary matroid. J. Comb. Theory, 40:40–62, 1986.
• Usadas en el contexto del “Rural Postman Problem”:
G. Ghiani and G. Laporte. A branch-and-cut algorithm for the undirected rural postman problem.
Mathematical Programming, 87:467–481, 2000.
R = { e E : e 0 }e E e= be-2ceGR (V (R) {d }, R)
{ Ci}i=0,…,p, dC0 componentes de GR. Vi= V(Ci)(Vi) en G
R (Vi) en GR
Dado e C*, si V (e) Vk para alguna componente Ck de GR R(Vk) C*.
( ó bien todas las aristas de R (Vk ) están en C* ó ninguna de ellas)
Algunas propiedades
Sea Ck una componente conexa de GR . Si e (Vk) \ R en C*, e se recorre como mucho una vez. (ye=0)
,Rk
e R kex x e V k P
\ ,Rk
e k kex x e V V R k P
Sea C* una solución óptima...
0, \ ,e ky e V R k P
x(’ (S )) + y(’’ (S )) 2 xe S V \ {d } ; e (S)
Conectividad con el depósito de las aristas recorridas.
x(’ (S)) + y(’’ (S)) 2 xekR S V \{d} ; k0, Vk S
)
x(’ (S)) + y(’’ (S)) 2xe S V \{d}); e ’(S) ’(S) t.q. V(e) V(R) =
Belenguer, J., E. Benavent, The Capacitated Arc Routing Problem: valid inequalities and facets. Computational Optimization and Applications (10), 165-187, 1998.
''' Ee
eeEe
ee ycxMax
impar. ''''''','',
1''''''''\'''\'
FFvFvFVv
FFFyFxFvyFvx
' '' 2
\ , ' ' t.q.
ex S y S x
S V d e S S V e V R
,Rk
e R kex x e V k P
' '' 2
\ , 0,
Rk
k
ex S y S x
S V d k V S
'' 'e ey x e E
\ ,Rk
e k kex x e V V R k P
PkRVey ke ,\0
01 Vex Re
Eeyx ee 1,0, '''
Un modelo para PRPP
Grado par
Conexión con el depósito
Relaciones de dominancia
Problema de Separación para restricciones de grado
' ''
**
'''',''
111''\''*'\'*minFe Fe
ee
vFvF
v yxFvyFvxA
Sean F ’ = {e’(v) : x*e’ 0.5}; F’’ = {e’’(v) : y*e’’ 0.5}
Si F’ F’’ es de cardinalidad par entonces
Sean z*e_min = min{y*e : eF’’}, z*e_max = max{x*e : e (v)\F’}
Si z*e_min - 0.5 0.5 - z*e_max entonces
eliminar e_min de F’en otro caso
añadir e_max a F’
Si la correspondiente desigualdad de grado está violada por F’ F’’ , tenemos un corte.
x( ’ (v) \ F’ ) + y( ’’ (v) \ F’’ ) x( F’ ) + y( F’’ ) - | F’ F’’ | +1
El algoritmo anterior resuelve el problema de separación para las restricciones de grado de forma exacta y su orden es O(|E|).
Sea (x*, y*) solución del LP actual.....
Separación de las restricciones de conexión
Adaptamos el algoritmo exacto de Belenguer y Benavent (1998)
Para cada arista e = {u,v}, con u, v diferentes del depósito y x*e >0,
Obtener el corte mínimo ‘(S) ‘’(S) tal que e‘ ( S) ’’( S) a partir de árbol de cortes mínimos.
Si el valor del corte es menor que 2x*e la desigualdad x(’(S)) + y(‘’(S)) 2xe está violada.
Sea (x*, y*) solución del LP actual....
x(’(S)) + y(‘’(S)) 2xe
D. Gusfield. Very Simple Methods for All Pairs Network Flow Analysis. SIAM Journal of Computing 19, 143-155, 1990.
Belenguer, J., E. Benavent, The Capacitated Arc Routing Problem: valid inequalities and facets. Computational Optimization and Applications (10), 165-187, 1998.
1. Transformar PRPP en un RPP.
Aristas requeridas de RPP, ER, las que tienen x*e > y {d, d’}
(arista ficticia que garantiza que la solución pasa por el depósito)
2. Aplicar heurística 3T de Fernández, Meza, Garfinkel, Ortega (2002) para obtener una solución factible para RPP.
3. Eliminar aristas paralelas {d, d ’} .
a. Construir un árbol T de coste mínimo.
b. Añadir aristas a ET ER para que todos los nodos tengan grado par. (matching perfecto de costo mínimo
en el subgrafo inducido por nodos de grado impar: M)
c. Aplicar “atajos” para mejorar la solución ET ER EM .
E. Fernández, O. Meza, R. Garfinkel, and M. Ortega. On the undirected rural postman problem: Tight bounds based on a new formulation. Operations Research, 51:281–291, 2003.
T1: Aristas candidatas: Todas las del grafo original Costos: los del grafo original. (Frederikson, 1979)
T2: Aristas candidatas: { e’E’: x*e’ > 0} { e’’E’’: y*e’’ > 0}. Costos: 1- x*e , 1- y*e’’ .
T3: Aristas candidatas: { e’E’: x*e’ > 0} { e’’E’’: y*e’’ > 0}.. Costos: los del grafo original .
Heurística 3T
Heurística para PRPP
0. Sea LPR0 la relajación lineal de PRPP. k 0
1. optimo = falso, mejorxy= (0,0), fin = falso,
2. Mientras fin = falso hacer
Encontrar una solucion (x*, y*) de LPRk
Si entonces
Si ( x*, y*) es factible para PRPP entonces
mejorxy = (x*, y*), fin = cierto,
en otro caso
i) Identificar desigualdades de grado y de conectividad violadas por (x*, y*).
ii) Añadir las desigualdades identificadas a LPRk.
iii) Si no se ha identificado ninguna desigualdad violada entonces fin = cierto
en otro casoAplicar procedimiento de fijación de variables.k:= k + 1
4. Aplicar la heurística y obtener la correspondiente solución (xh, yh) y cota inferior zh = z (xh, yh).
Si entonces y mejorxy = ( xh, yh )
,z 0z
*, *z z x y *, *z z x y
zz
( , )h hz z x y
Algoritmo LP para PRPP
( , )h hz z x y
|V| 100* (RL-HEU)/RL
100 * (HEU-opt_RPP) /
opt_RPP# opt RPP
Tiempo RL (seg)
Tiempo Heur. (seg)
Num Iter. RL
Num. Rest.Con.
RL
Num. Rest. Par.
conjuntos RL
Num. Rest. Par.
vertices RL
Albaidas [90, 102] 0,0026 0,0000 2/2 6,33 3,05 6,00 176,50 22,50 38,00
P's [7, 50] 0,0047 0,6447 19/23 (1) 0,17 0,49 1,83 29,92 1,29 5,79
D's [16, 100] 0,0075 0,9708 16 / 33 (3) 39,13 1,95 13,86 684,86 109,42 16,31
G's [16, 100] 0,0056 0,7342 25/33 (3) 40,61 1,44 18,69 878,33 108,53 10,61
R's [20, 50] 0,0017 0,2190 15/20 3,73 0,05 25,30 474,20 104,15 3,15
Experiencia computacional
RPP’s be=1000*ce
Instancias de RPP transformadas a PRPP:
- ALBAIDA’s:obtained from the Albaida, Spain Graph (see Corberan and Sanchis [10]). - P’s contains the 24 instances of Christodes et al. [9].
- The last three groups contain instances from Hertz et al [15] - D´s: 36 instances with vertices of degree 4 and disconnected required edge sets - G’s: 36 grid instances (labeled GRID), and - R’s: 20 randomly generated instances
Algoritmo para un nuevo problema: Privatized Rural Postman Problem.
Incorporamos relaciones de dominancia al modelo.
Resolvemos el problema de separación de forma exacta.
Aplicamos una heurística a partir de la solución óptima del LP.
Resultados satisfactorios en experiencia computacional preliminar.
Trabajo Futuro: Estudio de otro tipo de problemas con beneficio.
Mejora del proceso de fijación de variables.
Problemas con capacidades.
…
Comentarios Finales