Premium
New assignment‐based neighborhoods for traveling salesman and routing problems
Author(s) -
Glover Fred,
Rego Cesar
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21801
Subject(s) - travelling salesman problem , leverage (statistics) , 2 opt , traveling purchaser problem , mathematical optimization , computer science , routing (electronic design automation) , vehicle routing problem , class (philosophy) , combinatorial optimization , perspective (graphical) , flexibility (engineering) , mathematics , artificial intelligence , computer network , statistics
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.