Abstract

We study a variant of the traveling salesmen problem (TSP) known as the close-enough traveling salesman problem (CETSP). A salesman wants to find the shortest route that visits all customers and return to the starting location. The salesman is not required to visit the exact locations of the customers, but need only to get close enough to each customer. This feature allows savings from the classic TSP solution, but also adds complexity to the problem. The CETSP has applications in meter-reading using radio-frequency identification (RFID) technology and surveying ground targets using an airborne vehicle. We develop a Steiner zone variable neighbourhood search (SZVNS) heuristic to solve the CETSP. Our computational experiments over 700 instances demonstrate that SZVNS often produces optimal solutions to the small instances where optimal solutions are known. On the larger instances, SZVNS produces better or comparable solutions in less time when compared with the solutions produced by state-of-the-art heuristics.

Speaker Bio

Wang Xingyin is a lecturer at the Singapore University of Technology and Design (SUTD). After studying quantitative finance and receiving a bachelor’s degree (2011) at the National University of Singapore, Xingyin pursued a Ph.D. in applied mathematics at the University of Maryland – College Park. He received his doctorate in 2016 with a thesis on vehicle routing problems. After which, Xingyin joined the Science and Math Cluster and Engineering Systems and Design Pillar at SUTD. His research interests include vehicle routing and scheduling, heuristic methods, integer linear programming, and worst-case analysis.

For more information about the ESD Seminars Series, please contact Karthik Natarajan at karthik_natarajan@sutd.edu.sg.