This paper presents Post-Decision Proximal Policy Optimization (PDPPO), a novel variation of the leading deep reinforcement learning method, Proximal Policy Optimization (PPO). The PDPPO state transition process is divided into two steps: a deterministic step resulting in the post-decision state and a stochastic step leading to the next state. Our approach incorporates post-decision states and dual critics to reduce the problem's dimensionality and enhance the accuracy of value function estimation. Lot-sizing is a mixed integer programming problem for which we exemplify such dynamics. The objective of lot-sizing is to optimize production, delivery fulfillment, and inventory levels in uncertain demand and cost parameters. This paper evaluates the performance of PDPPO across various environments and configurations. Notably, PDPPO with a dual critic architecture achieves nearly double the maximum reward of vanilla PPO in specific scenarios, requiring fewer episode iterations and demonstrating faster and more consistent learning across different initializations. On average, PDPPO outperforms PPO in environments with a stochastic component in the state transition. These results support the benefits of using a post-decision state. Integrating this post-decision state in the value function approximation leads to more informed and efficient learning in high-dimensional and stochastic environments.

This paper seeks to advance CVRP research by addressing the challenge of understanding the nuanced relationships between instance characteristics and metaheuristic (MH) performance. We present Instance Space Analysis (ISA) as a valuable tool that allows for a new perspective on the field. By combining the ISA methodology with a dataset from the DIMACS 12th Implementation Challenge on Vehicle Routing, our research enabled the identification of 23 relevant instance characteristics. Our use of the PRELIM, SIFTED, and PILOT stages, which employ dimensionality reduction and machine learning methods, allowed us to create a two-dimensional projection of the instance space to understand how the structure of instances affect the behavior of MHs. A key contribution of our work is that we provide a projection matrix, which makes it straightforward to incorporate new instances into this analysis and allows for a new method for instance analysis in the CVRP field.

A recent study on the classical capacitated vehicle routing problem (CVRP) introduced an adaptive version of the widely used iterated local search paradigm, hybridized with a path-relinking (PR) strategy. The solution method, called adaptive iterated local search (AILS)-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances suggest that PR is too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an AILS combined with mechanisms to handle large CVRP instances, called AILS-II. The computational cost of this implementation is reduced, whereas the algorithm also searches the solution space more efficiently. AILS-II is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best-known solutions. Moreover, AILS-II consistently outperforms the state of the art on larger instances with up to 30,000 vertices. History: Accepted by Ted Ralphs, Area Editor for Software Tools. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Software Tools for Vehicle Routing. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 2013/07375-0, 2019/22067-6, and 2022/05803-3] and the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 309385/2021-0 and 403735/2021-1]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0106 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0106 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The solution of combinatorial problems has been largely performed by heuristics for their ability to obtain good solutions faster than exact methods. In this paper, we propose heuristic methods to approach a hard-to-solve combinatorial optimization problem. The target routing problem is the recently proposed Traveling Backpacker Problem (TBP), which has not been investigated by a heuristic method yet. The difficulty in constructing feasible solutions for such a problem drove us to approach the TBP by a metaheuristic with a learning stage in the search, the Intelligent Greedy Adaptive Search (IGAS). To validate the introduced solution methods, they were compared to the exact solution obtained by CPLEX. Besides, we analyze isolate parts of the methods to infer about the performance of the construction of the solution and the local search, the main phases of IGAS. The results of computational experiments show that IGAS outperformed the other introduced methods in small-sized and medium-sized instances, being competitive in larger instances. Moreover, IGAS presented reasonable gaps to the solutions obtained by the exact commercial solver.

The COVID-19 pandemic has created an urgency for studies to understand the spread of the virus, in particular, to predict the number of daily cases. This type of investigation depends heavily on the data collected and made available manually. Therefore, data are susceptible to human errors which can cause anomalies in the dataset. Understanding and correcting anomalies in real-world application data is an important task to ensure the reliability of the data analysis and prediction tools. This paper presents a spectral anomaly detection and correction strategy that uses concepts from the graph signal processing (GSP) theory. The main advantage of the introduced strategy is to analyze the variation in the daily number of cases with the proximity relation between the investigated locations. Experiments were carried out with real meteorological and mobility data for predicting the number of COVID-19 cases by the classic prediction model known as autoregressive integrated moving average exogenous (ARIMAX). Then, the anomaly detection method was applied to determine the relationship between the prediction errors and the anomalous variations identified by the tool. The results show a strong relationship between the anomalous variations and the errors made by the model and attest to the increase in the accuracy of the prediction model after the normalization of the anomalies.

Understanding the community structure of realworld networks is an important task to predict the dynamics of many complex systems. To this end, several optimization methods were developed to maximize the widely studied measure known as Modularity. Most of these methods use global information and, therefore, are computationally expensive to process large-scale networks. This paper proposes a genetic algorithm to detect communities in directed networks, named NGA-LP, that contains local genetic operators designed to have low computational cost. The primary advantage of NGA-LP is the local representation, where the vertices store the information of the individuals. This representation makes possible the use of local genetic operators which do not require global information. Moreover, NGA-LP combines a pair of crossover operators that are automatically chosen according to the characteristics of the network, guided by the quality of the solution. The goal of combining different crossover operators is to ensure the robustness and capability of handling with different networks in an adaptive fashion. In the computational tests carried out in this paper, the introduced algorithm achieved excellent results and outperformed the other benchmark algorithms, even for undirected networks.

Finding communities in networks is a commonly used form of network analysis. There is a myriad of community detection algorithms in the literature to perform this task. In spite of that, the number of community detection algorithms in directed networks is much lower than in undirected networks. However, evaluation measures to estimate the quality of communities in undirected networks nowadays have its adaptation to directed networks as, for example, the well-known modularity measure. This paper introduces a genetic-based consensus clustering to detect communities in directed networks with the directed modularity as the fitness function. Consensus strategies involve combining computational models to improve the quality of solutions generated by a single model. The reason behind the development of a consensus strategy relies on the fact that recent studies indicate that the modularity may fail in detecting expected clusterings. Computational experiments with artificial LFR networks show that the proposed method was very competitive in comparison to existing strategies in the literature.

The recent growth in the use of wireless sensor networks (WSNs) in many applications leads to the raise of a core infrastructure for communication and data gathering in Cyber-Physical Systems (CPS). The communication strategy in most of the WSNs relies on hierarchical clustering routing protocols due to their ad hoc nature. In the bulk of the existing approaches some special nodes, named Cluster-Heads (CHs), have the task of assembling clusters and intermediate the communication between the cluster members and a central entity in the network, the Sink. Therefore, the overall efficiency of such protocols is highly dependent on the even distribution of CHs in the network. Recently, a community detection-based approach, named RLP, have shown interesting results with respect to the CH distribution and availability that potentially increases the overall WSN efficiency. Despite the better results of RLP regarding the literature, the adopted CH election algorithm may lead to a CH shortage throughout the network operation. In line with that, in this paper, we introduce an improved version of RLP, named HRLP. Our proposal includes a hybrid CH election algorithm which relies on a computationally cheap and distributed probabilistic-based CH recovery procedure to improve the network connectivity. Additionally, we provide a performance analysis of HRLP and its comparison to other protocols by considering a large-scale WSN scenario. The results evince the improvements achieved by the proposed strategy by means of the network connectivity and lifetime metrics.

Iterative heuristics are commonly used to address combinatorial optimization problems. However, to meet both robustness and efficiency with these methods when their iterations are independent, it is necessary to consider a high number of iterations or to include local search-based strategies in them. Both approaches are very time-consuming and, consequently, not efficient for medium and large-scale instances of combinatorial optimization problems. In particular, the community detection problem in networks is well-known due to the instances with hundreds to thousands of vertices. In the literature, the heuristics to detect communities in networks that use a local search are those that achieve the partitions with the best solution values. Nevertheless, they are not suitable to tackle medium to large scale networks. This paper presents an adaptive heuristic, named GNGClus, that uses the neural network Growing Neural Gas to play the role of memory mechanism. The computational experiment with LFR networks indicates that the proposed strategy significantly outperformed the same solution method with no memory mechanism. In addition, GNGClus was very competitive with a version of the heuristic that employs an elite set of solutions to guide the solution search.

In this paper, we propose a new semi-supervised growing neural gas (GNG) model, named Consensus-Based Semi-Supervised GNG, or CSSGNG, in which both labeled and unlabeled data are used to train the network. In contrast to former adaptations of the GNG to semi-supervised classification, such as the SSGNG and OSSGNG models, the CSSGNG does not assign a single scalar label value to each neuron. Instead of the scalar, a vector containing the representativeness level of every class is associated with each neuron. Moreover, to propagate the labels among the neurons the CSSGNG employs a consensus approach. Computer experiments show that our model on average can deliver better classification results in comparison to the SSGNG and OSSGNG models.

In Wireless Sensor Networks (WSNs), routing remains a key issue primarily regarding to the overall energy consumption. Accordingly, the energy conservation has been addressed by a few strategies, namely cluster-based hierarchical routing protocols. Nevertheless, the load balancing and the network lifetime achieved by such strategies strongly depend on the even distribution of the cluster-heads in the network. Therefore, we propose in this paper a community detection-based routing protocol for automatically producing and evenly distributing clusters in the network. We evaluate the performance of the proposed protocol and compare it with LEACH by considering the connectivity of the sensor nodes to the cluster-heads, the routing efficiency, the event data delivery ratio and the network lifetime. According to the results, the proposed approach outperform LEACH when considering applications with strict response times.

Clustering is an important tool for data analysis, since it allows the exploration of datasets with no or very little prior information. Its main goal is to group a set of data based on their similarity (dissimilarity). A well known mathematical formulation for clustering is the k-medoids problem. Current versions of k-medoids rely on heuristics, with good results reported in the literature. However, few methods that analyze the quality of the partitions found by the heuristics have been proposed. In this paper, we propose a hybrid Lagrangian heuristic for the k-medoids. We compare the performance of the proposed Lagrangian heuristic with other heuristics for the k-medoids problem found in literature. Experimental results presented that the proposed Lagrangian heuristic outperformed the other algorithms.