THE OPTIMAL NETWORK PROBLEM : SOME COMPUTATIONAL PROCEDURES
IN ATTEMPTS TO SIMULATE THE SPATIAL DEVELOPMENT OF REAL TRANSPORTATION NETWORKS, THE DEVELOPMENT OF A SIMPLE NETWORK-GENERATING PRINCIPLE THAT APPROXIMATES SOME OF THE MAJOR PROCESSES OCCURING IN REALITY IS IMPORTANT BOTH AS AN ANALYTICAL TOOL AND AS A PLANNING MECHANISM. THE PROBLEM CONSIDERED IN THIS PAPER IS TO ESTABLISH A SET OF ARCS LINKING TOGETHER A GIVEN SET OF VERTICES SUCH THAT THE SUM OF THE SHORTEST DISTANCES (OR AT LEAST TRANSPORT COSTS) BETWEEN EASH PAIR OF VERTICES IS A MINIMUM. NO VERTEX MAY BE OMITTED FROM THE NETWORK, AND ARC-INTERSECTIONS MAY OCCUR ONLY AT THE PREDETERMINED LOCATIONS OF THESE VERTICES. IN ADDITION, AN IMPLIED CONDITION OF THE PROBLEM IS THAT ANY FLOWS THROUGH THE COMPUTED NETWORK ALWAYS INCUR ZERO CONGESTION COSTS. THREE ALTERNATIVE APPROACHES TO THE SOLUTION OF THE OPTIMAL NETWORK PROBLEM ARE CONSIDERED. FIRST, THE POSSIBILITIES OF APPLYING INTEGER PROGRAMMING TO THE SOLUTION OF THE PROBLEM ARE EXAMINED BRIEFLY. SECOND, A BACKTRACK PROGRAMMING SOLUTION ALGORITHM IS PROPOSED THAT DEMANDS LENGTHY ARITHMETICAL OPERATIONS BUT REQUIRES ONLY SMALL AMOUNTS OF STORAGE DURING THE SOLUTION PROCESS. THIRD, TWO APPROXIMATIVE ALGORITHMS ARE PROPOSED. THESE ALGORITHMS REQUIRE ONLY RELATIVELY SMALL AMOUNTS OF ARITHMETIC AND STORAGE, AND APPEAR TO GUARANTEE AT LEAST A GOOD APPROXIMATION TO OPTIMALITY. /TSR&A/
-
Supplemental Notes:
- Vol 3, pp 201-210
-
Authors:
- SCOTT, A J
- Publication Date: 1969
Media Info
-
Serial:
- Transportation Research /UK/
- Volume: 3
- Issue Number: 2
- Publisher: Pergamon Press, Incorporated
Subject/Index Terms
- TRT Terms: Algorithms; Costs; Information processing; Mathematical analysis; Networks; Optimization; Shortest path algorithms; Transportation
- Uncontrolled Terms: Transportation systems
- Old TRIS Terms: Minimum path
- Subject Areas: Operations and Traffic Management; Transportation (General);
Filing Info
- Accession Number: 00227294
- Record Type: Publication
- Source Agency: Traffic Systems Reviews & Abstracts
- Files: TRIS
- Created Date: Jun 11 1971 12:00AM