When conducting seafloor mapping operations from a vessel at sea, a plan of parallel lines spaced to ensure adequate overlap in the mapping data are laid out in advance and then systematically followed by human or robotic survey vessels. During the course of survey, it is not uncommon to omit portions of lines, for example, to deviate from the line to avoid other vessels or hazards to navigation, or to need to re-run portions of lines, for example when the INS-aided GPS navigation uncertainty is temporarily too large to meet the uncertainty requirements of the project.  These events cause “holidays” or holes in bathymetric surfaces created from the data collection effort if not remedied. Therefore, at the end of several days of systematic survey, an effort is made to repeat the survey lines that have been omitted. To do so in an optimal way, a routine has been developed to solve the Traveling Salesman Problem for a set of arbitrary survey lines. The algorithm extends an existing approximate solution to the standard point-wise TSP problem, so-called “two-opt swap”. The routine considers each step as the length of a line segment plus the path length to an arbitrary next line segment. In addition, the routine allows for the traversal of each line segment in either direction. The strategy for development of the algorithm will be presented along with simulated results.