New assignment‐based neighborhoods for traveling salesman and routing problems. Issue 3 (9th January 2018)

• Record Type: Journal Article
• Authors: Glover, Fred; Rego, Cesar
• Is Part Of: Networks. Volume 71:Issue 3(2018)
• Page Start: 170
• Page End: 187
• Publication Date: 2018-01-09
• Subjects: exponential neighborhoods -- assign neighborhood -- combinatorial leverage -- ejection chains -- heuristics -- local search -- traveling salesman problem -- vehicle routing; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21801
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : We introduce a new class of assignment‐based neighborhoods for symmetric and asymmetric traveling salesman problems that exhibits a combinatorial leverage property, by which a tour can be generated in polynomial time that dominates an exponential number of other tours. The ejection chain perspective motivating the new neighborhoods differs from that underlying the most general assignment‐based neighborhoods proposed in the past, giving rise to new tour constructions that encompass and go beyond previous proposals. The resulting neighborhoods provide greater flexibility for generating new tours while simultaneously accounting for sparse traveling salesman graphs that were previously omitted from consideration. Finally, our approaches are applicable for improving the solution of some versions of the vehicle routing problem.