Search

In practice, developers mostly use purely textual, line-based, merge tools. Such tools, however, often report false conflicts. Researchers have then proposed AST-based tools that explore language syntactic structure to reduce false conflicts. Nevertheless, these approaches might negatively impact merge performance, and demand the creation of a new tool for each language. Trying to simulate the behavior of AST-based tools without their drawbacks, this paper proposes and analyzes a purely textual, separator-based, merge tool that aims to simulate AST-based tools by considering programming language syntactic separators, instead of just lines, when comparing and merging changes. The obtained results show that the separator-based textual approach might reduce the number of false conflicts when compared to the line-based approach. The new solution makes room for future studies and hybrid merge tools.

The Large Scale Vehicle Routing Problem (LSVRP) is a classical combinatorial optimisation problem that serves several customers on a graph using a set of vehicles. Due to the NP-hardness and large problem size, LSVRP cannot be efficiently solved by exact approaches. Heuristic methods such as the Iterative Local Search or the Hybrid Genetic Algorithm still struggle for finding effective solutions for large scale instances. For these methods to deal with the large search space, pruning techniques are applied in order to limit the number of explored solutions. However, effective pruning is a hard task, requiring domain knowledge to craft good ways of limiting the search space without losing the ability to find better solutions. Hyper-heuristics are types of methods that aim to reduce domain knowledge on the creation of heuristics, and in this work, we also apply them for effective heuristic pruning. Our Evolutionary Hyper-Heuristic (EHH) automatically evolves limits to the solution search space together with the heuristic utilised to build and improve solutions for the LSVRP. We utilise a Guided Local Search (GLS) as the base algorithm in which our EHH searches for the best heuristic configuration. Our results show that the EHH can find better solutions for most LSVRP test instances when compared to the manually designed pruning of the GLS.

The Large Scale Vehicle Routing Problem is a classical NP-hard problem. It has several applications in the industry and has always been the focus of studies and development of new, ever more complex, techniques to solve it. An important group of these techniques are Local Search-based, which are sensitive to the initial solution given to them. However, finding effective initial solutions is not a trivial task, requiring domain knowledge for building them. Although some Genetic Programming Hyper-Heuristics (GPHH) have tried to build better heuristics automatically, they barely give an advantage for improving the solution afterwards. This paper aims to show that Genetic Programming can identify better regions of the search space, where the initial solutions can be improved more efficiently with optimisation steps. This is done by developing new terminals and a new fitness function, which are based on the width of the routes, a metric that was recently found to be an important feature for good solutions. The obtained results show that the proposed approach finds better final solutions than when using classical initial heuristics or other GPHH, for both time efficiency and effectiveness.

Amid continuing increases in purchasing power and Internet shopping, demands for more efficient algorithms to solve the Large-Scale Vehicle Routing Problems are to be expected. The problem, which consists of finding routes for visiting customers, however, is very hard to solve due to its combinatorial nature. This becomes more notable when looking at large scale instances, i.e at least 200 customers, requiring sophisticated solution methods to solve, mostly heuristic-based. The existing meta-heuristics apply some limits to the solution space for handling the large scale nature. However, this is typically done manually, based on extensive domain knowledge. Hyper-Heuristics aim to reduce domain knowledge dependence, but current works disregard search space size, presenting poor scalability. In this paper, we propose a new Hyper-Heuristic to automatically evolve effective heuristics, based on a Genetic Algorithm framework. The new Hyper-Heuristic adds limits to the neighbourhoods of Low-Level Heuristics. In the method, the large search space is dealt with an adaptive chromosome which limits the neighbourhood size for each operator. The goal is to show whether more effective limits can be found if done automatically. Results show that the automatically evolved neighbourhood size limits outperform fixed ones for most instances tested and manually designed limits.

One of the most known transportation problems, the Large-Scale Vehicle Routing Problem (LSVRP) requires more sophisticated methods to be solved due to the sheer amount of customers. Most current methods include manually designed heuristics and parameters, such as restrictions in the search space. Hyper-heuristics(HHs) appear as a counterpoint to the manually designed complex methods. This paper presents a preliminary study on adaptive search space based on clustering, utilizing a HH Selection framework with Genetic Algorithm (GA). The initial results show promise in having an adaptive search scope when compared to a fixed clustering approach. A comparison of the effects of having a route-first vs cluster-first initial solution is also presented, favouring the latter one, as well as a comparison between two types of chromosome decoding. Finally, the proposed method is compared to a manually designed algorithm, producing results with better quality. The method is shown to be significantly better for most scenarios, achieving solutions just as good as when no limits are applied, but in a much shorter time.

Empirical studies show that merge conflicts frequently occur, impairing developers' productivity, since merging conflicting contributions might be a demanding and tedious task. However, the structure of changes that lead to conflicts has not been studied yet. Understanding the underlying structure of conflicts, and the involved syntactic language elements might shed light on how to better avoid merge conflicts. To this end, in this paper we derive a catalog of conflict patterns expressed in terms of the structure of code changes that lead to merge conflicts. We focus on conflicts reported by a semistructured merge tool that exploits knowledge about the underlying syntax of the artifacts. This way, we avoid analyzing a large number of spurious conflicts often reported by typical line based merge tools. To assess the occurrence of such patterns in different systems, we conduct an empirical study reproducing 70,047 merges from 123 GitHub Java projects. Our results show that most semistructured merge conflicts in our sample happen because developers independently edit the same or consecutive lines of the same method. However, the probability of creating a merge conflict is approximately the same when editing methods, class fields, and modifier lists. Furthermore, we noticed that most part of conflicting merge scenarios, and merge conflicts, involve more than two developers. Also, that copying and pasting pieces of code, or even entire files, across different repositories is a common practice and cause of conflicts. Finally, we discuss how our results reveal the need for new research studies and suggest potential improvements to tools supporting collaborative software development.

While unstructured merge tools rely only on textual analysis to detect and resolve conflicts, semistructured merge tools go further by partially exploiting the syntactic structure and semantics of the involved artifacts. Previous studies compare these merge approaches with respect to the number of reported conflicts, showing, for most projects and merge situations, reduction in favor of semistructured merge. However, these studies do not investigate whether this reduction actually leads to integration effort reduction (productivity) without negative impact on the correctness of the merging process (quality). To analyze that, and better understand how merge tools could be improved, in this paper we reproduce more than 30,000 merges from 50 open source projects, identifying conflicts incorrectly reported by one approach but not by the other (false positives), and conflicts correctly reported by one approach but missed by the other (false negatives). Our results and complementary analysis indicate that, in the studied sample, the number of false positives is significantly reduced when using semistructured merge. We also find evidence that its false positives are easier to analyze and resolve than those reported by unstructured merge. However, we find no evidence that semistructured merge leads to fewer false negatives, and we argue that they are harder to detect and resolve than unstructured merge false negatives. Driven by these findings, we implement an improved semistructured merge tool that further combines both approaches to reduce the false positives and false negatives of semistructured merge. We find evidence that the improved tool, when compared to unstructured merge in our sample, reduces the number of reported conflicts by half, has no additional false positives, has at least 8% fewer false negatives, and is not prohibitively slower.

Industry widely uses unstructured merge tools that rely on textual analysis to detect and resolve conflicts between code contributions. Semistructured merge tools go further by partially exploring the syntactic structure of code artifacts, and, as a consequence, obtaining significant merge accuracy gains for Java-like languages. To understand whether semistructured merge and the observed gains generalize to other kinds of languages, we implement two semistructured merge tools for JavaScript, and compare them to an unstructured tool. We find that current semistructured merge algorithms and frameworks are not directly applicable for scripting languages like JavaScript. By adapting the algorithms, and studying 10,345 merge scenarios from 50 JavaScript projects on GitHub, we find evidence that our JavaScript tools report fewer spurious conflicts than unstructured merge, without compromising the correctness of the merging process. The gains, however, are much smaller than the ones observed for Java-like languages, suggesting that semistructured merge advantages might be limited for languages that allow both commutative and non-commutative declarations at the same syntactic level.

Merge conflicts often occur when developers concurrently change the same code artifacts. While state of practice unstructured merge tools (e.g. Git merge) try to automatically resolve merge conflicts based on textual similarity, semistructured and structured merge tools try to go further by exploiting the syntactic structure and semantics of the artifacts involved. Although there is evidence that semistructured merge has significant advantages over unstructured merge, and that structured merge reports significantly fewer conflicts than unstructured merge, it is unknown how semistructured merge compares with structured merge. To help developers decide which kind of tool to use, we compare semistructured and structured merge in an empirical study by reproducing more than 40,000 merge scenarios from more than 500 projects. In particular, we assess how often the two merge strategies report different results: we identify conflicts incorrectly reported by one but not by the other (false positives), and conflicts correctly reported by one but missed by the other (false negatives). Our results show that semistructured and structured merge differ in 24% of the scenarios with conflicts. Semistructured merge reports more false positives, whereas structured merge has more false negatives. Finally, we found that adapting a semistructured merge tool to resolve a particular kind of conflict makes semistructured and structured merge even closer.

Semi-supervised learning considers the problem of classification when only a small subset of the observations have corresponding classes labels. Unfortunately, labeling a sufficiently large training data set will require human involvement, an expensive and time-consuming task. Recently, several papers in literature show that deep learning techniques are able to solve this problem. In this sense, this work proposes a Semi-supervised Deep Classification (SDC) method to solve the semi-supervised problem by using a Multilayer Perceptron (MLP) embedded to the labeling process. Extensive experiments on benchmark data sets validate the effectiveness and robustness of the proposed method.

In this Dissertation, the Vehicle Routing Problem with Drones (VRPD), motivated by the growing interest on Unmanned Aerial Vehicles (UAVs, or Drones) by the industry and their applications in logistics is studied. A pioneer work by (MURRAY; CHU, 2015) shows a combination between UAV and a truck to deliver products, presenting an adaptation to the Traveling Salesman Problem (TSP). After a literature review, an extension of the model from Murray and Chu (2015) we present a model for the problem with multiple vehicles. This model is developed as a Mixed Integer Linear Programming (MILP) problem and solved with the solver CPLEX. A heuristic based on a Hybrid Genetic Algorithm (HGA) is also developed and presented. Our results show that the use of drones reduces the total mileage of the trucks by a significant percentage. Nessa monografia estuda-se o Problema do Roteamento de Veículos com Drones (PRVD), motivado pelo crescente interesse da indústria em Veículos Aéreos Não Tripulados (VANTs) e suas aplicações em logística. O trabalho pioneiro de (MURRAY; CHU, 2015) mostra uma combinação entre VANT e um caminhão para realização de entregas de produtos, no qual foi proposta uma adaptação do Problema do Caixeiro Viajante (PCV). Após uma revisão de literatura, apresenta-se uma extensão do modelo de Murray and Chu (2015) para o problema com múltiplos veículos. Desenvolveu-se um modelo de Programação Linear Inteira Mista que foi resolvido com o solver CPLEX. Uma heurística basead em um Algoritmo Genético Híbrido também foi desenvolvido e é apresentada. Resultados mostram que a utilização dos VANTs reduzem a quilometragem dos caminhões significativamente.

In a collaborative development environment, tasks are commonly assigned to developers working independent from each other. As a result, when trying to integrate these contributions, one might have to deal with conflicting changes. Such conflicts might be detected when merging contributions (merge conflicts), when building the system (build conflicts), or when running tests (semantic conflicts). Regarding such conflicts, previous studies show that they occur frequently, and impair developers’ productivity, as understanding and solving them is a demanding and tedious task that might introduce defects. However, despite the existing evidence in the literature, the structure of changes that lead to conflicts has not been studied yet. Understanding the underlying structure of conflicts, and the involved syntactic language elements, might shed light on how to better avoid them. For example, awareness tools that inform users about ongoing parallel changes such as Syde and Palantir can benefit from knowing the most common conflict patterns to become more efficient. With that aim, in this paper we focus on understanding the underlying structure of merge conflicts.

In this paper, we present a fuzzy system for structural recognition in which the environment information is used to generate a topological map. The proposed method combines the recognized information from a given scene with a topological graph to create a map. This map can be used to plan high-level tasks of robotic navigation. The topological nodes are used to store semantic information, such as the robot’s poses, sensor data and scene characteristics. The fuzzy system categorizes the structural information as either rooms, corridors or doors.

In collaborative development environments integration conflicts occur frequently. To alleviate this problem, different awareness tools have been proposed to alert developers about potential conflicts before they become too complex. However, there is not much empirical evidence supporting the strategies used by these tools. Learning about what types of changes most likely lead to conflicts might help to derive more appropriate requirements for early conflict detection, and suggest improvements to existing conflict detection tools. To bring such evidence, in this paper we analyze the effectiveness of two types of code changes as conflict predictors. Namely, editions to the same method, and editions to directly dependent methods. We conduct an empirical study analyzing part of the development history of 45 Java projects from GitHub and Travis CI, including 5,647 merge scenarios, to compute the precision and recall for the conflict predictors aforementioned. Our results indicate that the predictors combined have a precision of 57.99% and a recall of 82.67%. Moreover, we conduct a manual analysis which provides insights about strategies that could further increase the precision and the recall.

While unstructured merge tools try to automatically resolve merge conflicts via textual similarity, semistructured and structured merge tools try to go further by exploiting the syntactic structure and semantics of the involved artefacts. Previous studies compare these merge approaches with respect to the number of reported conflicts, showing, for most projects and merge situations, a reduction in favor of semistructured and structured merge. However, these studies do not investigate whether this reduction actually leads to integration effort reduction (Productivity) without negative impact on the correctness of the merging process (Quality). To analyze this, and to better understand how these tools could be improved, we propose empirical studies to identify spurious conflicts (false positives) reported by one approach but not by the other, and interference reported as conflict by one approach but missed by the other (false negatives).

While unstructured merge tools try to automatically resolve merge conflicts via textual similarity, semistructured merge tools try to go further by partially exploiting the syntactic structure and semantics of the involved artefacts. Previous studies compare these merge approaches with respect to the number of reported conflicts, showing, for most projects and merge situations, a reduction in favor of semistructured merge. However, these studies do not investigate whether this reduction actually leads to integration effort reduction (Productivity) without negative impact on the correctness of the merging process (Quality). To analyze this, and to better understand how these tools could be improved, we propose empirical studies to identify spurious conflicts reported by one approach but not by the other, and interference reported as conflict by one approach but missed by the other.

Context: To reduce the integration effort arising from conflicting changes resulting from collaborative software development tasks, unstructured merge tools try to automatically solve part of the conflicts via textual similarity, whereas structured and semistructured merge tools try to go further by exploiting the syntactic structure of the involved artifacts. Objective: In this study, aiming at increasing the existing body of evidence and assessing results for systems developed under an alternative version control paradigm, we replicate an experiment conducted by Apel et al. to compare the unstructured and semistructured approach with respect to the occurrence of conflicts reported by both approaches. Method: We used both semistructured and unstructured merge in a sample 2.5 times bigger than the original study regarding the number of projects and 18 times bigger regarding the number of merge scenarios, and we compared the occurrence of conflicts. Results: Similar to the original study, we observed that semistructured merge reduces the number of conflicts in 55% of the scenarios of the new sample. However, the observed average conflict reduction of 62% in these scenarios is far superior than what has been observed before. We also bring new evidence that the use of semistructured merge can reduce the occurrence of conflicting merge scenarios by half. Conclusions: Our findings reinforce the benefits of exploiting the syntactic structure of the artifacts involved in code integration. Besides, the reductions observed in the number and size of conflicts suggest that the use of semistructured merge, when compared to the unstructured approach, might decrease integration effort without compromising correctness.