In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer’s encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

This paper introduces a time efficient deep learning-based solution to the traveling salesman problem with time window (TSPTW). Our goal is to reduce the total tour length traveled by -*the agent without violating any time limitations. This will aid in decreasing the time required to supply any type of service, as well as lowering the emissions produced by automobiles, allowing our planet to recover from air pollution emissions. The proposed model is a variation of the pointer networks that has a better ability to encode the TSPTW problems. The model proposed in this paper is inspired from our previous work that introduces a hybrid context encoder and a multi attention decoder. The hybrid encoder primarily comprises the transformer encoder and the graph encoder; these encoders encode the feature vector before passing it to the attention decoder layer. The decoder consists of transformer context and graph context as well. The output attentions from the two decoders are aggregated and used to select the following step in the trip. To the best of our knowledge, our network is the first neural model that will be able to solve medium-size TSPTW problems. Moreover, we conducted sensitivity analysis to explore how the model performance changes as the time window width in the training and testing data changes. The experimental work shows that our proposed model outperforms the state-of-the-art model for TSPTW of sizes 20, 50 and 100 nodes/cities. We expect that our model will become state-of-the-art methodology for solving the TSPTW problems.

In this study, we propose a general method for tackling the Pickup and Drop-off Problem (PDP) using Hybrid Pointer Networks (HPNs) and Deep Reinforcement Learning (DRL). Our aim is to reduce the overall tour length traveled by an agent while remaining within the truck’s capacity restrictions and adhering to the node-to-node relationship. In such instances, the agent does not allow any drop-off points to be serviced if the truck is empty; conversely, if the vehicle is full, the agent does not allow any products to be picked up from pickup points. In our approach, this challenge is solved using machine learning-based models. Using HPNs as our primary model allows us to gain insight and tackle more complicated node interactions, which simplified our objective to obtaining state-of-art outcomes. Our experimental results demonstrate the effectiveness of the proposed neural network, as we achieve the state-of-art results for this problem as compared with the existing models. We deal with two types of demand patterns in a single type commodity problem. In the first pattern, all demands are assumed to sum up to zero (i.e., we have an equal number of backup and drop-off items). In the second pattern, we have an unequal number of backup and drop-off items, which is close to practical application, such as bike sharing system rebalancing. Our data, models, and code are publicly available at Solving Pickup and Dropoff Problem Using Hybrid Pointer Networks with Deep Reinforcement Learning.

City bikes and bike-sharing systems (BSSs) are one solution to the last mile problem. BSSs guarantee equity by presenting affordable alternative transportation means for low-income households. These systems feature a multitude of bike stations scattered around a city. Numerous stations mean users can borrow a bike from one location and return it there or to a different location. However, this may create an unbalanced system, where some stations have excess bikes and others have limited bikes. In this paper, we propose a solution to balance BSS stations to satisfy the expected demand. Moreover, this paper represents a direct extension of the deferred acceptance algorithm-based heuristic previously proposed by the authors. We develop an algorithm that provides a delivery truck with a near-optimal route (i.e., finding the shortest Hamiltonian cycle) as an NP-hard problem. Results provide good solution quality and computational time performance, making the algorithm a viable candidate for real-time use by BSS operators. Our suggested approach is best suited for low-Q problems. Moreover, the mean running times for the largest instance are 143.6, 130.32, and 51.85 s for Q = 30, 20, and 10, respectively, which makes the proposed algorithm a real-time rebalancing algorithm.