(January 18, 2018) Dr. Subhash Sarin, the Paul T. Norton Endowed Professor in the ISE department, proposed a solution to the “traveling salesman” problem in collaboration with Dr. Hanif Sherali, Professor Emeritus in ISE, and Dr. Maichel Aguayo, an ISE alumnus and assistant professor at University of Concepción. A summary of their work was featured in ISE Magazine in December 2017 (Page 51).
According to ISE Magazine, Asymmetric Traveling Salesmen Problems (ATSP) can be described as a difficult issue of finding the optimal route for a vehicle, which starts and ends the trip at the same location and must visit multiple locations only once while minimizing the total distance traveled. This problem was first made popular in the 1950’s and 1960’s by Rand Corp., who proposed a linear integer model and a cutting plane-based method for its solution. Since then, research has focused on handling these constraints in a judicious manner.
In their paper, Dr. Sarin, along with Drs. Sherali and Aguayo, presented a new way (called “decomposition-based method”) of handling these constraints, which produces a more effective solution for both ATSP and multiple traveling salesmen problem (mATSP). The proposed decomposition-based method outperforms a well-known method “Concorde” for solving ATSP, and produces near-optimal solutions for mATSP test instances. ISE Magazine states that the “proposed approach is easy to implement and can be used either to solve the ATSP or mATSP as standalone models or can be applied in contexts where they appear as substructures within some application settings.”
For more information, please go to the journal article “Solving the Single and Multiple Asymmetric Traveling Salesmen Problems by Generating Sub Tour Elimination Constraints from Integer Solutions” in the January 2018 issue of IISE Transactions (Vol. 50, No. 1, Pg 45-53).