This dissertation presents two applications of multi-commodity network routing problems, one in the area of telecommunication network operation and the other in the area of cash management for the banking industry. For the telecommunication problem, the multiple commodities arise from the multiple origin-destination demand pairs that must share the capacity of a fiber optical link. For the cash management problem, the commodities are associated with the various denominations (ones, fives, tens, twenties, fifties, hundreds, and various coins) that share the capacity of armed trucks and storage vaults.

Dijkstra’s simple shortest path algorithm provided the building block for link-state routing protocols in data networks. The open shortest path first (OSPF) protocol uses this algorithm in a distributed procedure in an attempt to balance the trade-off between routing implementation complexity and optimal network utilization. Today, powerful optimization software tools are available that can be used by a central processor in an attempt to improve network performance via implementation of better routing strategies. Two environments can be considered. In the first case, the routing software remains unchanged and the central processor simply determines optimal link weights that are supplied to the routers. Each router uses the link weights and Dijkstra’s algorithm to determine its routing table. In the second environment, the routing software is modified to accept an optimal routing table. Chapter 2 of this dissertation presents both node-arc and arc-path optimization models for both environments, along with an empirical analysis of all four models.

The Federal Reserve Bank (Fed) provides currency services to banks. These services include sorting currency into fit and non-fit bills and repackaging bills for redistribution. To reduce their own cost of currency management operations, many banks would make Fed deposits and withdrawals of the same denominations during a given week. In July of 2007, the Fed introduced cross-shipping fees (i.e. fees for making both deposits and withdrawals during a given Monday through Friday period) to encourage banks to recycle their currency. Recognizing the market opportunity, Fiserv initiated a project to optimize bank vault inventories across time and space for a major “Top 5” bank who previously suffered from over 7 billion dollars setting idle either in trucks, vaults, branches, or ATMs. Rarely in academic research does one enjoy an opportunity to actually implement and therefore test one’s work within the applied “dirty” world of business applications. The business results were most impressive.

The integer programming model as well as an empirical investigation to reduce the computational time is presented in Chapter 3. The model has been successfully applied to the vault operations of large banks. The underlying configuration is a time-space multi-commodity network with a fixed-charge cost structure.