Tese de doutoramento. Engenharia Informática. Faculdade de Engenharia. Universidade do Porto. 2010

This dissertation presents a cartographic approach to the dynamic vehicle routing problem with time windows and stochastic customers (DVRPTWSC). The objectives are to minimize the total travel time and maximize the number of new requests served. Addressing the DVRPTWSC requires solving the vehicle routing problem with time windows (VRPTW). A memetic algorithm (MA) for the VRPTW is proposed. The MA prunes the search space using the information gathered by a clustering procedure, which is applied to customers spatial data. The cartographic approach to the DVRPTWSC is incorporated into a multiagent system where a dispatcher agent plans the routes for vehicle agents. Before creating the initial routing plan, a cartographic processing is applied. This procedure uses hierarchical clustering to divide the region where customers are located into a hierarchy of nested regions. The initial routing plan considers known requests and potential requests sampled from known probability distributions. It is created using the search operators of the MA, which in turn use the information obtained from the hierarchical clustering to perform the search. Over the planning horizon, the dispatcher updates the routing plan: Potential requests that were included in the initial routing plan and do not materialize are removed and new requests are processed using the assignation of requests based on nested regions (ARNR). The ARNR procedure is aimed at reducing the number of vehicles considered for serving new requests. It tries to assign the requests among the vehicles that can serve them at low detour costs. The nested regions created in the cartographic processing are used to identify such vehicles. Experimental results show that the proposed MA performs competitively with state-of-the-art heuristics for the VRPTW. The proposed approach to the DVRPTWSC outperforms approaches that do not include potential requests in the initial routing plan. The use of the ARNR procedure significantly reduces the number of vehicles considered for serving new requests, and it yields solutions similar to those obtained when considering all vehicles in operation. The proposed approach performs consistently under three levels of dynamism: low, medium, and high. / Esta dissertação apresenta uma abordagem cartográfica para o problema de roteamento de veículos dinâmico com janelas de tempo e clientes estocásticos (DVRPTWSC, por sua sigla em inglês). Os objetivos considerados são minimizar o tempo total de viagem e maximizar o número de pedidos novos atendidos. Para abordar o DVRPTWSC é necessário resolver o problema de roteamento de veículos com janelas de tempo (VRPTW, por sua sigla em inglês). Assim, para tratar o VRPTW propõe-se um algoritmo memético (MA, por sua sigla em inglês). O MA reduz o espaço de busca usando informação obtida por meio de um procedimento de clusterização, o qual é aplicado aos dados espaciais dos clientes. Para o DVRPTWSC, a abordagem cartográfica é incorporada em um sistema multiagente, no qual um agente roteirizador planeja as rotas para os agentes veículos. O processamento cartográfico é aplicado antes de criar o plano de rotas inicial para o DVRPTWSC. Este procedimento usa clusterização hierárquica para dividir a região onde estão os clientes em uma hierarquia de regiões encaixadas. O plano de rotas inicial considera pedidos conhecidos e pedidos potenciais amostrados de distribuições de probabilidade conhecidas. Para obter o plano de rotas inicial, usam-se os operadores de busca do MA, os quais utilizam a informação obtida da clusterização hierárquica para fazer a busca. Ao longo do horizonte de planejamento, o roteirizador atualiza o plano de rotas: Pedidos potenciais que foram considerados no plano de rotas inicial e que não foram consolidados são removidos e novos pedidos são incluídos usando o procedimento assignation of requests based on nested regions (ARNR). O procedimento ARNR visa reduzir o número de veículos considerados para atender novos pedidos. Para isso, tenta designar os novos pedidos aos veículos disponíveis para o atendimento que possuem os menores custos de desvio da rota pré-determinada. As regiões encaixadas criadas no processamento cartográfico são utilizadas para identificar esses veículos. Para o VRPTW, resultados experimentais mostram que o MA proposto é competitivo com métodos do estado da arte. A abordagem proposta para o DVRPTWSC supera abordagens que não incluem pedidos potenciais no plano de rotas inicial. O uso do procedimento ARNR reduz significativamente o número de veículos considerados para atender novos pedidos, e produz soluções similares às produzidas quando se consideram todos os veículos em operação. A abordagem desenvolvida para o DVRPTWSC tem um desempenho consistente para três níveis de dinamismo: baixo, médio e alto.

This dissertation presents a cartographic approach to the dynamic vehicle routing problem with time windows and stochastic customers (DVRPTWSC). The objectives are to minimize the total travel time and maximize the number of new requests served. Addressing the DVRPTWSC requires solving the vehicle routing problem with time windows (VRPTW). A memetic algorithm (MA) for the VRPTW is proposed. The MA prunes the search space using the information gathered by a clustering procedure, which is applied to customers spatial data. The cartographic approach to the DVRPTWSC is incorporated into a multiagent system where a dispatcher agent plans the routes for vehicle agents. Before creating the initial routing plan, a cartographic processing is applied. This procedure uses hierarchical clustering to divide the region where customers are located into a hierarchy of nested regions. The initial routing plan considers known requests and potential requests sampled from known probability distributions. It is created using the search operators of the MA, which in turn use the information obtained from the hierarchical clustering to perform the search. Over the planning horizon, the dispatcher updates the routing plan: Potential requests that were included in the initial routing plan and do not materialize are removed and new requests are processed using the assignation of requests based on nested regions (ARNR). The ARNR procedure is aimed at reducing the number of vehicles considered for serving new requests. It tries to assign the requests among the vehicles that can serve them at low detour costs. The nested regions created in the cartographic processing are used to identify such vehicles. Experimental results show that the proposed MA performs competitively with state-of-the-art heuristics for the VRPTW. The proposed approach to the DVRPTWSC outperforms approaches that do not include potential requests in the initial routing plan. The use of the ARNR procedure significantly reduces the number of vehicles considered for serving new requests, and it yields solutions similar to those obtained when considering all vehicles in operation. The proposed approach performs consistently under three levels of dynamism: low, medium, and high. / Esta dissertação apresenta uma abordagem cartográfica para o problema de roteamento de veículos dinâmico com janelas de tempo e clientes estocásticos (DVRPTWSC, por sua sigla em inglês). Os objetivos considerados são minimizar o tempo total de viagem e maximizar o número de pedidos novos atendidos. Para abordar o DVRPTWSC é necessário resolver o problema de roteamento de veículos com janelas de tempo (VRPTW, por sua sigla em inglês). Assim, para tratar o VRPTW propõe-se um algoritmo memético (MA, por sua sigla em inglês). O MA reduz o espaço de busca usando informação obtida por meio de um procedimento de clusterização, o qual é aplicado aos dados espaciais dos clientes. Para o DVRPTWSC, a abordagem cartográfica é incorporada em um sistema multiagente, no qual um agente roteirizador planeja as rotas para os agentes veículos. O processamento cartográfico é aplicado antes de criar o plano de rotas inicial para o DVRPTWSC. Este procedimento usa clusterização hierárquica para dividir a região onde estão os clientes em uma hierarquia de regiões encaixadas. O plano de rotas inicial considera pedidos conhecidos e pedidos potenciais amostrados de distribuições de probabilidade conhecidas. Para obter o plano de rotas inicial, usam-se os operadores de busca do MA, os quais utilizam a informação obtida da clusterização hierárquica para fazer a busca. Ao longo do horizonte de planejamento, o roteirizador atualiza o plano de rotas: Pedidos potenciais que foram considerados no plano de rotas inicial e que não foram consolidados são removidos e novos pedidos são incluídos usando o procedimento assignation of requests based on nested regions (ARNR). O procedimento ARNR visa reduzir o número de veículos considerados para atender novos pedidos. Para isso, tenta designar os novos pedidos aos veículos disponíveis para o atendimento que possuem os menores custos de desvio da rota pré-determinada. As regiões encaixadas criadas no processamento cartográfico são utilizadas para identificar esses veículos. Para o VRPTW, resultados experimentais mostram que o MA proposto é competitivo com métodos do estado da arte. A abordagem proposta para o DVRPTWSC supera abordagens que não incluem pedidos potenciais no plano de rotas inicial. O uso do procedimento ARNR reduz significativamente o número de veículos considerados para atender novos pedidos, e produz soluções similares às produzidas quando se consideram todos os veículos em operação. A abordagem desenvolvida para o DVRPTWSC tem um desempenho consistente para três níveis de dinamismo: baixo, médio e alto.

Made available in DSpace on 2015-03-05T13:59:42Z (GMT). No. of bitstreams: 0 Previous issue date: 22 / Nenhuma / Este trabalho está relacionado com a aplicação de técnicas de Inteligência Artificial no desenvolvimento de um Sistema Multi-Agente robótico aplicado ao problema da monitoração e combate a incêndios em áreas florestais. O objetivo macro é evoluir estratrégias de formação de equipes de combate a incêndio (unidade de controle) e criar métodos robustos de navegação em agentes robóticos (unidades de combate), considerando um ambiente virtual de simulação realística.No sistema proposto, uma equipe de agentes autônomos trabalha cooperativamente a fim de realizar com sucesso a identificação e o combate a incêndios em áreas florestais, sem intervenção humana. O ambiente virtual 3D suporta uma série de características fundamentais para a simulação realística da operação, como terrenos irregulares, processos naturais e restrições físicas na criação e uso de robôs móveis. Este ambiente foi implementado através do uso das bibliotecas OSG, ODE e Demeter. A operacão multi-agente depende essencialmente de duas etapas: p / This work is related to the application of Artificial Intelligence techniques to develop a Multi-Agent Robotic System applied to the problem of monitoring wild forest fires and to the execution of fire fighting actions. Our main goal was to evolve strategies (control unit) in order to define the positioning of the fire-fighting autonomous robotic team and to create robust navigation methods used to control robotic agents (combat units). This work was developed based on simulations accomplished using a realistic 3D virtual environment, specially implemented for this purpose, using the software libraries OSG, Demeter and ODE. In the proposed system, a team of autonomous agents work cooperatively in order to successfully perform the identification and fighting of forest fires, without any human intervention. The 3D virtual environment includes several features for realistic simulation of this task, as for example, adoption of irregular terrains, natural processes simulation (e.g. fire propagation), and simulati

En esta tesis se ha desarrollado un marco de trabajo que hace uso de las tecnologías de agentes y de Servicios Web Semánticos para la elaboración de aplicaciones que puedan tratar con el dinamismo de la Web, al tiempo que se pueden beneficiar de características como la autonomía, el aprendizaje y el razonamiento. Éste es el punto en que cobra relevancia la Ingeniería Ontológica. Las ontologías son los componentes que permiten que la comunicación entre agentes y Servicios Web, situados a distintos niveles de abstracción, se produzca de forma fluida y sin interpretaciones erróneas. La arquitectura del marco de trabajo desarrollado consta, fundamentalmente, de un entorno multi-agente, un conjunto de bases de conocimiento y diversas interfaces que permiten al sistema comunicarse, de forma efectiva, con las entidades externas identificadas, a saber, Servicios Web y proveedores de servicios, entidades (usuarios) consumidores de servicios, y desarrolladores. / In this thesis, a knowledge-based Semantic Web Services framework that successfully integrates Intelligent Agents and Semantic Web Services technologies has been developed. For achieving this combination, the framework takes an ontology-centred approach. Ontologies are the facilitating technology that enables a seamlessly communication between agents and services.

En esta tesis se propone el uso de agentes inteligentes en entornos de aprendizaje en línea con el fin de mejorar la asistencia y motivación del estudiante a través de contenidos personalizados que tienen en cuenta el estilo de aprendizaje del estudiante y su nivel de conocimiento. Los agentes propuestos se desempeñan como asistentes personales que ayudan al estudiante a llevar a cabo las actividades de aprendizaje midiendo su progreso y motivación. El entorno de agentes se construye a través de una arquitectura multiagente llamada MASPLANG diseñada para dar soporte adaptativo (presentación y navegación adaptativa) a un sistema hipermedia educativo desarrollado en la Universitat de Girona para impartir educación virtual a través del web.Un aspecto importante de esta propuesta es la habilidad de construir un modelo de estudiante híbrido que comienza con un modelo estereotípico del estudiante basado en estilos de aprendizaje y se modifica gradualmente a medida que el estudiante interactúa con el sistema (gustos subjetivos). Dentro del contexto de esta tesis, el aprendizaje se define como el proceso interno que, bajo factores de cambio resulta en la adquisición de la representación interna de un conocimiento o de una actitud. Este proceso interno no se puede medir directamente sino a través de demostraciones observables externas que constituyen el comportamiento relacionado con el objeto de conocimiento. Finalmente, este cambio es el resultado de la experiencia o entrenamiento y tiene una durabilidad que depende de factores como la motivación y el compromiso.El MASPLANG está compuesto por dos niveles de agentes: los intermediarios llamados IA (agentes de información) que están en el nivel inferior y los de Interfaz llamados PDA (agentes asistentes) que están en el nivel superior. Los agentes asistentes atienden a los estudiantes cuando trabajan con el material didáctico de un curso o una lección de aprendizaje. Esta asistencia consiste en la recolección y análisis de las acciones de los estudiantes para ofrecer contenidos personalizados y en la motivación del estudiante durante el aprendizaje mediante el ofrecimiento de contenidos de retroalimentación, ejercicios adaptados al nivel de conocimiento y mensajes, a través de interfaces de usuario animadas y atractivas. Los agentes de información se encargan del mantenimiento de los modelos pedagógico y del dominio y son los que están en completa interacción con las bases de datos del sistema (compendio de actividades del estudiante y modelo del dominio).El escenario de funcionamiento del MASPLANG está definido por el tipo de usuarios y el tipo de contenidos que ofrece. Como su entorno es un sistema hipermedia educativo, los usuarios se clasifican en profesores quienes definen y preparan los contenidos para el aprendizaje adaptativo, y los estudiantes quienes llevan a cabo las actividades de aprendizaje de forma personalizada. El perfil de aprendizaje inicial del estudiante se captura a través de la evaluación del cuestionario ILS (herramienta de diagnóstico del modelo FSLSM de estilos de aprendizaje adoptado para este estudio) que se asigna al estudiante en su primera interacción con el sistema. Este cuestionario consiste en un conjunto de preguntas de naturaleza sicológica cuyo objetivo es determinar los deseos, hábitos y reacciones del estudiante que orientarán la personalización de los contenidos y del entorno de aprendizaje. El modelo del estudiante se construye entonces teniendo en cuenta este perfil de aprendizaje y el nivel de conocimiento obtenido mediante el análisis de las acciones del estudiante en el entorno.

Made available in DSpace on 2016-08-17T14:53:15Z (GMT). No. of bitstreams: 1 Fernando Pinheiro Costa Junior.pdf: 2747809 bytes, checksum: 341087c9b5282e045ab5af119473be1e (MD5) Previous issue date: 2010-12-13 / The present study attempts, through the methodology TROPOS, modeling a Multi- Agent System for Stock Exchange whose goal is make negotiations among agents in a Virtual Stock Exchange. The agents will act as investors in the Stock Market making the purchase and sale of stocks. This model is intended to specify agents with the ability to decide the best time for investing according to market indicators, i.e., when is the better time to buy or sell stocks. The model can identify the agents, the interaction protocols between agents, the applied technologies and the structures of the application. Therefore, the JADE platform will support the development of agents regarding the negotiation process. Such platform will provide communication between agents creating Broker Agents to provide communication with other Intermediate Agents whose information is collected in its Knowledge Base in order to make the negotiation. The after examining this study, conclusions could be taken about the subject explained and future suggested improvements can be implemented. / O presente trabalho busca, através da metodologia TROPOS, modelar um Sistema Multi-Agente para Bolsa de Valores com o objetivo de realizar negociações entre agentes em uma Bolsa de Valores virtual. Os agentes irão desempenhar a função de investidores na Bolsa de Valores, efetuando operações de compra e venda de ações. Esta modelagem tem o propósito de especificar agentes com a capacidade de decidir qual o melhor momento para realização dos investimentos pautado nos indicadores de mercado, ou seja, qual a melhor hora para comprar ou vender títulos de créditos. Neste sentido, serão identificados os agentes, os protocolos de interação entre agentes, as tecnologias aplicadas, as estruturas da aplicação. Portanto, a plataforma JADE dará suporte para o desenvolvimento dos agentes no tocante ao processo de negociação. Tal plataforma proporcionará a comunicação entre os agentes, criando Agentes Corretores a fim de proporcionar a comunicação com outro Agente Intermediário com as informações adquiridas em sua Base de Conhecimento para que assim seja realizada a negociação. Assim, após a análise desta obra poderão ser retiradas conclusões acerca do tema explanado e sugeridas melhorias para que no futuro possam ser implementadas.