Tese de doutoramento. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2003

Dissertação apresentada para obtenção do grau de Doutor em Engenharia Electrotécnica e de Computadores, na Faculdade de Engenharia da Universidade do Porto, sob a orientação do prof. Doutor Eugénio da Costa Oliveira

This thesis addresses the problem of learning in physical heterogeneous multi-agent systems(MAS) and the analysis of the benefits of using heterogeneous MAS with respect tohomogeneous ones. An algorithm is developed for this task; building on a previous work on stability in distributed systems by Tad Hogg and Bernardo Huberman, and combining two phenomena observed in natural systems, task partition and hierarchical dominance. This algorithm is devised for allowing agents to learn which are the best tasks to perform on the basis of each agent's skills and the contribution to the team global performance. Agents learn by interacting with the environment and other teammates, and get rewards from the result of the actions they perform. This algorithm is specially designed for problems where all robots have to co-operate and work simultaneously towards the same goal. One example of such a problem is role distribution in a team of heterogeneous robots that form a soccer team, where all members take decisions and co-operate simultaneously. Soccer offers the possibility of conducting research in MAS, where co-operation plays a very important role in a dynamical and changing environment. For these reasons and the experience of the University of Girona in this domain, soccer has been selected as the test-bed for this research. In the case of soccer, tasks are grouped by means of roles.One of the most interesting features of this algorithm is that it endows MAS with a highadaptability to changes in the environment. It allows the team to perform their tasks, whileadapting to the environment. This is studied in several cases, for changes in the environment and in the robot's body. Other features are also analysed, especially a parameter that defines the fitness (biological concept) of each agent in the system, which contributes to performance and team adaptability.The algorithm is applied later to allow agents to learn in teams of homogeneous andheterogeneous robots which roles they have to select, in order to maximise team performance. The teams are compared and the performance is evaluated in the games against three hand-coded teams and against the different homogeneous and heterogeneous teams built in this thesis. This section focuses on the analysis of performance and task partition, in order to study the benefits of heterogeneity in physical MAS.In order to study heterogeneity from a rigorous point of view, a diversity measure is developed building on the hierarchic social entropy defined by Tucker Balch. This is adapted to quantify physical diversity in robot teams. This tool presents very interesting features, as it can be used in the future to design heterogeneous teams on the basis of the knowledge on other teams.

El agua es un recurso escaso que, como tal, debe ser gestionado de manera eficiente. Así, uno de los propósitos de dicha gestión debiera ser la reducción de pérdidas de agua y la mejora del funcionamiento del abastecimiento. Para ello, es necesario crear un marco de trabajo basado en un conocimiento profundo de la redes de distribución. En los casos reales, llegar a este conocimiento es una tarea compleja debido a que estos sistemas pueden estar formados por miles de nodos de consumo, interconectados entre sí también por miles de tuberías y sus correspondientes elementos de alimentación. La mayoría de las veces, esas redes no son el producto de un solo proceso de diseño, sino la consecuencia de años de historia que han dado respuesta a demandas de agua continuamente crecientes con el tiempo. La división de la red en lo que denominaremos clusters de abastecimiento, permite la obtención del conocimiento hidráulico adecuado para planificar y operar las tareas de gestión oportunas, que garanticen el abastecimiento al consumidor final. Esta partición divide las redes de distribución en pequeñas sub-redes, que son virtualmente independientes y están alimentadas por un número prefijado de fuentes. Esta tesis propone un marco de trabajo adecuado en el establecimiento de vías eficientes tanto para dividir la red de abastecimiento en sectores, como para desarrollar nuevas actividades de gestión, aprovechando esta estructura dividida. La propuesta de desarrollo de cada una de estas tareas será mediante el uso de métodos kernel y sistemas multi-agente. El spectral clustering y el aprendizaje semi-supervisado se mostrarán como métodos con buen comportamiento en el paradigma de encontrar una red sectorizada que necesite usar el número mínimo de válvulas de corte. No obstante, sus algoritmos se vuelven lentos (a veces infactibles) dividiendo una red de abastecimiento grande. / Herrera Fernández, AM. (2011). Improving water network management by efficient division into supply clusters [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/11233

Hoy en día los avances en la miniaturización de sistemas electrónicos han impulsado el desarrollo de dispositivos o artefactos que incorporan capacidades computacionales y de comunicación. Estos dispositivos pueden proveer de una serie de servicios en diferentes entornos gracias a su tecnología empotrada, como por ejemplo: reconocimiento de personas, localización de usuarios en un entorno, ajuste automático de la temperatura e iluminación de un entorno, etc. Este potencial de procesamiento y comunicación, está permitiendo crear nuevas aplicaciones distribuidas, donde el rol principal no lo tiene el computador personal, sino los diferentes dispositivos empotrados en el entorno: sensores, interfaces, actuadores, teléfonos móviles, etc., Esto ha generado novedosas áreas de aplicación como: Internet de Cosas (Internet of Things), Computación Móvil, Redes de Sensores, Sistemas Ubícuos, Inteligencia Ambiental, etc. Estos avances han conducido al desarrollo de un nuevo paradigma, computación orientada a la interacción, es decir, la computación ocurre a través de los actos de comunicación entre las entidades. Por lo tanto, es lógico pensar que este paradigma requiere, desde un punto de vista de diseño, el desarrollo de aplicaciones en diferentes plataformas de software y de hardware, debido a lo heterogeneo de los sistemas de computación, lenguajes, sistemas operativos, y objetos (dispositivos físicos: sensores, actuadores, interfaces, etc.) dispersos en el entorno. Dicha heterogeneidad presente en los sistemas ubícuos, representa todo un reto a la hora de diseñarlos. La ingeniería de software basada en sistemas multi-agente, en particular, los sistemas multi-agente abiertos (como las Organizaciones Virtuales), tiene la capacidad de abordar los retos al diseñar sistemas ubícuos. A ello hay que unir, que varias metodologías de desarrollo de software han adoptado el enfoque “dirigido por modelos” (model-driven) para realizar el análisis y el diseño del software. Dicho enfoque puede ser adoptado en los sistemas multi-agente, para mejorar el proceso de desarrollo y la calidad del software basado en agentes. Así mismo, el desarrollo dirigido por modelos proporciona un soporte apropiado para abordar este tipo de sistemas, ya que nos permite el uso de modelos como principal elemento abstracto para el diseño del sistema, por medio de la interconexión de un conjunto de componentes visuales. En este trabajo proponemos el desarrollo de sistemas ubícuos utilizando una organización virtual, creando una Organización Virtual Ubícua, la cual es diseñada usando el enfoque de desarrollo dirigido por modelos. De forma más detallada, este trabajo presenta tres propuestas. La primera, presenta un conjunto de meta-modelos para diseñar una Organización Virtual Ubícua, llamado πVOM, que utiliza conceptos generales que se abstraen de las metodologías y de las plataformas de agentes, lo permite diseñar aplicaciones utilizando abstracciones generales de alto nivel, evitando los detalles de implementación de bajo nivel. Así mismo, se presentan dos modelos de transformaciones, que permiten obtener el modelo de implantación de la organización (con los agentes, entidades y dispositivos), por medio de transformaciones semi-automáticas dadas por la metodología model-driven, reduciendo la brecha entre las fases de diseño y de implementación para este tipo de sistema. La segunda propuesta presenta una arquitectura de implantación que define una estructura de capas funcionales basada en servicios, que soporta la interacción de las entidades de la organización virtual. La arquitectura de implantación permite la interoperabilidad de diferentes entidades, plataformas de software y hardware, proporcionando a los miembros de la organización virtual la capacidad de administrar y controlar los dispositivos del entorno (del sistema ubícuo). La tercera propuesta presenta una plataforma de ejecución de agentes empotrados llamada Andromeda, que permite ejecutar agentes empotrados sobre sistema operativo Android que cumplen con el modelo de agente de πVOM. Los agentes en Andromeda pueden acceder a los dispositivos del entorno, tal y como sucede en los sistemas ubícuos. Las propuestas presentadas fueron evaluadas empíricamente con dos ejemplos, que permiten mostrar sus bondades. / Aguero Medina, J. (2015). Diseño de organizaciones virtuales ubícuas utilizando desarrollo dirigido por modelos [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/52597

[EN] Coordination architectures in multi-agent systems represent an important topic, due to the agents must be organized in order to get a specific objective. In these kinds of systems, robot soccer is shown as an environment with a common frame for research in team coordination. The importance of these kinds of architectures is that the application in other kinds of systems which require coordination. An islanded micro-grid corresponds to a system which can be modeled as multi-agent system, where the distributed energy resources are modeled as agents are coordinated in order to protect the batteries of the energy storage systems, maintaining the common bus regulation. One way to do this throughout coordination strategies, which allow assigning roles and behaviors to the agents, depending on the system conditions. Likewise, the agents must show collaborative behaviors such as making passes in robot soccer, or the equalization of the state of charge for distributed energy storage systems, in order to obtain better results. Multi-agent systems such as robot soccer, that show uncertainties in a hostile environment, require team coordination in order to reach a common goal. One way to achieve this goal is by coordination strategies, which allow role assignment and behavior selection to the players depending on the game conditions. These strategies can present cooperative behaviors among players such as ball passes, in order to obtain better scores against an opponent team. One alternative is the design of hierarchical coordination strategies for an adequate tactic selection, roles assignment and subsequently behavior selection to the players. To this end, one possibility is to use Hierarchical Finite States Machines, due to those allow more flexible and adaptable programming, with a possibility to make changes or modifications. This allows the design of team strategies by an intuitive way according to the control architecture and the rules and specifications of the league where the team plays, in turn performing collaborative behaviors among the players. In this doctoral dissertation are proposed coordination strategies to robot soccer teams, based on tactics, dynamical role assignment and behaviors selection through the use of Finite States Machines, oriented to team architectures with centralized control and global perception. These strategies must allow an intuitive design depending on the team specifications and the rules of the league. These strategies must allow flexibility and adaptability to the necessary changes, such as the number of players, dimensions of the playing field or other changes in the league`s rules. The strategies must be show an adequate response to the failures and allow cooperative behaviors among their players. Lastly, this dissertation presents a structured architecture based on tactics, roles and behaviors for the coordinated operation of islanded microgrids. This grid architecture takes the form of a multi-agent system, and the energy storage and generation units are the team agents. The control strategy is based on the robot soccer strategies presented in this dissertation, which are designed for systems with global perception and centralized control, and in turn determines the changes among operation modes for the distributed energy resources in an islanded microgrid. / [ES] Arquitecturas de coordinación en sistemas multi-agente representa un tópico importante, ya que en este tipo de sistemas los agentes deben ser organizados con el fin de obtener un objetivo específico. Dentro de este tipo de sistemas el fútbol de robots se presenta como un entorno que ofrece un marco común para realizar investigaciones en temas relacionados con temas de coordinación de equipo. La importancia de este tipo de arquitecturas radica en su aplicación en otro tipo de ambientes que requieran coordinación. Un sistema que permite este tipo de aplicaciones consiste en una micro-red eléctrica aislada, donde se modelan las fuentes de energía distribuida como agentes que deben ser coordinados con el fin de proteger las baterías de los sistemas de almacenamiento de energía, manteniendo la regulación del bus común. Una forma de conseguir esto es a través de estrategias de coordinación, las cuales permiten asignar roles y comportamientos a los agentes de la forma más adecuada, dependiendo de las condiciones del sistema. Así mismo, también deben presentar comportamientos colaborativos entre los agentes como la realización de pases en el fútbol de robots o la ecualización del estado de carga de las baterías, con el fin de obtener mejores resultados. Una posibilidad para llevar a cabo esta colaboración entre agentes es el diseño de estrategias de coordinación a través de sistemas jerárquicos para la selección de una adecuada táctica. Adicionalmente se debe permitir la asignación de roles y posteriormente la selección de comportamientos de los agentes. Para esto, una alternativa es el uso de Máquinas Jerárquicas de Estado Finito, ya que presentan flexibilidad y adaptabilidad en su programación, siendo fácilmente expandibles a cambios y modificaciones, permitiendo con esto el diseño de estrategias de coordinación de equipo de manera intuitiva acorde con la arquitectura del equipo y los reglamentos de las ligas donde se compita, y a su vez, que permita también el diseño de comportamientos colaborativos entre sus jugadores. En esta tesis doctoral se proponen estrategias de coordinación para fútbol de robots, mediante la selección de tácticas, la asignación dinámica de roles y la selección de comportamientos, usando Máquinas de Estado Finito, enfocándose en el diseño de arquitecturas de equipo que presentan percepción global y control centralizado, y que permitan un diseño intuitivo dependiendo de las especificaciones de los equipos y de la liga en la que se compite. Estas estrategias deben permitir mayor flexibilidad y adaptabilidad frente a posibles cambios, como por ejemplo en el número de jugadores por equipo, en las dimensiones del campo de juego, o en el reglamento de la correspondiente liga. Igualmente deben poseer robustez ante posibles fallos o perturbaciones, permitiendo también comportamientos colaborativos entre sus integrantes. Finalmente se presenta una propuesta para el control del modo de operación de una micro-red aislada, presentando una arquitectura de red como sistema multi-agente, donde las unidades de almacenamiento y generación de energía son los agentes del equipo, y proponiendo una estrategia de control basada en tácticas, roles y comportamientos. Esta arquitectura está basada en las estrategias de fútbol de robots aportadas en esta tesis y las cuales son diseñadas para sistemas con percepción global y control centralizado, que determina los cambios en el modo de operación para las fuentes distribuidas de energía en la micro-red. / [CA] Arquitectures de coordinació en sistemes multi-agent representa un tòpic important, perquè en aquest tipus de sistemes els agents deuen organitzar-se per a obtindre un objectiu específic. Dins d'aquest tipus de sistemes, el futbol de robots es presenta com un entorn que ofereix un marc comú per a realitzar investigacions en temes relacionats amb la coordinació d'equips. La importància d'aquest tipus d'arquitectures radica en la seua aplicació en altre tipus d'entorns que requereixin coordinació. Un sistema que permet aquest tipus d'aplicació consisteix en una micro-xarxa elèctrica aïllada, a on es modelitzen les diferents fonts d'energia distribuïdes com agents que deuen ser coordinats per a protegir les bateries dels sistemes de acumulació de energia, mantenint la regulació del bus comú. Una manera d'aconseguir això es mitjançant estratègies de coordinació, que permeten assignar papers i comportaments als agents de la millor forma, en funció de las condicions del sistema. Així mateix, també deuen presentar comportaments col·laboratius entre els agents la realització de passes de futbol de robots o la equalització de la carga de les bateries, amb la finalitat d'obtindre millor resultats. Una possibilitat per a aconseguir aquesta col·laboració entre els agents és el disseny d'estratègies de coordinació mitjançant sistemes jeràrquics per a la selecció d'una tàctica adequada. Addicionalment s'ha de permetre l'assignació de rols i, posteriorment, la selecció de comportaments dels jugadors del equip. Per a açò, una alternativa es l'ús de Màquines Jeràrquiques d'Estat Finit, ja que presenten flexibilitat i adaptabilitat en la seua programació fent que siguin fàcilment expansibles a canvis i modificacions, permetent el disseny d'estratègies de coordinació d'equip de manera intuïtiva relacionant-se amb l'arquitectura de l'equip i el reglament de les lliga en la que estiguin competint, al mateix temps permetent el disseny de comportaments de col·laboració entre els jugadors. En aquesta tesis doctoral es proposen estratègies de coordinació per a futbol de robots, mitjançant la selecció de tàctiques, l'assignació dinàmica de rols y la selecció de comportaments, utilitzant Màquines d'Estat Finit, enfocant-se en el disseny d'arquitectures d'equip que presenten percepció global y control centralitzat, i que puguin permetre un disseny intuïtiu depenent de les especificacions dels equips y de la lliga en la que es competeix. Aquestes estratègies han de permetre major flexibilitat i adaptabilitat davant possibles canvis com podrien ser el nombre de jugadors per equip, les dimensions del camp o el reglament de la corresponent lliga. D'igual manera han de tindre robustesa davant possibles fallades o pertorbacions, permetent també comportaments d'aspecte col·laboratiu entre els seus integrants. En aquesta tesis, finalment es presenta un a proposta per al control del mode d'operació d'una micro-xarxa aïllada, presentant una arquitectura de xarxa com a sistema multi-agent, on les unitats d'emmagatzemament i generació d'energia són els agents del equip, i proposant una estratègia de control basada en tàctiques, rols i comportaments. Aquesta arquitectura està basada en les estratègies de futbol de robots aportades en aquesta tesis i que son dissenyades per a sistemes amb percepció global i control centralitzat, el qual determina els canvis en la forma d'operació per a les fonts distribuïdes d'energia en la micro-xarxa. / Guarnizo Marín, JG. (2016). Arquitecturas Centralizadas de Coordinación. Extrapolación del Fútbol de Robots al Control de Modo de Operaciones de Micro-Redes [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/68478

[EN] In recent years, within the field of mobile robotics, distributed architectures are becoming the fundamental pillar on which to develop modular, scalable and reusable algorithms that offer flexible solutions that can be applied easily and quickly to any platform with minimal changes in the software. Thus avoiding to reinvent the wheel facing the same problem again and again with each different type of robot on which it wants to work. Within this type of architecture, the multi-agent systems have the ability to orient their programming to modular behaviors and offer a well defined communication management. The ability for a group of robots to communicate with each other with some ease, gives new information to the agents that the sensoring hardware may sometimes not be able to detect, and that can be used to propose new or complementary solutions to the already defined within the area. This is exactly the reason and the challenge faced by this work, applied to mobile robots with limited resources. The first contribution of this thesis lies in the development of a control middleware which allows the use of two important distributed frameworks: JADE oriented multi-agent software development and ROS oriented distributed robotic software. The middleware was integrated into the set of robots available for testing and it was used as the basis of the architecture of most simulated and practical experiments that are presented. Once the established and detailed the hardware and software used, the new algorithms developed for local and global localization of mobile robots with limited resources, based on filters of sensory fusion and geometric correspondences are established. In addition, the benefits are evaluated using the principles of control and sampling based on events and taking as a starting point the cascade algorithms based on time. Based on these localization algorithms, navigation and coordination methodologies are described for groups of cooperative robots, where the communications between agents are the basis of success and where satisfactory results are observed both individually by robot and globally on the set Of robots. When working on a scenario shared by various mobile robots navigating, one of the most critical issues is to get the robots do not collide with each other. For this reason, another of the most important contributions of this work has been the development of an algorithm of detection and avoidance of collisions based on the consensus and agreement between robots through the point-to-point communications between them. For cases when a robot collided with just another robot, and for cases where multiple collisions occurred at the same time. Finally, the conclusions and the possible lines of work on which to continue researching and developing from the results obtained in this thesis are presented. / [ES] En los últimos años, dentro del campo de la robótica móvil, las arquitecturas distribuidas se están convirtiendo en el pilar fundamental sobre el cual desarrollar algoritmos modulares, escalables y reaprovechables que ofrezcan soluciones flexibles aplicables fácil y rápidamente a cualquier plataforma con unos cambios mínimos en el software, evitando de este modo reinventar la rueda enfrentándose al mismo problema una y otra vez con cada tipo distinto de robot sobre el que se desea trabajar. Dentro de este tipo de arquitectura los sistemas multi-agente permiten orientar su programación hacia comportamientos modulares y ofrecen una gestión de comunicaciones bien definida. La habilidad de que un grupo de robots pueda comunicarse entre sí con cierta facilidad, otorga información nueva a los agentes que el hardware de sensorización puede en ocasiones no ser capaz de detectar, y que puede ser utilizada para proponer nuevas soluciones alternativas o complementarias a las ya definidas dentro del área. Este es exactamente el motivo y el reto al que se enfrenta este trabajo, aplicado a robots móviles de recursos limitados. La primera aportación de esta tesis radica en el desarrollo de un middleware de control el cual permite el uso de dos importantes frameworks distribuidos: JADE orientado al desarrollo software multi-agente y ROS orientado a software robótico distribuido. El middleware se integró en el conjunto de robots disponibles para pruebas y se utiliza como base de la arquitectura de la mayoría de experimentos simulados y prácticos que se presentan. Establecido y detallado el hardware y el software a utilizar, se establecen los nuevos algoritmos desarrollados para la localización local y global de robots móviles de recursos limitados, basados en filtros de fusión sensorial y en correspondencias geométricas. Además se evalúan las prestaciones utilizando los principios de control y muestreo basados en eventos y tomando como punto de partida los algoritmos en cascada basados en el tiempo. Partiendo de dichos algoritmos de localización, se describen metodologías de navegación y coordinación de grupos de robots cooperativos, donde las comunicaciones entre agentes son la base del éxito y donde se observan resultados satisfactorios tanto a nivel individual por robot, como a nivel global sobre el conjunto de robots. Cuando se trabaja sobre un escenario compartido por diversos robots móviles navegando, una de las problemáticas más críticas es conseguir que los robots no choquen entre ellos. Por este motivo, otra de las aportaciones más importantes de este trabajo ha sido el desarrollo de un algoritmo de detección y evasión de colisiones basado también en el consenso y el acuerdo entre robots a través de las comunicaciones punto a punto entre ellos, el cual se ha definido tanto para situaciones donde un robot colisionaba sólo con otro robot, como para casos en los que ocurrían múltiples colisiones al mismo tiempo. Finalmente se exponen las conclusiones y las posibles líneas de trabajo sobre las que seguir investigando y desarrollando a partir de los resultados obtenidos en la presente tesis. / [CAT] En els últims anys, dins del camp de la robòtica mòbil, les arquitectures distribuïdes s'estan convertint en el pilar fonamental sobre el qual desenvolupar algorismes modulars, escalables i reaprovechables que oferisquen solucions flexibles aplicables fàcil i ràpidament a qualsevol plataforma amb uns canvis mínims en el programari, evitant d'aquesta manera reinventar la roda enfrontant-se al mateix problema una vegada i una altra amb cada tipus diferent de robot sobre el qual es desitja treballar. Dins d'aquest tipus d'arquitectura els sistemes multi-agent permeten orientar la seua programació cap a comportaments modulars i ofereixen una gestió de comunicacions ben definida. L'habilitat de que un grup de robots puga comunicar-se entre si amb certa facilitat, atorga informació nova als agents que el hardware de sensorització pot en ocasions no ser capaç de detectar, i que pot ser utilitzada per a proposar noves solucions alternatives o complementàries a les ja definides dins de l'àrea. Aquest és exactament el motiu i el repte al que s'enfronta aquest treball, aplicat a robots mòbils de recursos limitats. La primera aportació d'aquesta tesi radica en el desenvolupament d'un middleware de control el qual permet l'ús de dos importants frameworks distribuïts: JADE orientat al desenvolupament de la programació multi-agent i ROS orientat a la programació robòtica distribuïda. El middleware es va integrar en el conjunt de robots disponibles per a proves i s'utilitza com a base de l'arquitectura de la majoria d'experiments simulats i pràctics que es presenten. Establit i detallat el hardware i el software a utilitzar, s'estableixen els nous algorismes desenvolupats per a la localització local i global de robots mòbils de recursos limitats, basats en filtres de fusió sensorial i en correspondències geomètriques. A més s'avaluen les prestacions utilitzant els principis de control i mostreig basats en esdeveniments i prenent com a punt de partida els algorismes en cascada basats en el temps. Partint d'aquests algorismes de localització, es descriuen metodologies de navegació i coordinació de grups de robots cooperatius, on les comunicacions entre agents són la base de l'èxit i on s'observen resultats satisfactoris tant a nivell individual per robot, com a nivell global sobre el conjunt de robots. A més, quan es treballa sobre un escenari compartit per diversos robots mòbils navegant, una de les problemàtiques més crítiques és aconseguir que els robots no xoquen entre ells. Per aquest motiu, una altra de les aportacions més importants d'aquest treball ha sigut el desenvolupament d'un algorisme de detecció i evasió de col·lisions basat també en el consens i l'acord entre robots a través de les comunicacions punt a punt entre ells, el qual s'ha definit tant per a situacions on un robot col·lisionava només amb un altre robot, com per a casos en els quals ocorrien múltiples col·lisions al mateix temps. Finalment s'exposen les conclusions i les possibles línies de treball sobre les quals seguir investigant i desenvolupant a partir dels resultats obtinguts en la present tesi. / Soriano Vigueras, Á. (2017). Integración de sistemas multi-agente en plataformas embebidas heterogéneas con recursos limitados para tareas de localización y coordinación en detección y evasión de colisiones en robótica móvil [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/86174

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.

Dissertação apresentada para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores (Área de especialização de Informática Industrial), na Faculdade de Engenharia da Universidade do Porto, sob a orientação do Professor Doutor Raúl Filipe Teixeira de Oliveira