ResearchGate 

Currently Publishing:

Richter Peter H.:


Open and Closed Tours’ Efficient Determination in General Directed Graphs
Meeting the Asymmetric Steiner Traveling Salesman Path Problem (ASTSPP)

     Abstract

The Asymmetric Steiner Traveling Salesman Path Problem (ASTSPP) as a relative of the classical Traveling Salesman Problem (TSP) seems unattended till now despite its high practical importance for real-time navigation in digital traffic nets! For the ASTSPP we start from a graph with asymmetric arc weights, a start point s, target point t, and a subset S of the graph’s nodes not containing s and t. The objective is to find a minimal cost s-t-walk visiting all nodes of S at least once. We present a new efficient deterministic solution approach. The implemented and exhaustively tested polynomial time algorithm relies on an Advanced Scan of Spanning Trees (ASST) applied to approximate Steiner trees T G spanning S.  The new optimization feature Background Structure Analysis (BSA) overcomes “flaws” of T hampering good results. BSA determines verifiable proposals applied to change T to a new tree T' being a trimmed successor tree of T whose scanning afterwards most probably provides better results. Running ASST and BSA together with optimization feature Confined Complete Enumeration (CCE), the proposed algorithm yields a convincing maximal sample standard deviation qmax ≤ 1,86 %  compared to optimal results for |S| < 15. It accommodates demands for an efficient algorithm running on nets like traffic maps that have not to be complete graphs and that generally have asymmetric arc weights not required to comply with the triangle inequality. Finally yet importantly, the algorithm comes up to the request determining round trips (s= t) and general routes (s≠ t) without any special precaution.

 

[21]   Richter, Peter  H..:  :
AMSP and ATSP - Asymmetric Multi-Stopover and Asymmetric Traveling Salesman Problem - Two Efficient Algorithms each near-optimally Solving both Problems

  ResearchGate 19.04.2013,     Example

[20]   Richter, Peter  H..:
Asymmetric Traveling Salesman Problem – Near Optimal Real-time Computation,  ATOS 2010,
1st International Air Transport and Operations Symposium, 14. - 16. April  2010, Delft, the Netherlands,
Proceedings of ATOS 2010I:
ISBN 978-1-60750-559-4 (online), Publisher: Delft University Press

[19]   Richter, Peter  H..:
 
Asymmetric Traveling Salesman and Multi-stopover Problem with Turn Restrictions - Exact Real-Time Computation for Stopovers £ 10,   CEAS 2009 European Air and Space Conference (ISBN 1 85768 208 4, ISBN 1 85768 22130) , 26 -29 October 2009, Manchester, UK

[18]   Richter, Peter  H..:
 Efficient Communication in Self-organizing Sensor Nets - Mathematical Foundation, Optimization Algorithm, Simulation
    CEAS 2009
European Air and Space Conference (ISBN 1 85768 208 4), 26 -29 October 2009, Manchester, UK

[17]   Richter, Peter  H..:
Efficient Double Root Optimal Path Determination,
1 st CEAS European Air and Space Conference, ID CEAS-2007-706, Berlin, 10.-13.9.2007, ISSN 0700-4083 (DGLR Bonn, Germany)

[16]   Richter, Peter  H..:
 Optimal Path Determination Observing Turn Restrictions,
1 st CEAS European Air and Space Conference, ID CEAS-2007-707, Berlin, 10.-13.9. 2007, 0700-4083 (DGLR Bonn, Germany)

[15]   Richter, Peter  H..:
Traffic Flow Layout Optimization Minimizing Routing Cost and Capacity Constraints / Road Charges,
DGLR Kongress 2006, Braunschweig, Nov 6 – Nov 9, 2006, zu dem in Jahrbuch Band II / 2006 der DGLR: ISSN 0070-4083, DGLR-2006-157    

[14]   Richter, Peter  H..:
The Efficient Determination of Optimal Traffic Flow Layouts with Respect to both Transportation Cost and Road Charges,
ITSC'05 - 8th International IEEE Conference (PIN 11288), 13 - 16 Sep 2005 Vienna Austria

[13]   Richter, Peter  H..:
Wiring Layout Design Reducing Cable and Trace Cost,
ISATA 2000, Dublin, Irland, 25. - 27.9. 2000. Simultaneous Engineering and Rapid Product Development, ISBN 1-902856-13-9, page 61-68. Distinction:
Award for the best paper in the Track on Simultaneous Engineering and Rapid Product Development.

[12]   Richter, Peter H..:The General Tracing Problem in Graphs -An Efficient Constructive Algorithm,
5th International Symposium on Operations Research 279-285, ISBN 961-6165--08-9, Preddvor / Slovenia, Sep 30 - Oct 2, 1999.

[11]   Richter Peter H.:    
The Efficient Embedding of Flow Graphs into Layout Graphs with Respect to Flow Intensity Weighted Minimum Tracing Cost, MCC'99 Zagreb, 21.-26.6.1999.

[10]   Richter, Peter  H..:
Semi-Quadratic Assignment Problem - Pragmatic Change of the QAP's Domain Enables Attractive e-Approximation,
Keynote Lecture at the SSCC'
98 (Durban, South Africa, Sep 22-24.98, Advances in Systems, Signals, Control and Computers, Vol. 1, Ed. by V.B.Bajic, ISBN 0-620-23137-8, 1998, 69-75

[9]     Richter Peter H.:
Efficient Deterministic Approaches Solving the General Connection Problem in Graphs,
15th IMACS World Congress on Scientific Computation, Modeling and Applied Mathematics, Berlin, Aug 1997, Volume 2 'Numerical Mathematics'. 255-260, ISBN 3-89685-552-2, Wissenschaft und Technik Verlag Dr. Jürgen Groß

[8]     Richter Peter H.:
Efficient Shortest Path Algorithms for Road Traffic Optimization, 27th International Symposium on Advanced Transportation Applications
(ISATA): Dedicated Conference on Advanced Transport Telematics, ISBN 0947719652, Aachen, 31.10.-4.11.1994, 79-86

[7]     Richter, Peter  H..:
Present Approximate Algorithms for Steiner's Problem in Graphs - Classification and Two New Fast Approaches,
Systems Science (PL ISSN 0137-1223); Volume 17 - Number 2 1991 2-28.

[6]     Richter Peter H.:
Fabrikplanung mit Flußnetzen: Layoutoptimierung unter Berücksichtigung von Transportnetzen am Beispiel des Maschinen-Layout-Problems (Designing Plant Layouts Considering Transport Nets: Layout Optimization Exemplary Shown at the Machine Layout Problem) ZWFCIM, 10/91 (ISSN 0932-0482), #86. 1991, S. 496-499.

[5]     Richter Peter H.:
The Machine Layout Problem Considering Transport Nets,
Artificial Intelligence & Industrial Application, Leningrad, USSR, 16.-19. April 1990, 382-387.

[4]     Richter Peter H.:
A Graph-Theoretic Approach Tackling the Machine Layout Problem in FMS with Respect to Transport Networks,
Flexible Automation 90, Bratislava, 20.-23. February 1990, CSSR.

[3]     Richter Peter  H.:
Two New Efficient Approximate Algorithms Solving Steiner's Problem in Graphs,
Systems Science X, International Conference on Systems Science, scientific paper No.7, September 19-22, 1989, Wroclaw, Polen.

[2]     Richter Peter H.; Döring S.; Schiemangk C.; Taraszow O.:
Program System NETOPT, Optimization of Connection Structures in Graphs,
Ed. Iwainsky, A.; ZKI Berlin, 1985.

[1]     Richter Peter H.; Taraszow O.:
Random Graph Generation, Optimization of Connection Structures in Graphs, Ed. Iwainsky, A.; ZKI Berlin, 1985.

 

Impressum           AGB

Problems, comments or questions? Please use the Feedback-Page..
Last  modification: April 2020
© by O&S Consultancy