A New Approach for the Asymmetric Traveling Salesman Problem with Replenishment Arcs

Here, we present a new arc-based formulation for the Asymmetric Traveling Salesman Problem with Replenishment Arcs, which is an extension of the Asymmetric Traveling Salesman Problem, with constraints on subpaths of the tour. This problem is commonly modeled using a path-based formulation which is shown to be computationally challenging in solving large scale problems. To address these challenges, we adapt a novel modeling approach, originally proposed for the one-dimensional cutting stock and assortment problem, which does not require pre-specification of cutting patterns. Our arc-based formulation does not require pre-specification of feasible paths but instead generates feasible paths and constructs a tour simultaneously. We also develop a sharp augmented Lagrangian based solution method that uses an ant colony optimization algorithm to solve subproblems. A version of this solution method was previously applied to aircraft maintenance routing problem in [K.G. Bulbul, R. Kasimbeyli, Augmented Lagrangian Based Hybrid Subgradient Method for Solving Aircraft Maintenance Routing Problem, Computers & Operations Research, 32(2021), 105294]. In this paper, an enhanced version of this hybrid method is introduced in the sense of complexity and efficiency. The problem is solved for 180 randomly generated instances by using both a commercial solver and the proposed sharp augmented Lagrangian based method. Moreover, the proposed formulation and solution approach is implemented on the aircraft maintenance routing problem, by adding an extra side constraint, and tested on 11 instances given in the aforementioned study. The results obtained from these computational experiments show the effectiveness of the proposed method