Paper #216
A New Mathematical Model for the Asymmetric Traveling Salesman Problem
Presenting author: Hour Almadhaani
Session: I12
Abstract
Last-mile delivery is one of the most costly and complex stages of logistics, especially in urban areas where travel distances are affected by road direction, traffic conditions, and access restrictions. This paper studies the Asymmetric Traveling Salesman Problem (ATSP) as a routing framework for last-mile delivery optimization. A binary integer programming model is proposed to determine the visiting order of customers and the directed movements between consecutive positions in the tour. The model assigns each customer to exactly one position, ensures that all customers are visited once, and returns the route to the depot while minimizing the total directed travel cost. The proposed formulation is implemented in Python and solved using Gurobi Optimizer. Computational experiments are conducted on ATSP benchmark instances, including four different instances. The results show that the model generates valid ATSP routes and performs efficiently for small instances, achieving a solution time of 0.01 seconds for 4.atsp. However, the solution time increases for larger instances due to the growth of transition variables. The proposed model is compared with classical ATSP formulations, including MTZ, GP, MCF, PQ, and SST. The findings show that the model provides a clear and interpretable route structure, while future work will focus on improving its computational performance for larger-scale instances.