COSTA, Camila Ferreira. Nearest neighbors with operating time constraints and optimal sequenced route queries in time-dependent road networks. 2014. 75 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-28T19:27:19Z No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T15:43:28Z (GMT) No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Made available in DSpace on 2016-08-01T15:43:28Z (GMT). No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) Previous issue date: 2014 / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries. / Nesta dissertação nós estudamos os problemas de processar uma variação de consulta de vizinhos mais próximos e de planejamento de rotas em redes viárias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro é geralmente dado pela distância física entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histórico das condições de tráfego. Mais especificamente, o tempo que um objeto móvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horários de pico, quando o tráfego é intenso e as ruas estão congestionadas, é muito maior do que em horários normais. Dentro do contexto apresentado, primeiramente nós estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuário pode começar a ser servido o mais rápido possível. Em outras palavras, nós buscamos minimizar a soma do tempo de viagem até um ponto de interesse mais o tempo de espera até que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais próximos em redes dependentes do tempo, porém, eles não levam em consideração o horário de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estão mais próximos do usuário, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuário espere por muito tempo. Nós propomos e discutimos três soluções para essa consulta que são baseadas em um algoritmo de expansão incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funções heurísticas adequadas para cada solução. Com o uso do algoritmo A*, nós visamos reduzir o percentual da rede avaliado na busca, evitando expandir vértices que oferecem uma baixa probabilidade de alcançar nosso objetivo. Também apresentamos resultados experimentais que comparam o número de acessos ao disco exigido em cada solução em relação a alguns parâmetros diferentes e que indicam em que casos deve-se optar por cada solução. Na segunda consulta, nós visamos encontrar a rota ótima que conecta uma dada origem a um dado destino e que passa por uma série de pontos de interesse pertencentes a categorias determinadas pelo usuário em uma certa ordem também especificada pelo usuário. Esse tipo de consulta é conhecida como OSR, do inglês, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguém está indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vários bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluções para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. Nós propomos uma solução ótima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansão. Além disso, como uma consulta OSR em redes viárias tende a re-expandir um número muito grande de vértices, nós incorporamos à essa solução um esquema para reduzir o número de re-expansões. Nós também apresentamos resultados experimentais que mostram a eficiência dessa solução em comparação com uma solução de base que foi obtida a partir da estensão de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintéticas.

COSTA, Camila Ferreira. Nearest Neighbors with Operating Time Constraints and Optimal Sequenced Route Queries in Time-Dependent Road Networks. 2014. 75 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2014. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-06T19:14:12Z No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-06T19:18:16Z (GMT) No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Made available in DSpace on 2016-06-06T19:18:16Z (GMT). No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) Previous issue date: 2014 / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries. / Nesta dissertação nós estudamos os problemas de processar uma variação de consulta de vizinhos mais próximos e de planejamento de rotas em redes viárias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro é geralmente dado pela distância física entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histórico das condições de tráfego. Mais especificamente, o tempo que um objeto móvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horários de pico, quando o tráfego é intenso e as ruas estão congestionadas, é muito maior do que em horários normais. Dentro do contexto apresentado, primeiramente nós estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuário pode começar a ser servido o mais rápido possível. Em outras palavras, nós buscamos minimizar a soma do tempo de viagem até um ponto de interesse mais o tempo de espera até que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais próximos em redes dependentes do tempo, porém, eles não levam em consideração o horário de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estão mais próximos do usuário, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuário espere por muito tempo. Nós propomos e discutimos três soluções para essa consulta que são baseadas em um algoritmo de expansão incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funções heurísticas adequadas para cada solução. Com o uso do algoritmo A*, nós visamos reduzir o percentual da rede avaliado na busca, evitando expandir vértices que oferecem uma baixa probabilidade de alcançar nosso objetivo. Também apresentamos resultados experimentais que comparam o número de acessos ao disco exigido em cada solução em relação a alguns parâmetros diferentes e que indicam em que casos deve-se optar por cada solução. Na segunda consulta, nós visamos encontrar a rota ótima que conecta uma dada origem a um dado destino e que passa por uma série de pontos de interesse pertencentes a categorias determinadas pelo usuário em uma certa ordem também especificada pelo usuário. Esse tipo de consulta é conhecida como OSR, do inglês, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguém está indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vários bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluções para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. Nós propomos uma solução ótima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansão. Além disso, como uma consulta OSR em redes viárias tende a re-expandir um número muito grande de vértices, nós incorporamos à essa solução um esquema para reduzir o número de re-expansões. Nós também apresentamos resultados experimentais que mostram a eficiência dessa solução em comparação com uma solução de base que foi obtida a partir da estensão de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintéticas.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Nesta dissertaÃÃo nÃs estudamos os problemas de processar uma variaÃÃo de consulta de vizinhos mais prÃximos e de planejamento de rotas em redes viÃrias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro à geralmente dado pela distÃncia fÃsica entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histÃrico das condiÃÃes de trÃfego. Mais especificamente, o tempo que um objeto mÃvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horÃrios de pico, quando o trÃfego à intenso e as ruas estÃo congestionadas, à muito maior do que em horÃrios normais. Dentro do contexto apresentado, primeiramente nÃs estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuÃrio pode comeÃar a ser servido o mais rÃpido possÃvel. Em outras palavras, nÃs buscamos minimizar a soma do tempo de viagem atà um ponto de interesse mais o tempo de espera atà que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais prÃximos em redes dependentes do tempo, porÃm, eles nÃo levam em consideraÃÃo o horÃrio de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estÃo mais prÃximos do usuÃrio, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuÃrio espere por muito tempo. NÃs propomos e discutimos trÃs soluÃÃes para essa consulta que sÃo baseadas em um algoritmo de expansÃo incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funÃÃes heurÃsticas adequadas para cada soluÃÃo. Com o uso do algoritmo A*, nÃs visamos reduzir o percentual da rede avaliado na busca, evitando expandir vÃrtices que oferecem uma baixa probabilidade de alcanÃar nosso objetivo. TambÃm apresentamos resultados experimentais que comparam o nÃmero de acessos ao disco exigido em cada soluÃÃo em relaÃÃo a alguns parÃmetros diferentes e que indicam em que casos deve-se optar por cada soluÃÃo. Na segunda consulta, nÃs visamos encontrar a rota Ãtima que conecta uma dada origem a um dado destino e que passa por uma sÃrie de pontos de interesse pertencentes a categorias determinadas pelo usuÃrio em uma certa ordem tambÃm especificada pelo usuÃrio. Esse tipo de consulta à conhecida como OSR, do inglÃs, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguÃm està indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vÃrios bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluÃÃes para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. NÃs propomos uma soluÃÃo Ãtima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansÃo. AlÃm disso, como uma consulta OSR em redes viÃrias tende a re-expandir um nÃmero muito grande de vÃrtices, nÃs incorporamos à essa soluÃÃo um esquema para reduzir o nÃmero de re-expansÃes. NÃs tambÃm apresentamos resultados experimentais que mostram a eficiÃncia dessa soluÃÃo em comparaÃÃo com uma soluÃÃo de base que foi obtida a partir da estensÃo de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintÃticas. / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries.