Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

This study is based on heuristic methodology and looks at counsellor/therapists’ experience of integrating Christian faith with their clinical practice. The researcher overtly includes her own material and documents her own internal process as part of the research journey. Some of this is achieved by the inclusion of portions of creative writing. The literature review covers a wide field, looking at the relationship between spirituality and counselling from both historical and contemporary writers. It includes both US and UK material and representation from both secular and Christian sources. It examines the ethics and the practicalities of integrating faith with practice. Interview material is presented from twenty-two practitioners, together with that of three named academics in the field. Initially three exemplars are described in their entirety, as representatives of different groups of counsellors within the whole sample. Four major themes of interest emerged from the academic interviews. These themes were: a) Attention to the spirituality of the counsellorb) Support for the counsellor working with the spiritual dimensionc) The effect of context, culture and language of the counsellingd) The effect of client’s spirituality on the counselling process. Material from all interviewees is discussed using these themes, in relation to the literature. Specific unmet needs of the practitioners are identified. Major findings were that although counsellors with a Christian faith generally agree with the concept of their spirituality being an integral part of their work, there is variation in the level of attention paid to this. The availability of support for this integration is often problematic. Most counsellors desired more ‘safe space’ to explore the issue. Following the heuristic process, a model linking the psychological and spiritual perspectives emerged. This has enabled the researcher to further reflect on her own integration journey. It has since been used in workshops to facilitate other practitioners in reflecting on their individual integration. Recommendations for further research are made. The limitations of the research are noted.

Graph theory is a large mathematical discipline. Chinese postman problem falls under category of arc vehicle routing problems. Chinese postman problems are very extensive and difficult to calculate in practice. They belong to NP-hard problems. For this reason, heuristics are proposed to provide acceptably good solution in polynomial time. The focus of this thesis is to propose a randomized heuristic which does not follow deterministic rules but is ruled by random. Monte Carlo simulation is launched to find the best solution. Heuristic is formulated for undirected capacitated rural postman problem. It is programmed in VBA and validated on testing problems. At the end of the thesis is a case study about municipal garbage collection.

This research outlines a study that was performed to determine the effects of user interface design variations on the usability and solution quality of complex, multivariate discrete-event simulations. Specifically, this study examined four key research questions: what are the user interface considerations for a given simulation model, what are the current best practices in user interface design for simulations, how is usability best evaluated for simulation interfaces, and specifically what are the measured effects of varying levels of usability of interface elements on simulation operations such as data entry and solution analysis. The overall goal of the study was to show the benefit of applied usability practices in simulation design, supported by experimental evidence from testing two alternative simulation user interfaces designed with varying usability. The study employed directed research in usability and simulation design to support design of an experiment that addressed the core problem of interface effects on simulation. In keeping with the study goal of demonstrating usability practices, the experimental procedures were analogous to the development processes recommended in supporting literature for usability-based design lifecycles. Steps included user and task analysis, concept and use modeling, paper prototypes of user interfaces for initial usability assessment, interface development and assessment, and user-based testing of actual interfaces with an actual simulation model. The experimental tests employed two interfaces designed with selected usability variations, each interacting with the same core simulation model. The experimental steps were followed by an analysis of quantitative and qualitative data gathered, including data entry time, interaction errors, solution quality measures, and user acceptance data. The study resulted in mixed support for the hypotheses that improvements in usability of simulation interface elements will improve data entry, solution quality, and overall simulation interactions. Evidence for data entry was mixed, for solution quality was positive to neutral, and for overall usability was very positive. As a secondary benefit, the study demonstrated application of usability-based interface design best practices and processes that could provide guidelines for increasing usability of future discrete-event simulation interface designs. Examination of the study results also provided suggestions for possible future research on the investigation topics.

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T21:41:01Z (GMT). No. of bitstreams: 1 Xavier_EduardoCandido_D.pdf: 20666026 bytes, checksum: 5e051653d938a813e227b1e2eebcd415 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade. / Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality. / Doutorado / Doutor em Ciência da Computação

This thesis focuses on the development and extension of nonlinear evolutionary model predictive control (NEMPC), a control algorithm previously developed by Phil Hyatt of the BYU RaD Lab. While this controller and its variants are applicable to any high degree-of-freedom (DoF) robotic system, particular emphasis is given in this thesis to control of a soft robot continuum joint. First, speed improvements are presented for NEMPC. Second, a Python package is presented as a companion to NEMPC, as a method of establishing a common interface for dynamic simulators and approximating each system by a deep neural network (DNN). Third, a method of training a DNN approximation of a hardware system that is generalize-able to more complex hardware systems is presented. This method is shown to reduce median tracking error on a soft robot hardware platform by 88%. Finally, particle swarm model predictive control (PSOMPC), a variant of NEMPC, is presented and modified to model and account for uncertainty in a dynamic system. Control performance of NEMPC and PSOMPC are presented for a set of control trials on simulated systems with uncertainty in parameters, states, and inputs, as well as on a soft robot hardware platform. PSOMPC is shown to have an increased robustness to system uncertainty, reducing expected collisions by 71% for a three-link robot arm with parameter uncertainty, input disturbances, and state measurement error.

In the field of embedded systems, computers embedded into machines ranging from microwaveovensto assembly lines impact the physical world. They do so under tight real-time constraintswith ever-increasing demand for computing power and performance. Development of higher speedprocessors have been hampered by diminishing returns on power consumption as clock frequency isfurther increased. For this reason, today, embedded processor development is instead moving towardfurther concurrency with multi-core processors being considered more and more every day. Withparallelism comes challenges, such as interference caused by shared resources. Contention betweenprocessor cores, such as shared memory, result in inter-core interference which is potentially unpredictableand unbounded. The focus of this thesis is placed on minimizing inter-core interferencewhile meeting local task timing requirements by utilizing scheduling heuristics. A scheduling heuristicis designed and a prototype scheduler which implements this algorithm is developed. Thescheduler is evaluated on randomly generated test cases, where its ability to keep inter-core datapropagationdelays low across different core counts and utilization values was evaluated. The algorithmis also compared with constraint programming in a real world industrial test case. Theobtained results show that the algorithm can produce schedules with low inter-core delays in a veryshort time, although not being able to optimize them fully compared to constraint programming.

A modern computer-based simulation tool (WaterMan) in the form of a game for on-farm water management was developed for application in training events for farmers, students, and irrigators. The WaterMan game utilizes an interactive framework, thereby allowing the user to develop scenarios and test alternatives in a convenient, risk-free environment. It includes a comprehensive soil water and salt balance calculation algorithm. It also employs heuristic capabilities for modeling all of the important aspects of on-farm water management, and to provide reasonable scores and advice to the trainees. Random events (both favorable and unfavorable) and different strategic decisions are included in the game for more realism and to provide an appropriate level of challenge according to player performance. Thus, the ability to anticipate the player skill level, and to reply with random events appropriate to the anticipated level, is provided by the heuristic capabilities used in the software. These heuristic features were developed based on a combination of two artificial intelligence approaches: (1) a pattern recognition approach; and (2) reinforcement learning based on a Markov Decision Processes approach, specifically, the Q-learning method. These two approaches were combined in a new way to account for the difference in the effect of actions taken by the player and action taken by the system on the game world. The reward function for the Q-learning method was modified to reflect the anticipated type of the WaterMan game as what is referred to as a partially competitive and partially cooperative game. Twenty-two different persons classified under three major categories (1) practicing farmers; (2) persons without an irrigation background; and (3) persons with an irrigation background, were observed while playing the game, and each of them filled out a questionnaire about the game. The technical module of the game was validated in two ways: through conducting mass balance calculations for soil water content and salt content over a period of simulation time, and through comparing the WaterMan technical module output data in calculating the irrigation requirements and the use of irrigation scheduling recommendations with those obtained from the same set of input data to the FAO CropWat 8 software. The testing results and the technical validation outcomes demonstrate the high performance of the WaterMan game as a heuristic training tool for on-farm water management.

Research has examined how encoding or retrieval factors affect metamemory. Few studies have manipulated both an encoding and a retrieval factor in the same paradigm. The current experiments examined which factor had a greater impact on metamemory when both were manipulated. Attention was manipulated during encoding and Retroactive Interference was manipulated at retrieval.Two lists of word pairs were studied, with the second list including both new pairs and cues from the first list re-paired with a new target. The attention manipulation occurred when studying the first list in which participants denoted when one tone sequence changed to another. Participants gave predictions about the likelihood of future recall of the original targets either immediately following study (JOL) or in a separate phase after studying all pairs (DJOL). The Modified Opposition Test (MOT) was used in which a hint was used to direct participants to the correct list for recall. After all pairs were studied and predicted, participants completed a cued-recall test. In Experiment 1, DJOLs were used because they are collected between encoding and retrieval. Both factors impacted memory, but DJOLs were only impacted by the retrieval factor. A dissociation between memory and metamemory under retroactive interference was expected and replicates prior research (Eakin, 2005). In Experiment 2, JOLs were added; JOLs are measured during the encoding phase, allowing the impact of the encoding factor to be observed. Replicating Experiment 1, memory was affected by both the encoding and retrieval factor, but JOLs were impacted by the retrieval factor. Another comparison using a standard cued-recall test instead of the MOT, showed that JOLs were no longer influenced by the retrieval factor, but they still did not vary with attention. The results conclusively suggest that metamemory was not based on encoding factors, even when the retrieval factor is not influencing the predictions. Koriat’s (1993, 1994) accessibility heuristic can explain these results. Predictions were based on how much information came to mind when the prediction is made, regardless of whether that information is correct. Furthermore, metamemory predictions are based on heuristics that do not always follow memory outcomes.

No description available.