Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T19:39:00Z (GMT). No. of bitstreams: 1 Takahata_AndreKazuo_M.pdf: 1113954 bytes, checksum: 18f4c96c943dced30f100b8a56c97258 (MD5) Previous issue date: 2009 / Resumo: Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção de soluções de alta qualidade em tempo reduzido. As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas e apresenta resultados de testes em instâncias da literatura. / Abstract: In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to combine the flexibility offered by heuristics and the expressive advances achieved in the development of optimization solvers so as to obtain high quality solutions in a short time. The proposed heuristics are based on rounding solutions located on the rays of a cone whose vertex is associated with the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is motivated by its geometric appeal and by the success of similar approaches in heuristics for solving combinatorial problems. This work describes the development and implementation of the heuristics and presents computational tests on instances from literature. / Mestrado / Automação / Mestre em Engenharia Elétrica

Na maioria das cidades brasileiras, o ônibus é o principal, senão o único meio de transporte público de passageiros, atendendo àqueles que não possuem carro, mas também contribuindo para reduzir os congestionamentos e, dessa forma, melhorando a qualidade de vida. A fim de incentivar a sua utilização em muitas cidades, inúmeras medidas devem ser tomadas, incluindo um esforço para reduzir custos e, em decorrência, as tarifas pagas pelos usuários, definindo uma tarifa justa que privilegie a população de baixa renda, na qual estão inseridos uma grande parcela dos seus usuários. Nesse contexto, a programação eficiente de veículos e tripulações é essencial para essa redução de custos, uma vez que representa uma parcela significativa dos mesmos. Este trabalho trata do Problema de Programação de Veículos e de Tripulantes de Ônibus, em que ambas as programações são determinadas simultaneamente e de maneira integrada. Durante a realização deste trabalho, foi desenvolvido um programa computacional em C++, o qual implementa a metaheurística Busca em Vizinhança Variável (VNS) utilizada para resolver esse problema complexo. São apresentados resultados de experimentos computacionais com dados reais de uma empresa de transporte coletivo. Os resultados obtidos comprovam a eficácia da abordagem integrada em comparação com quatro outras abordagens encontradas na literatura. / In most Brazilian cities, bus has become the main, and oftentimes the only mean of public transportation, not only servicing those who cannot afford to have a car, but also helping to reduce traffic congestion and thus improving quality of life. In order to encourage the bus usage in many cities, several measures must be taken, including an effort to reduce overall costs and, as a result, fares paid by the users, thus benefit mainly low income users which represent a major part of its users. In this context, an efficient scheduling of vehicles and crews is essential to achieve cost reduction, since it accounts for a major part of overall costs. In this paper, we deal with the Bus Vehicle Crew Scheduling Problem, in which bus and crew schedules are simultaneously determined in an integrated approach. We propose an approach based on Variable Neighborhood search to solve this complex problem, which was implemented in C++. Computational results for real-world problems are presented, showing the effectiveness of this novel approach in comparison with other four approaches found in the literature.

Orientador: Orlando Fontes Lima Júnior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo / Made available in DSpace on 2018-08-26T02:20:07Z (GMT). No. of bitstreams: 1 Paiva_EduardoPereiraLimade_M.pdf: 15061304 bytes, checksum: 0389c666bf0c3316bd357dbeeb9b2c54 (MD5) Previous issue date: 2014 / Resumo: O serviço de entrega por bicicleta representa um mercado de prestação de serviços promissor e em crescimento. O transporte de carga movido por propulsão humana tem recebido bastante atenção por ser capaz de reduzir custos e emissão de poluentes em operações logísticas de curta distância e por aliviar a quantidade de veículos motorizados utilizados em centros urbanos. A distribuição de pequenas encomendas por bicicleta em área urbana de pequeno porte foi objeto deste trabalho. Com base nos métodos de Districting (divisão por distritos), de Clarke e Wright e Diagramas de Voronoi, realizou-se um estudo de caso envolvendo a distribuição de malotes no campus de Campinas da UNICAMP (Universidade Estadual de Campinas). Os resultados dessas aplicações foram comparados entre eles e em relação à situação existente, e as dificuldades e restrições para a implantação de serviços de bicicletas foram exploradas considerando-se a viabilidade econômica e social da substituição do veículo motorizado pelo veículo movido a propulsão humana / Abstract: The bicycle delivery service is a promising and growing service delivery market. Human propelled load transportation has received great attention these days for being able to reduce costs and pollution emission in short distance logistics operations, as well as to diminish the amount of motor vehicles in urban centers. The subject of this paper is the distribution of small orders by bicycle in small urban areas. Based on the Districting method (division by districts), Clarke and Wright Algorithm, and Voronoi Diagrams, a case study was developed considering the distribution of pouches in the campus of Campinas State University (Universidade Estadual de Campinas - UNICAMP), São Paulo, Brazil. The results of these applications were compared among themselves and to the actual situation, and the difficulties and restrictions imposed to the implementation of bicycle service delivery were explored from the point of view of the economic and social viability of motor vehicle replacement for human propelled vehicle / Mestrado / Transportes / Mestre em Engenharia Civil

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T14:30:07Z (GMT). No. of bitstreams: 1 Mortati_CamilaFrederico_M.pdf: 341927 bytes, checksum: 5b1a9d9a8e6c0852c0e86425852e2584 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento periódico de veículos, que consiste em designar uma combinação de dias de visitas a cada cliente, e definir as rotas de veículos em cada dia de um horizonte de planejamento, de forma a minimizar o custo ou a duração total das rotas. Um algoritmo de busca tabu é proposto para a resolução do problema. A história da busca tabu, usada para guiar o processo de busca, é representada através de memórias de curto e longo prazo. A eficiência das estratégias sugeridas para diversificação e intensificação, associadas à memória de logo prazo, são verificadas experimentalmente. O desempenho do algoritmo de busca tabu é testado computacionalmente em problemas da literatura. Um procedimento de busca tabu proposto na literatura é implementado e comparado com o algoritmo aqui proposto / Abstract: This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this work / Mestrado / Automação / Mestre em Engenharia Elétrica

The p-Median problem (PMP) is one of the most widely applied location problems in urban and regional planning to support spatial decision-making. As an NP-hard problem, the PMP remains challenging to solve optimally, especially for large-sized problems. This research focuses on developing geocomputational approaches to improve the effectiveness and efficiency of solving the PMP. This research also examines existing PMP methods applied to choropleth mapping and proposes a new approach to address issues associated with uncertainty. Chapter 2 introduces a new algorithm that solves the PMP more effectively. In this chapter, a method called the spatial-knowledge enhanced Teitz and Bart heuristic (STB) is proposed to improve the classic Teitz and Bart (TB) heuristic.. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and candidate facility sites. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. Chapter 3 provides a high performance computing (HPC) based heuristic, Random Sampling and Spatial Voting (RSSV), to solve large PMPs. Instead of solving a large-sized PMP directly, RSSV solves multiple sub-PMPs with each sub-PMP containing a subset of facility and demand sites. Combining all the sub-PMP solutions, a spatial voting strategy is introduced to select candidate facility sites to construct a PMP for obtaining the final problem solution. The RSSV algorithm is well-suited to the parallel structure of the HPC platform. Tests with the BIRCH dataset show that RSSV provides high-quality solutions and reduces computing time significantly. Tests also demonstrate the dynamic scalability of the algorithm; it can start with a small amount of computing resources and scale up or down when the availability of computing resources changes. Chapter 4 provides a new classification scheme to draw choropleth maps when data contain uncertainty. Considering that units in the same class on a choropleth map are assigned the same color or pattern, the new approach assumes the existence of a representative value for each class. A maximum likelihood estimation (MLE) based approach is developed to determine class breaks so that the overall within-class deviation is minimized while considering uncertainty. Different methods, including mixed integer programming, dynamic programming, and an interchange heuristic, are developed to solve the new classification problem. The proposed mapping approach is then applied to map two American Community Survey datasets. The effectiveness of the new approach is demonstrated, and the linkage of the approach with the PMP method and the Jenks Natural Breaks is discussed.

With increasing size of sequence databases heuristic search approaches have become necessary. Hidden Markov models are the best performing search methods known today with respect to discriminative power, but are too time complex to be practical when searching in large sequence databases. In this report, heuristic algorithms that reduce the search space before searching with traditional search algorithms of hidden Markov models are presented and experimentally validated. The results of the validation show that the heuristic search algorithms will speed up the searches without decreasing their discriminative power.

As an increasing number of people are logging on to the internet to do their shopping, it is imperative for a site to be accessible and usable. Nielsen’s heuristic method is one esteemed method that many web site developers use in their design work. One study suggests that online shopping needs most improvement with the heuristics “User control and freedom” where an undo button often is lacking and in ‘Help and Documentation’ where the user may not easily switch between their work and the help. The study, however, has been made on grocery shops alone. The following study adopts the results of the past study as hypotheses and investigates if they hold true for another type of online shopping site – women’s apparel. The results of the study confirm that these two heuristics indeed are the two most troublesome. However, for the biggest usability disaster under each, the results are either inapplicable or only lend weak support. The following results lend more support to a possible generalization for all online sites and better awareness among software developers of online shopping sites. Yet a more consistent base of common usability disasters under these two specific heuristics needs to be developed.

Today, web, Internet, mobile and other ambient technologies engage in persuasive interaction with people. The technology designed to reinforce and change user’s attitude or behaviors or both through persuasion and social influence are persuasive technologies. Recently, persuasive systems and services are becoming increasingly abundant and ubiquitous. Evaluation of these systems is a challenging endeavor and typically requires a simple and efficient method. Nielsen suggests heuristic evaluation as a method for intuitive, inexpensive and easy evaluation of a user interface design. The purpose of this thesis is to examine heuristic evaluation as a method to evaluate the persuasive potential of software programs. The Heuristics used were operationalized version of Fogg’s persuasive design principles. Software programs MS Word, MS PowerPoint, Counter-Strike, The Sims, Stone and Plan Eat Smile were chosen with the goal of measuring their ability to change behavior or attitude of users. The Evaluation was performed on the software programs using three evaluators and the test results indicated that they possess significant persuasive potential. It was concluded that the set of heuristics which were developed can be used to perform summative heuristic evaluation and the method used was helpful in evaluating the persuasive potential of software programs.

Rectilinear crossing number of a graph is the number of crossing edges in a drawing with all straight line edges. The problem of drawing an n-vertex complete graph such that its rectilinear crossing number is minimum is known to be an NP-Hard problem. In this thesis, we present a heuristic that attempts to achieve the theoretical lower bound value of the rectilinear crossing number of a n+1 vertex complete graph from that of n vertices. Our algorithm accepts an optimal or near-optimal rectilinear drawing of Kn graph as input and tries to place a new node such that the crossing number is minimized. Based on prior optimal drawings of Kn, we make an empirical observation that the optimal drawings are triangular in shape. The proposed heuristic has three steps: (1) Given the optimal or near-optimal drawing of Kn, the outer triangle is determined; (2) A set of candidate positions for the (n+1)th node is determined by ensuring none of them are collinear with two or more nodes in the graph; and (3) the best drawing with least rectilinear crossing number is chosen based on the drawings corresponding to the candidate position. A loose bound on the worst-case time complexity of the proposed algorithm is O(n7). The heuristic is not guaranteed to yield optimal solution as the search space is constrained by the input graph. In our experimental results, we obtained optimal results for complete graphs of up to n=27.

Peridynamics (PD), a reformulation of the Classical Continuum Mechanics (CCM), is a new and promising meshless and nonlocal computational method in solid mechanics. To permit discontinuities, the PD integro-differential equation contains spatial integrals and time derivatives. PD can be considered as the continuum version of molecular dynamics. This feature of PD makes it a good candidate for multi-scale analysis of materials. Concurrently, the topology optimization has also been rapidly growing in view of the need to design lightweight and high performance structures. Therefore, this thesis presents the potential for a peridynamics-based topology optimization approach. To avoid the gradient calculations, a heuristic topology optimization method is employed. The minimization of the PD strain energy density is set as the objective function. The structure is optimized based on a modified solid isotropic material with a penalization approach and a projection scheme is utilized to obtain distinct results. Several test cases have been studied to analyze the suitability of the proposed method in topology optimization. / Graduate