Search

Deep Reinforcement Learning (RL) has achieved high success in solving routing problems. However, state-of-the-art deep RL approaches require a considerable amount of data before they reach reasonable performance. This may be acceptable for small problems, but as instances grow bigger, this fact severely limits the applicability of these methods to many real-world instances. In this work, we study a setting where the agent can access data from previously handcrafted heuristics for the Traveling Salesman Problem. In our setting, the agent has access to demonstrations from 2-opt improvement policies. Our goal is to learn policies that can surpass the quality of the demonstrations while requiring fewer samples than pure RL. In this study, we propose to first learn policies with Imitation Learning (IL), leveraging a small set of demonstration data to accelerate policy learning. Afterward, we combine on policy and value approximation updates to improve performance over the expert's performance. We show that our method learns good policies in a shorter time and using less data than classical policy gradient, which does not incorporate demonstration data into RL. Moreover, in terms of solution quality, it performs similarly to other state-of-the-art deep RL approaches.

Recent works using deep learning to solve routing problems such as the traveling salesman problem (TSP) have focused on learning construction heuristics. Such approaches find good quality solutions but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which can be easily extended to more generalk-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions faster than previous state-of-the-art deep learning methods for the TSP. We also show we can adapt the proposed method to two extensions of the TSP: the multiple TSP and the Vehicle Routing Problem, achieving results on par with classical heuristics and learned methods.

Water distribution networks have shown an increased rate of failure due to material deterioration. In this paper, we apply a Recurrent Neural Hawkes Process model to learn the failure intensity function of water pipes. The failure intensity function is learned based on two components: the base failure rate that is determined by the unique pipe profile attributes, and the effect of past failures. Compared to the existing solutions, our model is able to predict the time to next failure on an individual water pipe level. The learned failure intensity function is used to identify value points in the deterioration process of water pipes that represent their economical end-of-life. We use data from a Dutch water distribution network that consists of 49,600 km of pipelines to test the performance of the proposed model. We have made this dataset available online.

In Prognostics and Health Management (PHM) sufficient prior observed degradation data is usually critical for Remaining Useful Lifetime (RUL) prediction. Most previous data-driven prediction methods assume that training (source) and testing (target) condition monitoring data have similar distributions. However, due to different operating conditions, fault modes, noise and equipment updates distribution shift exists across different data domains. This shift reduces the performance of predictive models previously built to specific conditions when no observed run-to-failure data is available for retraining. To address this issue, this paper proposes a new data-driven approach for domain adaptation in prognostics using Long Short-Term Neural Networks (LSTM). We use a time window approach to extract temporal information from time-series data in a source domain with observed RUL values and a target domain containing only sensor information. We propose a Domain Adversarial Neural Network (DANN) approach to learn domain-invariant features that can be used to predict the RUL in the target domain. The experimental results show that the proposed method can provide more reliable RUL predictions under datasets with different operating conditions and fault modes. These results suggest that the proposed method offers a promising approach to performing domain adaptation in practical PHM applications.

In this work we study a dynamic pricing problem with demand censoring and limited price changes. In our problem there is a seller of a single product that aims to maximize revenue over a finite sales horizon. The seller does not know the form of the mean demand function but does have some limited knowledge. We assume that the seller has a hypothesis set of mean demand functions and that the true mean demand function is an element of this set. Furthermore, the seller faces a business constraint on the number of price changes that is allowed during the sales horizon. More specifically, the number of price changes that the seller is allowed to make is bounded above by a finite integer. We furthermore assume that the seller can only observe the sales (minimum between realized demand and available inventory) and thus that demand is censored. In each period the seller can replenish his inventory to a particular level. The objective of the seller is to set the best price and inventory level in each period of the sales horizon in order to maximize his profit. The profit is determined by the revenue of the sales minus holding costs and costs for lost sales (unsatisfied demand). In determining the best price and inventory level the seller faces and exploration-exploitation trade-off. The seller has to experiment with different prices and inventory levels in order to learn from historical sales data which contains information about market responses to offered prices. On the other hand, the seller also needs to exploit what it has learned and set prices and inventory levels that are optimal given the information collected so far. We propose a heuristic policy for this problem and study its performance using numerical experiments. The results are promising and indicate that the growth rate of regret of the policy is sub-linear with respect to the sales horizon.

We propose a Genetic Algorithm (GA) to address a Green Vehicle Routing Problem (G-VRP). Unlike classic formulations of the VRP, this study aims to minimise the CO2 emissions per route. The G-VRP is of interest to policy makers who wish to reduce greenhouse gas emissions. The GA is tested on a suite of benchmark, and real-world instances which include road speed and gradient data. Our solution approach incorporates elements of local and population search heuristics. Solutions are compared with routes currently used by drivers in a courier company. Reductions in emissions are achieved without incurring additional operational costs.