Evolutionary algorithms are machine learning techniques that can be used in many applications of optimization problems in various fields. Banking route planning is a combinatorial optimization problem. The paper proposes a genetic algorithm for planning routes for bank employees. Computational experiments have been carried out, and the effectiveness of the proposed method has been shown. / Эволюционные алгоритмы - это методы машинного обучения, которые можно использовать во многих приложениях задач оптимизации в различных областях. Планирование банковских маршрутов представляет собой задачу комбинаторной оптимизации. В работе предложен генетический алгоритм планирования маршрутов банковских работников. Проведены вычислительные эксперименты, показана эффективность предложенного метода.

Indoor Positioning Systems (IPS) using the existing WLAN have won growing interest in the last years, it can be a perfect supplement to provide location information of users in indoor environments where other positioning techniques such as GPS, are not much effective. The thesis manuscript proposes a new approach to define a WLAN-based indoor positioning system (WLAN-IPS) as a combinatorial optimization problem to guarantee the requested communication quality while optimizing the positioning error. This approach is characterised by several difficult issues we tackled in three steps.At first, we designed a WLAN-IPS and implemented it as a test framework. Using this framework, we looked at the system performance under various experimental constraints. Through these experiments, we went as far as possible in analysing the relationships between the positioning error and the external environmental factors. These relationships were considered as evaluation indicators of the positioning error. Secondly, we proposed a model that defines all major parameters met in the WLAN-IPS from the literature. As the original purpose of the WLAN infrastructures is to provide radio communication access, we introduced an additional purpose which is to minimize the location error within IPS context. Two main indicators were defined in order to evaluate the network Quality of Service (QoS) and the positioning error for Location-Based Service (LBS). Thirdly, after defining the mathematical formulation of the optimisation problem and the key performance indicators, we proposed a mono-objective algorithm and a multi-objective algorithm which are based on Tabu Search metaheuristic to provide good solutions within a reasonable amount of time. The simulations demonstrate that these two algorithms are highly efficient for the indoor positioning optimization problem.

Submitted by Raildo Barros Rodrigues (raildo.barros@gmail.com) on 2018-09-24T15:10:31Z No. of bitstreams: 1 Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2926580 bytes, checksum: 6799724ac48abd21caecd50cf5156480 (MD5) / Rejected by Pamella Benevides Gonçalves null (pamella@feg.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo Verificar formatação com a equipe da biblioteca. Agradecemos a compreensão. on 2018-09-24T18:49:58Z (GMT) / Submitted by Raildo Barros Rodrigues (raildo.barros@gmail.com) on 2018-09-25T16:48:30Z No. of bitstreams: 2 Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2926580 bytes, checksum: 6799724ac48abd21caecd50cf5156480 (MD5) Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) / Approved for entry into archive by Pamella Benevides Gonçalves null (pamella@feg.unesp.br) on 2018-09-25T18:15:24Z (GMT) No. of bitstreams: 1 rodrigues_rb_me_guara.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) / Made available in DSpace on 2018-09-25T18:15:24Z (GMT). No. of bitstreams: 1 rodrigues_rb_me_guara.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) Previous issue date: 2018-09-20 / Outra / Esta dissertação trata da construção de um modelo matemático para a elaboração do quadro de horários dos cursos de graduação do CBV/IFRR. A programação de horários é um problema de otimização combinatória estudado há anos pela Pesquisa Operacional e, em termos de complexidade computacional, é tido como NP-Completo, sendo assim, é um problema que exige grande capacidade de processamento. A elaboração do quadro de horários em qualquer instituição de ensino é complexa e demanda tempo para os responsáveis por essa atividade, pois as necessidades dos professores e alunos devem ser atendidas e devem-se evitar conflitos nos horários dos professores. A instituição estudada nesta dissertação assim como outras instituições, possui particularidades institucionais, dessa forma, uma formulação geral do problema acaba não lhe sendo útil. O CBV/IFRR realiza a elaboração dos horários de forma manual, por meio de planilha eletrônica e realização de reuniões entre os gestores, o que torna difícil encontrar uma solução factível. Sendo assim, foi necessária a realização de pesquisa científica para encontrar métodos que poderiam ser aplicados ao problema. Assim, este trabalho teve como objetivo desenvolver um modelo de Programação Matemática que permitisse a elaboração dos horários para cursos de graduação do CBV/IFRR. Utilizou-se entrevistas com as Coordenações de Cursos para obtenção das informações acerca do problema tratado, tais como restrições e prioridades a serem atendidas com a programação de aulas para professores. Estas informações serviram de base para a construção do modelo conceitual, que foi utilizado para elaboração do modelo matemático final, que foi implementado na linguagem de alto nível GAMS® e resolvido pelo solver CPLEX®. Os testes do modelo foram realizados otimizando uma instância com dados reais da instituição estudada. Os resultados obtidos da otimização foram satisfatórios, pois foi possível encontrar uma solução ótima para a instância em tempo computacional adequado, com todas as restrições, impostas pelas características peculiares do problema tratado, sendo respeitadas e as prioridades estabelecidas pelas Coordenações de Cursos atendidas. / This dissertation deals with the construction of a mathematical model for the elaboration of the timetable of the undergraduate courses of the CBV/IFRR. Time scheduling is a combinatorial optimization problem that has been studied for years by Operational Research and, in terms of computational complexity, is considered as NP-Complete, so it is a problem that requires large processing capacity. The elaboration of the timetable in any educational institution is complex and takes time for those responsible for this activity, because the needs of teachers and students must be met and avoid conflicts in the schedules of teachers. The institution studied in this dissertation as well as other institutions, has institutional features, so a general formulation of the problem ends up being of no use to it. The CBV/IFRR performs the elaboration of the schedules manually, through a spreadsheet and holding meetings between managers, which makes it difficult to find a feasible solution. Thus, it was necessary to carry out scientific research to find methods that could be applied to the problem. Thus, this work had the objective of developing a Mathematical Programming model that allowed the elaboration of the schedules for the undergraduate courses of the CBV/IFRR. We used interviews with the Course Coordinators to obtain information about the problem, such as constraints and priorities to be met with the programming of classes for teachers. This information was the basis for the construction of the conceptual model, which was used to elaborate the final mathematical model, which was implemented in the GAMS® high-level language and solved by the CPLEX® solver. The tests of the model were performed optimizing an instance with real data of the studied institution. The results obtained from the optimization were satisfactory, since it was possible to find an optimal solution for the instance in adequate computational time, with all the restrictions imposed by the peculiar characteristics of the problem, being respected and the priorities established by the Coordination of Courses attended.

No description available.

La localisation des personnes et des objets à l’intérieur des bâtiments basée sur les réseaux WLAN connaît un intérêt croissant depuis quelques années ; ce système peut être un parfait complément pour fournir des informations de localisation statique ou dynamique dans des environnements où les techniques de positionnement telles que GPS ne sont pas efficaces. Le manuscrit de thèse propose une nouvelle approche pour définir un système WLAN de positionnement indoor (WLAN-IPS) comme un problème d'optimisation combinatoire afin de garantir à la fois une qualité de communication et une minimisation de l'erreur de positionnement via le réseau. Cette approche est caractérisée par plusieurs questions difficiles que nous abordons en trois étapes.Dans un premier temps, nous avons conçu un réseau WLAN-IPS et mis en œuvre une plateforme de test. Nous avons examiné la performance du système sous diverses contraintes expérimentales et nous nous sommes penchés sur l'analyse des relations entre l'erreur de positionnement et les facteurs environnementaux externes. Ces relations ont permis de proposer des indicateurs pour évaluer l'erreur de positionnement. Ensuite nous avons proposé un modèle physique qui définit tous les paramètres majeurs rencontrés en WLAN-IPS à partir de la littérature. L'objectif initial des infrastructures WLAN étant de fournir un accès radio de qualité au réseau, nous avons introduit un objectif supplémentaire qui est de minimiser l'erreur de localisation dans le contexte IPS. Deux indicateurs principaux ont été définis afin d'évaluer la qualité de service (QoS) et l'erreur de localisation pour LBS (Location-Based Services). Enfin après avoir défini la formulation mathématique du problème d'optimisation et les indicateurs clés de performance, nous avons proposé un algorithme mono-objectif et un algorithme multicritère basés sur Tabu Search et Variable Neighborhood Search pour fournir des bonnes solutions en temps raisonnable. Les simulations montrent que ces deux algorithmes sont très efficaces pour le problème d'optimisation que nous avons posé. / Indoor Positioning Systems (IPS) using the existing WLAN have won growing interest in the last years, it can be a perfect supplement to provide location information of users in indoor environments where other positioning techniques such as GPS, are not much effective. The thesis manuscript proposes a new approach to define a WLAN-based indoor positioning system (WLAN-IPS) as a combinatorial optimization problem to guarantee the requested communication quality while optimizing the positioning error. This approach is characterised by several difficult issues we tackled in three steps.At first, we designed a WLAN-IPS and implemented it as a test framework. Using this framework, we looked at the system performance under various experimental constraints. Through these experiments, we went as far as possible in analysing the relationships between the positioning error and the external environmental factors. These relationships were considered as evaluation indicators of the positioning error. Secondly, we proposed a model that defines all major parameters met in the WLAN-IPS from the literature. As the original purpose of the WLAN infrastructures is to provide radio communication access, we introduced an additional purpose which is to minimize the location error within IPS context. Two main indicators were defined in order to evaluate the network Quality of Service (QoS) and the positioning error for Location-Based Service (LBS). Thirdly, after defining the mathematical formulation of the optimisation problem and the key performance indicators, we proposed a mono-objective algorithm and a multi-objective algorithm which are based on Tabu Search metaheuristic to provide good solutions within a reasonable amount of time. The simulations demonstrate that these two algorithms are highly efficient for the indoor positioning optimization problem.

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.