Analysis of Decoding Strategies for Transformer-Based Solution of Multi-Depot Vehicle Routing Problems

Multi-Depot Vehicle Routing Problem (MDVRP) is a well-known problem with many real-world applications in supply chains. In MDVRP, a set of customer nodes needs to be served by a fleet of vehicles supplied by multiple depots. Each vehicle starts from a depot, visits a subset of customers in a sequential order, and then returns to the original depot. Finding the optimal solution to this NP-hard problem can be challenging in the area of distribution and logistics. The goal is to find (near-)optimal routes that minimize the total transportation costs. We solve and improve the model using a transformer-based encoder-decoder architecture that has been originally proposed for neural machine translation. Our proposed method produces a set of consecutive actions which assign each vehicle to a certain customer node using a decoding strategy at each decoding step. After training, the model has low inference time, and produce high-quality solutions in a few seconds for variant number of customers which is faster compared to other exact and approximate approaches. In this paper, we investigate the impact of different decoding strategies, including greedy, multinomial sampling, and beam search, on solution quality. An ensemble decoding strategy is presented which further improves the efficiency of the transformer architecture in finding near-optimal MDVRP solutions in 2 out of every 3 cases on average. We compare the results of our proposed transformer architecture to original transformer and an extension of Lin-Kernighan heuristic solver (LKH-3) which has found many best-known solutions for well-known benchmarks.