Algorithms for multiplex bundling in a telecommunications network

The function of a digital telecommunications network is to transport demand of digital signals between pairs of locations. To achieve this economically, multiplex equipment packs lower rate digital signals into higher rate signals for routing over transmission facility links. Given a multiperiod demand forecast and demand routing plan, the multiplex bundling problem minimizes equipment and transmission costs by demultiplexing the higher rate signals into their lower rate components at various nodes along paths to allow lower rate signals from different sources and sinks to be combined. However, exact solution of the multiplex bundling problem is intractable, and therefore this paper presents a heuristic two-phased approach. Phase 1 formulates a single-period, capacitated routing model. The Phase 1 solution method is to first solve a problem with relaxed capacity constraints and then solve a 0-1 multiconstraint knapsack problem to obtain feasibility. Computational results show that the Phase 1 heuristic produces near-optimal results. Phase 2 exactly solves a multiperiod problem for each demand re-routing chosen in Phase 1 by using a single-stage dynamic programming algorithm. The Phase 2 algorithm reduces the state space by taking advantage of state conditions at optimality.