171 |
On efficient ordered binary decision diagram minimization heuristics based on two-level logic.January 1999 (has links)
by Chun Gu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 69-71). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.3 / Chapter 2 --- Definitions --- p.7 / Chapter 3 --- Some Previous Work on OBDD --- p.13 / Chapter 3.1 --- The Work of Bryant --- p.13 / Chapter 3.2 --- Some Variations of the OBDD --- p.14 / Chapter 3.3 --- Previous Work on Variable Ordering of OBDD --- p.16 / Chapter 3.3.1 --- The FIH Heuristic --- p.16 / Chapter 3.3.2 --- The Dynamic Variable Ordering --- p.17 / Chapter 3.3.3 --- The Interleaving method --- p.19 / Chapter 4 --- Two Level Logic Function and OBDD --- p.21 / Chapter 5 --- DSCF Algorithm --- p.25 / Chapter 6 --- Thin Boolean Function --- p.33 / Chapter 6.1 --- The Structure and Properties of thin Boolean functions --- p.33 / Chapter 6.1.1 --- The construction of Thin OBDDs --- p.33 / Chapter 6.1.2 --- Properties of Thin Boolean Functions --- p.38 / Chapter 6.1.3 --- Thin Factored Functions --- p.49 / Chapter 6.2 --- The Revised DSCF Algorithm --- p.52 / Chapter 6.3 --- Experimental Results --- p.54 / Chapter 7 --- A Pattern Merging Algorithm --- p.59 / Chapter 7.1 --- Merging of Patterns --- p.60 / Chapter 7.2 --- The Algorithm --- p.62 / Chapter 7.3 --- Experiments and Conclusion --- p.65 / Chapter 8 --- Conclusions --- p.67
|
172 |
Scatter Search para problemas de roterização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas. / Scatter search for Heterogeneous Fleet vehicle routing problem with Time Windows and Split Deliveries.Belfiore, Patrícia Prado 03 March 2006 (has links)
Esta tese estuda a implementação de heurísticas e da metaheurística scatter search (SS) em um problema de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries HFVRPTWSD). O HFVRPTWSD é uma combinação do problema de roteirização com frota heterogênea (HFVRP), problema de roteirização de veículos com janelas de tempo (VRPTW) e problema de roteirização com entregas fracionadas (VRPSD). O problema é baseado em um único depósito, a demanda dos clientes pode ser maior que a capacidade dos veículos e, além das restrições de janelas de tempo, há também restrições de capacidade dos veículos e restrições quanto ao tipo de veículo. O VRPSD foi introduzido na literatura por Dror e Trudeau em 1989. No problema de roteirização de veículos com entregas fracionadas, cada cliente pode ser abastecido por mais de um veículo, enquanto no problema clássico de roteirização de veículos (VRP), cada cliente é atendido por um único veículo. Desta forma, para o VRPSD, além dos roteiros de entrega, deve-se determinar a quantidade entregue a cada cliente em cada veículo. Todos os problemas de roteirização com entregas fracionadas encontrados na literatura (VRPSD e suas extensões) têm como característica frota homogênea. O problema estudado neste trabalho difere, portanto, de todos os problemas de roteirização com entregas fracionadas da literatura, pois tem, como característica, frota heterogênea. O mesmo raciocínio vale para problemas de roteirização de veículos com frota heterogênea. Os modelos são aplicados em uma rede de varejo no Brasil que é abastecida a partir de um centro de distribuição. A rede compõe um total de 519 lojas distribuídas em 12 estados do país. As heurísticas e a metaheurística scatter search também são aplicadas em três conjuntos de problemas encontrados na literatura (SOLOMON, 1987; HO E HAUGLAND, 2004; LIU E SHEN, 1999), com o objetivo de avaliar o desempenho dos algoritmos para cada problema. O problema consiste em determinar, a cada dia, como alocar os caminhões às lojas, a quantidade de carga em cada caminhão a ser entregue em cada uma das lojas, qual o melhor roteiro e o tempo de início de atendimento do primeiro cliente da rota, de forma a minimizar o custo total de distribuição, garantindo que a demanda das lojas seja atendida e as demais restrições do problema sejam respeitadas. Para a resolução do VRPSD e suas extensões, a única metaheurística encontrada na literatura foi busca tabu. Para o problema de roteirização com frota heterogênea e suas extensões, foram implementadas apenas as metaheurísticas busca tabu e BATA (Back-Tracking Adaptative Threshold Accepting). As estratégias de solução propostas no presente trabalho consistem na implementação de heurísticas construtivas e da metaheurística scatter search. As soluções iniciais de SS são obtidas através da implementação de quatro heurísticas construtivas: heurística de economias, heurística de inserção seqüencial baseada nas idéias de Solomon (1987), heurística de inserção seqüencial baseada nas idéias de Ho e Haugland (2004) e adaptação da heurística de inserção seqüencial de Dullaert et al. (2002). Para o caso real, foi possível uma redução no custo total da frota comparado com a solução atual da empresa. Para algumas instâncias dos três conjuntos de problemas da literatura, os algoritmos apresentaram resultados similares ou superiores às melhores soluções encontradas. / This thesis studies the implementation of heuristics and scatter search (SS) metaheuristic in a Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (HFVRPTWSD). The HFVRPTWSD is a combination of Heterogeneous Fleet Vehicle Routing Problem (HFVRP), Vehicle Routing Problem with Time Windows (VRPTW) and Vehicle Routing Problem with Split Deliveries (VRPSD). The problem is based in a single depot, the demand of each client can be greater than the vehicles capacity and beyond the time windows constraints, and there are also constraints on the vehicle capacity and vehicles type. The VRPSD was introduced in the literature by Dror e Trudeau in 1989. In the split deliveries vehicle routing problem, each client can be supplied by more than one vehicle; while in a classic vehicle routing problem (VRP) each client is supplied by only one vehicle. Thus, for the VRPSD, besides the delivery routes, the amount to be delivered to each client in each vehicle must also be determined. All the split delivery vehicle routing problems researched in the literature (VRPSD and its extensions) have as a characteristic the homogeneous fleet. Therefore, the problem studied differs from the split deliveries vehicle routing problems of the literature because it has a heterogeneous fleet. The same reasoning can be applied in heterogeneous fleet vehicle routing problem. The models will be applied in a retail market in Brazil that is supplied by a distribution center. The market has 519 stores distributed in 12 Brazilian states. The heuristics and the scatter search metaheuristic will also be applied in three benchmark problems (SOLOMON, 1987; HO AND HAUGLAND, 2004; LIU AND SHEN, 1999), aiming to evaluate the design of the algorithms for each problem. The problem consists in determining, each day, how to allocate the trucks to the stores, the amount to be delivered in each truck to each client, which one is the best route and the initial time for attending the first client, with the aim of minimizing the total distribution cost, attending the clients demand and respecting all the problems constraints. For the VRPSD and its extensions, the only metaheuristic implemented in the literature was tabu search. For the heterogeneous fleet vehicle routing problem and its extensions, only the tabu search and BATA (Back-Tracking Adaptative Threshold Accepting) metaheuristics have been implemented. The strategies proposed here consist in the implementation of constructive heuristics and the scatter search metaheuristic. The initial solutions of SS are obtained with the implementation of four constructive heuristics: saving heuristics, sequential insertion heuristic based on the ideas of Solomon (1987), sequential insertion heuristic based on the ideas of Ho e Haugland (2004) and adaptation of the sequential insertion heuristic of Dullaert et al. (2002). For the real case, it was possible to reduce the total fleet cost, when comparing to the actual solution. At some instances of the three benchmark problems, the algorithms presented similar or better results when compared to the best solutions in the literature.
|
173 |
Heurística baseada em colônia artificial de abelhas para o problema de localização de bases, alocação e realocação de ambulâncias. / Artificial bee colony heuristic for the base location, ambulance allocation and re-allocation problem.Luiz Augusto Canito Gallego de Andrade 04 June 2012 (has links)
Sistemas de atendimento emergencial estão presentes nos grandes centros urbanos de todo o mundo. Sua finalidade é fornecer socorro a indivíduos acidentados, catástrofes e pessoas com problemas de saúde de maneira ágil e eficaz. Assim, uma característica importante desses sistemas é a prontidão dos recursos e o planejamento da malha de atendimento, definida pelas localizações das bases de veículos e pelas viaturas de atendimento. A operação desses sistemas é ainda mais crítica em grandes centros urbanos, nos quais as condições de trânsito e os padrões de variação da demanda por atendimento emergencial inserem um grau de complexidade extra ao problema. Desta forma, um mapa de localização de bases e viaturas eficientemente elaborado é crítico para o desempenho do sistema como um todo. Como no Brasil existe uma lacuna entre os mecanismos de planejamento dessas malhas de atendimento e as teorias de localização de instalações, observa-se que os métodos atualmente utilizados para a localização das bases e veículos, bem como para o dimensionamento desses serviços, dependem da percepção e da experiência dos gestores responsáveis. Este trabalho visa tratar esse problema de estruturação das malhas de atendimento quanto à localização e alocação dos recursos chave (bases e viaturas) utilizando ferramentas e modelos matemáticos, de modo a propor uma formalização de todo o processo de planejamento. São revisados diversos modelos de localização de instalações e veículos de emergência e com base nas características dos grandes centros urbanos, propõe-se uma formulação matemática para o problema. Uma vez que esse modelo recai num problema de complexidade não polinomial, também é proposto um método de solução baseado no comportamento de colônias de abelhas na busca de alimentos. O método de soluções proposto é aplicado ao Serviço de Atendimento Móvel Pré-hospitalar de Urgência do Município de São Paulo em um estudo de caso. / Emergency systems are present in most of the large urban centers around the world. Its main goal is to provide assistance to victims of accidents, catastrophic events and general health issues in a quick and effective way. Therefore, a major characteristic of such systems is their resources readiness and a well-structured service network consisted basically by their emergency sites and ambulances. Operation of these systems is even more critical in large cities, in which the traffic conditions and the shifting pattern of demand along the day impose an extra complexity to the problem. Thus, an efficiently defined location/allocation map is crucial for the systems performance. In Brazil however, there is a gap between the processes, by which these maps are obtained and the facility location theories. Besides that, the methods currently applied to achieve a location/allocation map strongly depend on the perception and experience of decision makers. This work aims to deal with this planning problem by tackling the question with mathematical tools and models, resulting in a formal procedure for future emergency service network planning. A review of theories and mathematical models regarding emergency siting models is presented, and based on the large cities main characteristics, a model is proposed. Also, once this problem leads to a problem with non-polynomial complexity, a meta-heuristic was developed based on the behavior of foraging bees. This proposed solution method is also applied in a case study in São Paulo\'s Ambulance Service System (Serviço de Atendimento Móvel Pré-hospitalar de Urgência do Município de São Paulo).
|
174 |
An examination of heuristics for the shelf space allocation problem.January 2010 (has links)
Wong, Mei Ting. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 115-120). / Abstracts in English and Chinese. / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Our Contributions --- p.4 / Chapter 1.3 --- Framework of Shelf Space Allocation Problem --- p.4 / Chapter 1.4 --- Organization --- p.6 / Chapter 2. --- Literature Review --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Commercial Approaches --- p.7 / Chapter 2.3 --- Experimental Approaches --- p.8 / Chapter 2.4 --- Optimization Approaches --- p.11 / Chapter 2.4.1 --- Exact Approaches --- p.11 / Chapter 2.4.2 --- Heuristics Approaches --- p.16 / Chapter 2.5 --- Summary --- p.19 / Chapter 3. --- Overview of Shelf Space Allocation Problem --- p.21 / Chapter 3.1 --- Introduction --- p.21 / Chapter 3.2 --- Problem description --- p.22 / Chapter 3.2.1 --- Mathematical Model --- p.24 / Chapter 3.2.1.1 --- Notations --- p.25 / Chapter 3.2.1.2 --- Model --- p.25 / Chapter 3.2.1.3 --- Assumption --- p.26 / Chapter 3.2.1.4 --- Notations of final model --- p.27 / Chapter 3.2.1.5 --- Final model --- p.27 / Chapter 3.3 --- Original Heuristic --- p.28 / Chapter 3.3.1 --- Yang (2001) Method --- p.28 / Chapter 3.3.2 --- Remarks on Original Heuristic --- p.29 / Chapter 3.4 --- Original Heuristic with Yang's Adjustment --- p.30 / Chapter 3.4.1 --- Remarks on Yang's Adjustment --- p.32 / Chapter 3.5 --- New Neighborhood Movements --- p.33 / Chapter 3.5.1 --- New Adjustment Phase --- p.33 / Chapter 3.6 --- Network Flow Model --- p.35 / Chapter 3.6.1 --- ULSSAP --- p.35 / Chapter 3.6.2 --- Transforming shelf space allocation problem (SSAP) --- p.38 / Chapter 3.7 --- Tabu Search --- p.41 / Chapter 3.7.1 --- Tabu Search Algorithm --- p.42 / Chapter 3.7.1.1 --- Neighborhood search moves --- p.42 / Chapter 3.7.1.2 --- Candidate list strategy --- p.45 / Chapter 3.7.1.3 --- Tabu list --- p.46 / Chapter 3.7.1.4 --- Aspiration criteria.........................................: --- p.47 / Chapter 3.7.1.5 --- Intensification and Diversification --- p.48 / Chapter 3.7.1.6 --- Stopping criterion --- p.49 / Chapter 3.7.1.7 --- Probabilistic choice --- p.50 / Chapter 3.7.2 --- General Process of Tabu Search --- p.51 / Chapter 3.7.3 --- Application of Tabu Search to SSAP --- p.54 / Chapter 3.7.4 --- Analysis of Tabu Search --- p.58 / Chapter 4. --- Tabu Search with Path Relinking --- p.60 / Chapter 4.1 --- Introduction --- p.60 / Chapter 4.2 --- Foundations of path relinking --- p.62 / Chapter 4.3 --- Path Relinking Template --- p.65 / Chapter 4.4 --- Identification of Reference set --- p.69 / Chapter 4.5 --- Choosing initial and guiding solution --- p.73 / Chapter 4.6 --- Neighborhood structure --- p.74 / Chapter 4.7 --- Moving along paths --- p.81 / Chapter 4.8 --- Application of Tabu Search with Path Relinking --- p.87 / Chapter 4.9 --- Conclusion --- p.90 / Chapter 5. --- Computational Studies --- p.92 / Chapter 5.1 --- Introduction --- p.92 / Chapter 5.2 --- General Parameter Setting --- p.92 / Chapter 5.3 --- Parameter values for Tabu search --- p.94 / Chapter 5.4 --- Sensitivity test for Tabu search with Path Relinking --- p.95 / Chapter 5.4.1 --- Reference Set Strategies and Initial and Guiding Solution Criteria --- p.96 / Chapter 5.4.2 --- Frequency of Path Relinking --- p.99 / Chapter 5.4.3 --- Size of reference set --- p.101 / Chapter 5.4.4 --- Comparison with Tabu Search --- p.102 / Chapter 5.5 --- Comparison with other heuristics --- p.105 / Chapter 5.6 --- Conclusion --- p.109 / Chapter 6. --- Conclusion --- p.111 / Chapter 6.1 --- Summary of achievements --- p.112 / Chapter 6.2 --- Future Works --- p.113 / Bibliography --- p.115
|
175 |
Women's Experiences of Mindfulness in Romantic RelationshipsJay, Melissa 01 January 2018 (has links)
Mindfulness has been found to enhance romantic relationships through the practice of remaining open, calm, and emotionally regulated during times of struggle. There was a gap in the literature, however, related to how the practice of mindfulness is subjectively experienced in women's romantic relationships. The purpose of this heuristic study was to understand how women's practice of mindfulness effects their romantic relationships. The conceptual framework for this study was mindfulness-to-meaning theory, which highlights that wellbeing is supported through 2 main mechanisms of mindfulness: savoring and reappraisal. The nature of this study was a qualitative approach using Moustakas's heuristic method. After the data were collected through semistructured interviews, 6 themes were identified. The themes were (a) heightened presence in the relationship; (b) enhanced emotional regulation within the relationship; (c) expanded awareness in the relationship; (d) stronger connection to self and partner; (e) increased gratitude for self, partner, and their shared life; and (f) continued growth in the relationship. Women identified feeling a sense of enhanced emotional regulation within the relationship which enables them to remain calm, less reactive, and better able to communicate with their partners during times of difficulty. The findings from this study confirmed and expanded previous research. This study may enhance understanding of how mindfulness may lead to deeper connection and stability in romantic relationships. By doing so, this study may also contribute to positive social change by informing the work of those in the wellness industry who provide support to women.
|
176 |
Approximating Solutions for NANIP-BlackstartDhananjaya, Varun 01 January 2019 (has links)
In July 2012, a paper by Gutfraind et al. introduced the neighbor-aided network installation problem, which asks for "a minimal cost ordering of the vertices of a graph, where the cost of visiting a node is a function of the number of neighbors that have already been visited." Additionally, in a 2018 paper by Cummings et al., two greedy heuristics were implemented to estimate solutions to the NANIP-Blackstart problem. This paper will evaluate the performance of the greedy heuristics introduced by Cummings et al., and compare their performance to a new heuristic. In addition to comparing heuristics, we will also look at varying the blackstart node and cost function. This analysis will be conducted by testing the heuristics on power networks from the SuiteSparse Matrix Collection and NIST Matrix Market. The goal of this body of work is to better understand the variables at play in the NANIP-Blackstart problem in order to work towards better estimated solutions.
|
177 |
Investigating the effect of science writing heuristic approach on students’ learning of multimodal representations across 4th to 8th grade levelsKeles, Nurcan 15 December 2016 (has links)
This study was designed to examine the effect of Science Writing Heuristic Approach on Students’ Learning of Multimodal Representations across 4th Grade to 8the Grade Levels. Multimodal representations in the forms of figures, tables, pictures, and charts are part of scientific language. A quasi-experimental design with control and treatment group of classes was used. Students completed the summary writing task by including multimodal representations in the both control and treatment classes. The students’ writing samples were evaluated with four measures of multimodal categories, including sign, functional, conceptual and embeddedness structures. To examine the differences of treatment and control groups and the effect of age, the Hierarchical Linear Modeling (HLM) analysis was used in this study. The HLM provides an opportunity to use statistical models that account for nesting of the data. Analysis of quantitative data indicated that the treatment classes significantly outperformed than the control classes on four measures of categories. Age also was a significant contributor to students’ learning of multimodal representations. Three key points emerged from the results. Firstly, the SWH approach had positive effects on students’ understanding of the multimodal representations. Secondly, the impact of the age was different for each category. Thirdly, the categories were used in this study had significant potential when exploring the students learning of multimodal representations. The study indicated some practical benefits that the strategy of promoting argumentative scientific language effectively was resulted in better communication, understanding of the topic with multimodal representations, and some transferring impacts of all these with the summary writing activities.
|
178 |
A visual interpretation of Chinese immigrants’ identity dilemma in New ZealandZhang, Nuo January 2008 (has links)
This thesis explores the notion of identity dilemma and its visualisation in the context of New Zealand Chinese immigration. It focuses on interpreting and visualising New Zealand Chinese immigrants’ thoughts and feelings and their struggle to adapt to the environment as well as their ambivalent negotiation to balance their in-between identity of being a New Zealander (Westerner) and Chinese. It is a practice-based project and is presented by means of photography, with illustration as the supporting medium. The predicament of identity is explored through interviewing members of the New Zealand Chinese community. A semi-constructed interview is designed and introduced to canvass 20 Chinese participants’ opinions of their cultural beliefs and sense of belonging in a Western society. The data is collected and analysed to investigate the informants’ thoughts and feelings in their daily routine in a multicultural community. I, as an art and design practitioner, visually interpret and transcend my opinion of identity dilemma of Chinese immigrants into my practical works. The participants’ thoughts and feelings are transferred into my artwork through creating patterns of visual elements. Employing a heuristic visual research method, my explorative work attempts to transfer social research findings of the idea of identity dilemma into my artwork for initiating contemporary visual discourse.
|
179 |
Online shopping for women's apparel : A study extending generalization possibilities for problematic heuristics in online shoppingNilsson, Emma January 2007 (has links)
<p>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.</p><p>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.</p>
|
180 |
Scheduling the hybrid flowshop : branch and bounnd algorithmsMoursli, Omar 12 February 1999 (has links)
This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.
|
Page generated in 0.0169 seconds