New assignment‐based neighborhoods for traveling salesman and routing problems. Issue 3 (9th January 2018)
- Record Type:
- Journal Article
- Title:
- New assignment‐based neighborhoods for traveling salesman and routing problems. Issue 3 (9th January 2018)
- Main Title:
- New assignment‐based neighborhoods for traveling salesman and routing problems
- Authors:
- Glover, Fred
Rego, Cesar - 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.
- Is Part Of:
- Networks. Volume 71:Issue 3(2018)
- Journal:
- Networks
- Issue:
- Volume 71:Issue 3(2018)
- Issue Display:
- Volume 71, Issue 3 (2018)
- Year:
- 2018
- Volume:
- 71
- Issue:
- 3
- Issue Sort Value:
- 2018-0071-0003-0000
- 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 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0037 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/net.21801 ↗
- Languages:
- English
- ISSNs:
- 0028-3045
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 6077.205000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 5999.xml