HEURISTICS AND GRAPHICS FOR THE SHORTEST NETWORK PROBLEM

The problem of the design of the shortest network is studied and a simple heuristic technique is developed for its solution. Computational results illustrate and evaluate the technique. Computer graphics when used in conjunction with the algorithm make intelligent human intervention possible. The report shows that simple heuristics are a practical way to address the Steiner problem, i.e. the problem of design of the shortest network linking a set of given points. The heuristic algorithm utilizes certain properties of the optimal solution to rule out certain configurations as nonoptimal and to improve others. This report describes in detail the problem, the algorithm, and the computational results.

• Corporate Authors:

  General Motors Corporation

  Research and Development Center, 30500 Mound Road
  Warren, MI  United States  48090
• Authors:
  • Bhaskaran, S
• Publication Date: 1985-10-28

Media Info

• Features: Appendices; Figures; References; Tables;
• Pagination: 22 p.

Subject/Index Terms

• TRT Terms: Algorithms; Computer graphics; Heuristic methods; Networks
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; Society; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00458181
• Record Type: Publication
• Files: TRIS
• Created Date: Sep 30 1987 12:00AM