91. The Generalized Traveling Salesman Path Problem GTSPP – An impactful construction algorithm
Invited abstract in session TE-1: Travelling salesperson, stream Travelling salesperson.
Thursday, 16:30 - 18:00Room: L226
Authors (first author is the speaker)
| 1. | Peter H, Richter
|
| Development, O&S Consultancy |
Abstract
The GTSPP looks in asymmetric directed graphs, whose nodes are partially segmented into several classes S (services, clusters), for a shortest walk from a given start s to a given target t such that each class is visited at least once. The proposed construction method arises from the problem’s decomposition into (a) Search for a Densest Set S of Service Locations (shortly Service Location Cloud Problem SLCP) containing at least one location each service such that the sum of the distances among these locations as well as to s and t is minimal and (b) the Asymmetric Steiner Traveling Salesman Path Problem ASTSPP that looks for a shortest s-t-walk through all these nodes S. A novel SLCP algorithm determines the service location cloud S and a novel ASTSPP algorithm builds and scans an approximate Steiner tree T(S) to get a shortest walk from s to t through S using a new meta-heuristic Advanced Scan of Spanning Trees ASST. During this scan another new meta-heuristic Tree Structure Adaption TSA tries to find proposals to change this tree T(S) afterwards to a mutated one T'(S) whose scan most probably provides a shorter walk. Tests on large high density digraphs reveal that the proposed deterministic algorithm gets near-optimal results with a sample standard deviation q_max= 2,5% in real-time.
Keywords
- Combinatorial Optimization
- Algorithm and Computational Design
- Heuristics and meta-heuristics
Status: accepted
Back to the list of papers