Descubriendo rutas populares a partir de trayectorias

La floreciente industria de servicios basados en ubicación ha acumulado una enorme colección de trayectorias de ubicación de usuarios, incluyendo conducción, ciclismo, senderismo, etc. En este trabajo, investigamos el problema de descubrir la Ruta Más Popular (MPR) entre dos ubicaciones observando los comportamientos de viaje de muchos usuarios anteriores. Esta nueva consulta es beneficiosa para los viajeros que piden direcciones o planean un viaje en una ciudad/área desconocida, ya que las experiencias de viaje históricas pueden revelar cómo las personas suelen elegir rutas entre ubicaciones. Para lograr este objetivo, primero desarrollamos un algoritmo de Expansión de Coherencia para recuperar una red de transferencia a partir de trayectorias crudas, que indica todos los movimientos posibles entre ubicaciones. Después de eso, se aplica el modelo de Cadena de Markov Absorbente para derivar una probabilidad de transferencia razonable para cada nodo de transferencia en la red, que se utiliza posteriormente como indicador de popularidad en la fase de búsqueda. Finalmente, proponemos un algoritmo de Producto de Máxima Probabilidad para descubrir la MPR a partir de una red de transferencia basada en los indicadores de popularidad de manera de búsqueda en amplitud, y ilustramos los resultados y el rendimiento del algoritmo a través de experimentos extensos.