Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / El problema de la evasión del pago del pasaje en el transporte público es transversal a distintos sistemas de transporte a lo largo del mundo, causando pérdidas a las empresas operadoras y al Estado. Ya que la instalación de barreras físicas y torniquetes no siempre es posible o deseable, diversos sistemas recurren al control del pago del pasaje a bordo. En esta tesis se modela el fenómeno de la evasión como un juego de Stackelberg sobre un grafo dirigido en el que interactúan dos jugadores: un inspector (el líder) y un evasor (el seguidor). Para controlar la evasión, el líder se ubica aleatoriamente sobre a lo más un arco de la red. Para ello, su estrategia consiste en fijar una distribución de probabilidad de inspección sobre los arcos del grafo. El seguidor, quien desea viajar entre dos nodos fijos sin pagar el pasaje, reacciona escogiendo como estrategia un camino, y lo recorre de manera que si atraviesa el arco donde se encuentra el inspector, deberá pagar una multa antes de continuar su viaje.
Dependiendo de su comportamiento después de pagar la multa, se hace la distinción entre un seguidor no adaptativo, que continúa su viaje por el camino escogido previamente sin modificar su ruta, y uno adaptativo, que continúa su trayecto a través de un camino mínimo con respecto a las distancias. Dada una distribución de probabilidad de inspección, los tiempos de viaje y el valor de la multa, el objetivo del seguidor es encontrar un camino de costo esperado mínimo. Mientras que para el seguidor no adaptativo este problema se reduce a encontrar un camino mínimo con respecto a una versión modificada de las distancias, la pregunta por la complejidad del problema del seguidor adaptativo queda abierta. En esta tesis se diseñan algoritmos pseudopolinomiales para este último problema en grafos acíclicos y en grafos generales, además de un algoritmo fuertemente polinomial en grafos generales para el caso en que la distribución de inspección es uniforme sobre los arcos. Por último, se presenta un esquema de aproximación a tiempo totalmente polinomial (FPTAS) en grafos generales, y se amplía un resultado previo de Correa et al., donde se muestra que el cuociente entre los valores óptimos de los problemas no adaptativo y adaptativo es a lo más 4/3, mostrando un ejemplo donde la cota es ajustada.
El líder, por su parte, es modelado de acuerdo a dos variantes. En la primera de ellas, su objetivo es maximizar el costo esperado del seguidor. Se prueba que cuando el seguidor es no adaptativo, este problema se puede resolver en tiempo polinomial, mientras que para el seguidor adaptativo se diseña un FPTAS. En la segunda variante, el líder busca maximizar el valor esperado de la multa recolectada. En el caso del seguidor no adaptativo, se demuestra que el problema de decisión asociado es NP-completo, mientras que para el seguidor adaptativo la pregunta por la complejidad se deja abierta.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/138899 |
| Date | January 2016 |
| Creators | Bahamondes Pizarro, Bastián Matías |
| Contributors | Correa Haeussler, José, Cominetti Cotti-Cometti, Roberto, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Industrial, Departamento de Ingeniería Matemática, Matuschke, Jannik, Soto San Martín, José |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0026 seconds