Title: Solving the Traveling-Salesman Problem with Time Windows Using Tabu Search
Abstract: AbstractThis paper presents a robust tabu search approach to the traveling-salesman problem with time windows. The approach uses a two-level tour hashing scheme within a reactive tabu search procedure to detect unique repeated solutions and to promote a more diverse search. Strong feasibility conditions restrict the neighborhood of candidate solutions. The search returns optimal, or near-optimal, solutions within a fraction of the time required by optimal methods. The algorithm's search neighborhood is not restricted to feasible solutions, and superior marginally infeasible solutions are reported to enhance the decision making process. The paper presents computational results for 145 problems from the literature. Additional informationNotes on contributorsWilliam B. CarltonWilliam B. Carlton is an active duty officer in the U.S. Army. He recently completed a Ph.D. degree with the Graduate Program in Operations Research at the University of Texas at Austin. LTC Carlton is currently serving as a Senior Operations Research Analyst for the Operational Test and Evaluation Command, Alexandria, VA. In addition to several operational assignments, LTC Carlton has served as Material Systems Analyst in the Pentagon and as Assistant Professor in the Department of Engineering at the U.S. Military Academy, West Point, NY.J. Wesley BarnesJ. Wesley Barnes is the Cullen Trust for Higher Education Endowed Professor in Engineering at the University of Texas at Austin, and has been the Coordinator of the Graduate Program in Operations Research for 15 of the past 20 years. He is the author of several books, one of which won the Institute of Industrial Engineers Book of the Year Award. Professor Barnes's recent research focus has been in the application of direct search techniques to the solution of important complex scheduling problems.
Publication Year: 1996
Publication Date: 1996-08-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 71
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot