In this paper, we show a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs. This is a NP-hard variant of the classical minimum spanning tree problem, in ...which there are mutually exclusive edges. We introduce a new set of valid inequalities for the problem, based on the properties of its feasible solutions, and we develop a branch-and-cut algorithm based on them. Computational tests are performed both on benchmark instances coming from the literature and on some newly proposed ones. Results show that our approach outperforms a previous branch-and-cut algorithm proposed for the same problem.
•A Biased Random-Key Genetic Algorithm (BRKGA) for the Set Orienteering Problem is presented.•A preprocessing phase is developed to remove from the instances useless vertices, arcs and clusters.•A ...hashtable and a three-dimensional matrix are used to speed up the resolution of the problem by avoiding redundant computations.•Computational results on the benchmark instances show that BRKGA quickly finds high-quality solutions.•BRKGA is faster than the other algorithms proposed in the literature.
This paper addresses the Set Orienteering Problem which is a generalization of the Orienteering Problem where the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster. The problem consists of finding a tour that maximizes the collected profit but, since the cost of the tour is limited by a threshold, only a subset of clusters can usually be visited. We propose a Biased Random-Key Genetic Algorithm for solving the Set Orienteering Problem in which three local search procedures are applied to improve the fitness of the chromosomes. In addition, we introduced three rules useful to reduce the size of the instances and to speed up the resolution of the problem. Finally, a hashtable is used to quickly retrieve the information that are required several times during the computation. The computational results, carried out on benchmark instances, show that our algorithm is significantly faster than the other algorithms, proposed in the literature, and it provides solutions very close to the best-known ones.
This article introduces the Generalized Minimum Branch Vertices problem. Given an undirected graph, where the set of vertices is partitioned into clusters, the Generalized Minimum Branch Vertices ...problem consists of finding a tree spanning exactly one vertex for each cluster and having the minimum number of branch vertices, namely vertices with degree greater than two. When each cluster is a singleton, the problem reduces to the well-known Minimum Branch Vertices problem, which is NP-hard. We show some properties that any feasible solution to the problem has to satisfy. Some of these properties can be used to determine useless vertices or edges, which can be removed to reduce the size of the instances. We propose an integer linear programming formulation for the problem, we derive the dimension of the polytope, we study the trivial inequalities and introduce two new classes of valid inequalities, that are proved to be facet-defining.
This article addresses the minimum spanning tree problem with conflicting edge pairs, a variant of the classical minimum spanning tree where, given a list of conflicting edges, the goal is to find ...the cheapest spanning tree with no edges in conflict. We adopt a Lagrangian relaxation approach together with a dual ascent and a subgradient procedure to find tight lower bounds on the optimal solution. The algorithm is also equipped with a heuristic approach which provides an upper bound by removing the conflicts from possible infeasible solutions met during the calculation of the lower bounds. The computational results, carried out on benchmark instances, show that the proposed algorithm finds the optimal solutions on several instances. Moreover, the lower bounds it provides are much more accurate than ones provided by other Lagrangian approaches available in the literature and they are computed in much less time.
The Set Orienteering Problem Archetti, Claudia; Carrabs, Francesco; Cerulli, Raffaele
European journal of operational research,
05/2018, Letnik:
267, Številka:
1
Journal Article
Recenzirano
•We introduce the Set Orienteering Problem.•An interesting application refers to the distribution of mass products.•We propose a mathematical formulation and a matheuristic algorithm.•Computational ...results on a large set of problem instances are presented.
In this paper, we study the Set Orienteering Problem which is a generalization of the Orienteering Problem where customers are grouped in clusters and a profit is associated with each cluster. The profit of a cluster is collected only if at least one customer from the cluster is visited. A single vehicle is available to collect the profit and the objective is to find the vehicle route that maximizes the profit collected and such that the route duration does not exceed a given threshold. We propose a mathematical formulation of the problem and a matheuristic algorithm. Computational tests are made on instances derived from benchmark instances for the Generalized Traveling Salesman Problem with up 1084 vertices. Results show that the matheuristic produces robust and high-quality solutions in a short computing time.
In inventory management, a fundamental issue is the rational use of required space. Among the numerous techniques adopted, an important role is played by the determination of the replenishment cycle ...offsetting which minimizes the warehouse space within a considered time horizon. The NP-completeness of the Offsetting Inventory Cycle Problem (OICP) has led the researchers towards the development and the comparison of specific heuristics. We propose and implement a genetic algorithm for the OICP, whose effectiveness is validated by comparing its solutions with those found by a mixed integer programming model. The algorithm, tested on realistic instances, shows a high reduction of the maximum space and a more regular warehouse saturation with negligible increase of the total cost. This paper, unlike other papers currently available in literature, provides instances data and results necessary for reproducibility, aiming to become a benchmark for future comparisons with other OICP algorithms.
In this paper, we analyze a new variant of the well-known NP-hard Set Covering Problem, characterized by pairwise conflicts among subsets of items. Two subsets in conflict can belong to a solution ...provided that a positive penalty is paid. The problem looks for the optimal collection of subsets representing a cover and minimizing the sum of covering and penalty costs. We introduce two integer linear programming formulations and a quadratic one for the problem and provide a parallel GRASP (Greedy Randomized Adaptive Search Procedure) that, during parallel executions of the same basic procedure, shares information among threads. We tailor such a parallel processing to address the specific problem in an innovative way that allows us to prevent redundant computations in different threads, ultimately saving time. To evaluate the performance of our algorithm, we conduct extensive experiments on a large set of new instances obtained by adapting existing instances for the Set Covering Problem. Computational results show that the proposed approach is extremely effective and efficient providing better results than Gurobi (tackling three alternative mathematical formulations of the problem) in less than 1/6 of the computational time.
•We propose a variant of the Set Covering Problem including conflicts among subsets.•We introduce three mathematical formulations including a binary quadratic one.•We develop a novel parallel GRASP with a two-stage structure.•Intermediate computations are shared to remove redundant operations across threads.•Wide experimental campaign proves efficiency and effectiveness of the proposed method.
In this study we address the Set Orienteering Problem, which is a generalization of the Orienteering Problem where customers are clustered in groups. Each group is associated with a profit which is ...gained in case at least one customer in the group is served. A single vehicle is available to serve the customers. The aim is to find the vehicle route that maximizes the profit collected without exceeding a maximum route cost, which can be interpreted also as route duration. The problem was introduced in Archetti (2018) together with a mathematical programming formulation. In this paper, we propose a new formulation which uses less variables. We also derive different classes of valid inequalities to strengthen the formulation. In addition, separation algorithms are developed, some of which are new with respect to those presented in the literature. A branch-and-cut algorithm is implemented to solve the problem and tests are made on benchmark instances. The results show that the branch-and-cut algorithm is effective in solving instances with up to 100 customers. Moreover, the difficulty of solving the problem largely depends on the maximum route duration. We also show that valid inequalities are effective in speeding up the solution process. Finally, a comparison with two exact benchmark approaches proposed in the literature shows that the branch-and-cut algorithm proposed in this paper is the new state-of-the-art exact approach for solving the Set Orienteering Problem.
•We propose a new formulation for the Set Orienteering Problem.•We propose valid inequalities.•We develop a branch-and-cut algorithm.•We perform extensive computational tests.•Results show that the B&C is effective in solving the SOP.
This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the ...close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate.
•We introduce a novel discretization scheme for the close enough TSP problem.•By reducing the discretization error, the new scheme allows to compute tighter upper and lower bounds for the problem.•We apply an enhanced convex hull strategy to save the number of discretization points to be used.•The discretization strategy allows us to assign an adaptively variable number of discretization points to each neighborhood.•Numerical comparisons with some algorithms proposed in the literature are presented.
This paper addresses a variant of the minimum spanning tree problem in which, given a list of conflicting edges, the primary goal is to find a spanning tree with the minimum number of conflicting ...edge pairs and the secondary goal is to minimize the weight of spanning trees without conflicts. The problem is NP‐hard and it finds applications in the design of offshore wind farm networks. We propose a multiethnic genetic algorithm for the problem in which the fitness function is designed to simultaneously manage the two goals of the problem. Moreover, we introduce three local search procedures to improve the solutions inside the population during the computation. Computational results performed on benchmark instances reveal that our algorithm outperforms the other heuristic approach, proposed in the literature, for this problem.
PDF
