OPTIMAL DYNAMIC ROUTING IN COMMUNICATION NETWORKS WITH CONTINUOUS TRAFFIC

New characterizations of optimal state-dependent routing strategies are obtained for the continuous traffic network model proposed by Segall for linear cost with unity weighting at each node and for constant inputs. The concept of flow relaxation is introduced and is used to transform the optimal routing problem into an initial flow optimization problem with convex cost and linear constraints. Three algorithms are given for open-loop computation of the optimal initial flow. The first is a simple iterative algorithm based on gradient descent with bending and it is well suited for decentralized computation. The second algorithm reduces the problem to a series of max-flow problems and it computes the exact optimal flow in O (mod N to the fourth) computations, where mod N is the number of nodes in the network. The third algorithm is based on a search for successive bottlenecks in the network. (Author/TRRL)

• Corporate Authors:

  John Wiley & Sons, Incorporated

  111 River Street
  Hoboken, NJ  United States  07030-6000
• Authors:
  • Hajek, B
  • Ogier, R G
• Publication Date: 1984

Media Info

• Features: Figures; Photos; References;
• Pagination: p. 457-487
• Serial:
  • NETWORKS
  • Volume: 14
  • Issue Number: 3

Subject/Index Terms

• TRT Terms: Bottlenecks; Communication systems; Costs; Itinerary; Mathematical models; Networks; Optimization; Routing; Traffic flow
• Uncontrolled Terms: Optimum; Traffic networks; Transportation networks
• ITRD Terms: 630: Bottleneck; 224: Cost; 699: Itinerary; 6473: Mathematical model; 1054: Network (traffic); 671: Traffic flow
• Subject Areas: Finance; Highways; Operations and Traffic Management; I71: Traffic Theory;

Filing Info

• Accession Number: 00393292
• Record Type: Publication
• Source Agency: Transport Research Laboratory
• Files: ITRD, TRIS
• Created Date: Jun 30 1985 12:00AM