Search

Capacitated vehicle routing problem is one of the classic combinatorial optimization problems, which has been studied repeatedly for many years. Recently, Transformer has become the dominant deep learning architecture for solving vehicle routing problems. However, traditional positional encoding method is not suitable for extracting location information for dynamic optimization problems. The state of an instance is changed according to the model at different construction steps, and the node features should be updated correspondingly. Therefore, current methods have poor effect on improving learning efficiency. With the goal of minimizing the routing length, a dynamic graph transformer model (DGTM) and a dynamic positional encoding (DPE) method are proposed, and a double-loss REINFORCE algorithm is used to train the DGTM model. In addition, reinforcement learning, graph neural networks and Transformer architecture are combined to improve the training efficiency of the model. It enhances the information representation of the neural network for routing problems with constraints. The experimental results show that the optimization of the model on this problem outperforms current deep reinforcement learning methods and some traditional algorithms. The DGTM model has better overall performance than the professional solver and has good generalization performance, which provides an effective method for solving the combinatorial optimization problems on graphs. [ABSTRACT FROM AUTHOR]

The capacitated vehicle routing problem (CVRP) is a classical combinatorial optimization problem having a wide range of practically important applications in operations research. As most combinatorial problems, CVRP is strongly NP-hard (even on the Euclidean plane). A metric instance of CVRP is APX-complete, so it cannot be approximated to arbitrary prescribed accuracy in the class of polynomial time algorithms (assuming that ). Nevertheless, in the case of finite-dimensional Euclidean spaces, a quasi-polynomial or even polynomial time approximation scheme can be found for the problem by applying an approach based on works by S. Arora, A. Das, and C. Mathieu. Below, this approach has been extended for the first time to a significantly larger class of metric spaces of fixed doubling dimension. It is shown that CVRP formulated in such a space has a quasi-polynomial time approximation scheme whenever the number of routes in its optimal solution is bounded above by a polynomial in the logarithm of the input size. [ABSTRACT FROM AUTHOR]

In capacitated vehicle routing problem (CVRP), a fleet of vehicles with a certain capacity starts at a central depot and returns to this starting point after serving some customers by using the optimal set of routes with the minimum cost. However, in real-life, environments may include obstacles such as holes, machines, or trees of different sizes. In this research, a CVRP extension is proposed that is the problem of the classical one for the environments with various sized circular obstacles. To solve this problem, a hybrid meta-heuristic algorithm based on genetic algorithms improved by a local search was developed. Additionally, a visual simulation tool was designed to place obstacles and locations in the working space. The developed algorithm was tested for different customer-obstacle counts and obstacle sizes with various obstacle occupancies in the environment. The results obtained are presented and the problem's potential applications are discussed. [ABSTRACT FROM AUTHOR]

With the rapid development of e-commerce, logistics industry becomes a crucial component in the e-commercial ecological chain. Impelled by both economical and environmental benefit, logistics companies demand automated tools more urgently than ever. In this paper, a dynamic logistic dispatching system is proposed. The underlying model of the dispatching system is the dynamic vehicle routing problem which allows new orders being received as the working day progress. With this feature, the system becomes more practical than the systems with traditional static vehicle routing models, but is also more challenging as the vehicles must be scheduled in a dynamic way. The core of the system is a specially designed set-based particle swarm optimization algorithm. According to the characteristic of the problem, a new encoding scheme is defined by set and possibility, and a local refinement method is designed to accelerate the convergence speed of the algorithm. In addition, two more techniques: 1) region partition and 2) archive strategy are incorporated in the dispatching system to reduce the complexity of the problem and to facilitate the optimization process, helping the dispatcher control the vehicles in real time. The proposed system is tested on various benchmarks with different scales. Experimental results show that the proposed dispatching system is effective. [ABSTRACT FROM AUTHOR]

This paper proposed a multi-objective model for capacitated vehicle routing problem (CVRP)facing different target preference (MOCVRPFDTP)to solve CVRP more effectively and evaluate transportation cost comprehensively. There were three different preference structures in this model, which were joint optimization of loading and CVRP, absolute minimum vehi-cles preference, and path optimization preference. To solve this model, this paper constructed an algorithm framework with cor-responding algorithms. In experiments, the model and its solving methods display satisfactory performance in the testing for VR-PLIB, and they are more suitable for practical instance. [ABSTRACT FROM AUTHOR]

Distribution, location and routing systems have significant impacts on a company's competitiveness, particularly with regard to transportation and service costs. Therefore, designing strategies to minimize costs is a recommended alternative for organizations. This paper presents a suggested routing and location scheme for distribution centers based on the use of linear programming algorithms and Gillet and Miller's heuristics for a company that produces olive oil and sells it in supermarket chains in Barranquilla, Colombia. The implemented techniques reveal, as a result, the location and dimensioning of a single distribution center in the downtown area and not several, as expected. A recommendable routing for each client is also proposed. [ABSTRACT FROM AUTHOR]

This article presents the variable neighbourhood simulated annealing (VNSA) algorithm, a variant of the variable neighbourhood search (VNS) combined with simulated annealing (SA), for efficiently solving capacitated vehicle routing problems (CVRPs). In the new algorithm, the deterministic ‘Move or not’ criterion of the original VNS algorithm regarding the incumbent replacement is replaced by an SA probability, and the neighbourhood shifting of the original VNS (from near to far byk←k+1) is replaced by a neighbourhood shaking procedure following a specified rule. The geographical neighbourhood structure is introduced in constructing the neighbourhood structures for the CVRP of the string model. The proposed algorithm is tested against 39 well-known benchmark CVRP instances of different scales (small/middle, large, very large). The results show that the VNSA algorithm outperforms most existing algorithms in terms of computational effectiveness and efficiency, showing good performance in solving large and very large CVRPs. [ABSTRACT FROM AUTHOR]

The Vehicle Routing Problem (VRP) is one of the most optimized tasks studied and it is implemented in a huge variety of industrial applications. The objective is to design a set of minimum cost paths for each vehicle in order to serve a given set of customers. Our attention is focused on a variant of VRP, the capacitated vehicle routing problem when applied to natural gas distribution networks. Managing natural gas distribution networks includes facing a variety of decisions ranging from human resources and material resources to facilities, infrastructures, and carriers. Despite the numerous papers available on vehicle routing problem, there are only a few that study and analyze the problems occurring in capillary distribution operations such as those found in a metropolitan area. Therefore, this work introduces a new algorithm based on the Saving Algorithm heuristic approach which aims to solve a Capacitated Vehicle Routing Problem with time and distance constraints. This joint algorithm minimizes the transportation costs and maximizes the workload according to customer demand within the constraints of a time window. Results from a real case study in a natural gas distribution network demonstrates the effectiveness of the approach. [ABSTRACT FROM AUTHOR]