Heuristics for the Transportation Problem in Planning of ICT Access Networks

R.H. Nielsen, M.T. Riaz, J.M. Pedersen, and O.B. Madsen (Denmark)


FTTH, Facility Location, Transportation, Heuristic Algo rithm.


Networks are being upgraded or deployed from scratch all over the world. The field of network planning is thus be coming still more important. In this paper we consider one of the involved optimization problems related to the loca tioning of facilities, namely the transportation problem. We propose 3 heuristic algorithm and model the problem to ob tain a special case of it where an exact solution can be found for comparison. The contribution of this paper is two-fold: 1. 3 different heuristics for the transportation are proposed. 2. The 3 proposed heuristics along with a 4. heuristic are tested, in a large-scale case study, as to their exactness com pared to solving a simplified formulation of the problem to optimality. It is concluded that the most advanced of the heuristics which uses reordering is well-suited for estimat ing the solution for most of the problem instances tested.

Important Links:

Go Back