Abstract In this article, the Resource Constrained Clustered Shortest Path Tree Problem is defined. It generalizes the classic Resource Constrained Shortest Path Tree Problem since it is defined on an undirected, complete and weighted graph whose set of nodes is partitioned into clusters. The aim is then to find a shortest path tree respecting some resource consumption constraints and inducing a connected subgraph within each cluster. The main support and motivation for studying this problem are related, among the others, to the design of telecommunication networks, and to Disaster Operations Management. In this work, we present a path‐based formulation for the problem, addressing the case of local resource constraints, that is, resource constraints on single paths. For its resolution, a Branch&Price algorithm featuring a Column Generation approach with Multiple Pricing Scheme is devised. A comprehensive computational study is conducted, comparing the proposed method with the results achieved by the CPLEX solver, adopted to solve the mathematical model. The numerical results underline that the Branch&Price algorithm outperforms CPLEX, both in terms of solution cost and time.

Current vehicles are equipped with a number of environmental sensors to improve safety and quality of life for passengers. Many researchers have shown that these sensors can also be exploited for opportunistic crowd-sensing. Useful new services can be developed on top of these data, like urban surveillance of Smart Cities. The spatio-temporal sensing coverage achievable with Vehicular Crowd-Sensing (VCS), however, is an open issue, since vehicles are not uniformly distributed over the road network, undermining the quality of potential services based on VCS data.In this paper, we present an evolution of the standard A ∗ routing algorithm, meant to increase VCS coverage by selecting a route in a random way among all those satisfying a parametric constraint on the total cost of the path. The proposed solution is based on an edge-computing paradigm, not requiring a central coordination but rather leveraging the computational resources available on-board, significantly reducing the back-end infrastructure costs. The proposed solution has been empirically evaluated on two public datasets of 450,000 real taxi trajectories from two cities, San Francisco and Porto, characterized by a very different road network topology. Results show sensible improvements in terms of achievable spatio-temporal sensing coverage of probe vehicles.

Abstract This paper deals with the Constrained Forward Shortest Path Tour Problem, an NP‐complete variant of the Forward Shortest Path Tour Problem. Given a directed weighted graph G = (V, A), where the set of nodes V is partitioned into clusters T1, …, TN, the aim is determining a shortest path between two given nodes, s and d, with the properties that clusters must be visited according to a given order, and each arc can be crossed at most once. We introduce a mathematical formulation of the problem, and a reduction procedure to reduce the number of variables involved in the model. Furthermore, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm to solve large instances of the problem. Computational tests show that the reduction procedure is very effective and its application significantly speeds up the resolution of the model. Moreover, the computational results certify the effectiveness of GRASP that often finds the optimal solution and, in general, provides quickly high‐quality sub‐optimal solutions.

SUMMARY: Quantitative structure-activity relationship (QSAR) modelling is currently used in multiple fields to relate structural properties of compounds to their biological activities. This technique is also used for drug design purposes with the aim of predicting parameters that determine drug behaviour. To this end, a sophisticated process, involving various analytical steps concatenated in series, is employed to identify and fine-tune the optimal set of predictors from a large dataset of molecular descriptors (MDs). The search of the optimal model requires to optimize multiple objectives at the same time, as the aim is to obtain the minimal set of features that maximizes the goodness of fit and the applicability domain (AD). Hence, a multi-objective optimization strategy, improving multiple parameters in parallel, can be applied. Here we propose a new multi-niche multi-objective genetic algorithm that simultaneously enables stable feature selection as well as obtaining robust and validated regression models with maximized AD. We benchmarked our method on two simulated datasets. Moreover, we analyzed an aquatic acute toxicity dataset and compared the performances of single- and multi-objective fitness functions on different regression models. Our results show that our multi-objective algorithm is a valid alternative to classical QSAR modelling strategy, for continuous response values, since it automatically finds the model with the best compromise between statistical robustness, predictive performance, widest AD, and the smallest number of MDs. AVAILABILITY AND IMPLEMENTATION: The python implementation of MaNGA is available at https://github.com/Greco-Lab/MaNGA. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

While many works have been devoted to service matchmaking and modeling nonfunctional properties, the problem of matching service requests to offers in an optimal way has not yet been extensively studied. In this paper we formalize three kinds of optimal service selection problems, based on different criteria. Then we study their complexity and implement solutions. We prove that one-time costs make the optimal selection problem computationally hard; in the absence of these costs the problem can be solved in polynomial time. We designed and implemented both exact and heuristic (suboptimal) algorithms for the hard case, and carried out a preliminary experimental evaluation with interesting results.

We propose FORTRAN subroutines for approximately solving the feedback vertex and arc set problems on directed graphs using a Greedy Randomized Adaptive Search Procedure (GRASP). Implementation and usage of the package is outlined and computational experiments are reported illustrating solution quality as a function of running time.