Issue link: https://industrialengineer.epubxp.com/i/905872
December 2017 | ISE Magazine 51 Going around in circles, yet getting the job done It is not uncommon to find situations in the logistics environment where a ve- hicle must be routed among customers on a given day to make the deliveries as quickly or as efficiently as possible. The key question is to determine the vehicle's route given the customers' lo- cations. This well-known but difficult issue is called the traveling salesman problem. It can be concisely stated as follows: Given a complete graph, a base location from where the vehicle begins its jour- ney, and an asymmetric distance matrix of customer locations, determine an optimal tour that starts and ends at the base location after having visited each customer exactly once while minimiz- ing the total distance traveled (denoted as ATSP). This problem was among the first set of problems shown by Richard Karp to be NP-complete, thus estab- lishing the computational difficulty of obtaining an optimal solution. In case multiple vehicles have to be routed over a given number of customers so that they collectively cover all the custom- ers only once, the problem of deter- mining such multiple tours is called the multiple traveling salesmen problem (mATSP). This problem is easy to visualize in the context of movements of a ve- hicle from one place to another. And it is, in fact, encountered in various other application areas as well, includ- ing production scheduling (whenever processing of jobs involves sequence- dependent setups) as well as DNA se- quencing and microchip layout. This problem was made popular by the researchers at the Rand Corp. in the 1950s and 1960s, where, for the first time, they proposed a linear integer model and a cutting plane-based meth- od for its solution. Such a model formu- lation consists of constraints that avoid forming subtours (partial tours), which are known as subtour elimination con- straints. Research over the years has focused on judiciously handling these constraints. In their paper "Solving the Single and Multiple Asymmetric Traveling Sales- men Problems by Generating Sub Tour Elimination Constraints from Integer Solutions," Subhash C. Sarin, Hanif D. Sherali and their student Maichel M. Aguayo present a new way of han- dling these constraints that has led to an effective solution for both ATSP and mATSP. The proposed decomposition- based method outperforms Concorde, a well-known exact method for solv- ing ATSP, and enables the solution to near optimality of all the challenging mATSP test instances of sizes ranging from 443 to 1,001 cities that appear in the literature. In fact, only one instance of a size greater than 443 cities achieved a solution using one of the existing for- mulations from the literature, but that solution had a much larger optimality gap. The proposed approach is easy to im- plement 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. CONTACT: Subhash C. Sarin; sarins@vt.edu; (540) 231-7140; Grado Department of Industrial and Systems Engineering, 1145 Perry St., Durham Hall, Room 250, Virginia Tech, Blacksburg, VA 24061. Best practices for setting up a financial sharing system The sharing economy is a key concept for understanding today's economic systems. People share their houses with tourists (e.g., via Airbnb), use on-de- mand ridesharing networks (e.g., Uber and Lyft) and raise money by means of crowdfunding and peer-to-peer lend- ing. Although sharing seems like a new and unprecedented economic phenom- enon, a system for sharing of funds has existed in some parts of the world for thousands of years. A rotating savings and credit association (ROSCA) is a microfinance system that people orga- nize with friends, relatives and other acquaintances. Financial technology companies are now trying to combine the ROSCA concept with their inter- net-based technologies. Relatively little technical research has been conducted on this financial sharing system. Important aspects of Subhash C. Sarin (from left), Hanif D. Sherali and Maichel M. Aguayo have proposed an easy-to-implement solution to the traveling salesman problem. In this research summary we highlight one of the articles from Volume 62, No. 3 of The Engineering Economist. Rotating savings and credit associations are a form of the sharing economy in the financial sector. Although these microfinance systems have long existed, they have not been analyzed rigorously before. Here, the authors show how to set the interest rate and prioritize members for receiving the funds collected.