Abstract

In this paper a total approach is presented for interactive planning of a reliable fiber-to-the-cabinet network. Interactive means here that areas with 600 to 1000 cabinets can be planned roughly within minutes. The problem of telecom operators, when planning fiber to the cabinet, is to find the minimum number of cabinets that are equipped with active equipment such that a required number of customers are within a targeted distance from an activated cabinet. Next, these activated cabinets need to be clustered and connected with a highly reliable fiber ring, satisfying capacity constraints. A three-step approach is described: an activation problem, a cluster problem, and a routing problem, each in a heuristic approach. The paper shows that the total interactive approach is indeed possible by presenting several real life cases.

© 2014 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. F. Phillipson, “A cost effective topology migration path toward fibre,” in Proc. of the 3rd Int. Conf. on Information Communication and Management (ICICM2013), Paris, France, 2013.
  2. D. Tipper, “Resilient network design: Challenges and future directions,” Telecommun. Syst., vol.  56, no. 1, pp. 5–16, 2014.
  3. K. Vajanapoom, D. Tipper, and S. Akavipat, “Risk based resilient network design,” Telecommun. Syst., vol.  52, pp. 799–811, 2012.
  4. Y. Gong, C. Gan, C. Wu, and R. Wang, “Novel ring-based WDM-PON architecture with high-reliable remote nodes,” Telecommun. Syst., to be published.
    [CrossRef]
  5. G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol.  12, no. 4, pp. 568–581, 1964.
    [CrossRef]
  6. F. Phillipson, “Fast roll-out of fibre to the cabinet: Practical approach for activation of cabinets,” in 19th Eur. Conf. on Networks and Optical Communications (NOC 2014), Milano, Italy, 2014.
  7. F. Phillipson, “Efficient clustering of cabinets at FttCab,” in Internet of Things, Smart Spaces, and Next Generation Networking. Berlin, Germany: Springer, 2013, pp. 201–213.
  8. M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.
  9. S. Gollowitzer, L. Gouveia, and I. Ljubić, “A node splitting technique for two level network design problems with transition nodes,” Lect. Notes Comput. Sci., vol.  6701, pp. 57–70, 2011.
  10. S. Gollowitzer and I. Ljubić, “MIP models for connected facility location: A theoretical and computational study,” Comput. Oper. Res., vol.  38, pp. 435–449, 2011.
  11. M. Gendreau, M. Labbé, and G. Laporte, “Efficient heuristics for the design of ring networks,” Telecommun. Syst., vol.  4, no. 1, pp. 177–188, 1995.
  12. A. Fink, G. Schneidereit, and S. Voß, “Solving general ring network design problems by meta-heuristics,” in Computing Tools for Modeling, Optimization and Simulation. Springer, 2000, pp. 91–113.
  13. G. Mateus, F. Cruz, and H. Luna, “An algorithm for hierarchical network design,” Location Sci., vol.  2, no. 3, pp. 149–164, 1994.
  14. R. Zhao, H. Liu, and R. Lehnert, “Topology design of hierarchical hybrid fiber-VDSL access networks with ACO,” in Proc. of the 4th Advanced Int. Conf. on Telecommunications, Athens, Greece, 2008.
  15. M. Kalsch, M. Koerkel, and R. Nitsch, “Embedding ring structures in large fiber networks,” in Proc. of Telecommunications Network Strategy and Planning Symp. (NETWORKS), Rome, Italy, 2012.
  16. M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.
  17. T. Thomadsen and T. Stidsen, “Hierarchical ring network design using branch-and-price,” Telecommun. Syst., vol.  29, no. 1, pp. 61–76, 2005.
  18. R. Baldacci, M. Dell’Amico, and J. S. González, “The capacitated m-ring-star problem,” Oper. Res., vol.  55, no. 6, pp. 1147–1162, 2007.
    [CrossRef]
  19. M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
    [CrossRef]
  20. K. Darby-Dowman and H. Lewis, “Lagrangian relaxation and the single-source capacitated facility-location problem,” J. Oper. Res. Soc., vol.  39, no. 11, pp. 1035–1040, 1988.
  21. J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proc. of 5th Berkeley Symp. on Mathematical Statistics and Probability, 1967, pp. 281–297.
  22. A. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recogn. Lett., vol.  31, pp. 651–666, 2010.
    [CrossRef]
  23. D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
    [CrossRef]
  24. M. Inaba, N. Katoh, and H. Imai, “Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering,” in Proc. of 10th ACM Symp. on Computational Geometry, 1994, pp. 332–339.
  25. S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, vol.  IT-28, no. 2, pp. 129–137, 1982.
  26. P. Bradley, K. Bennet, and A. Demiriz, “Constrained K-means clustering,” Microsoft Research, , 2000.
  27. D. Arthur and S. Vassilvitskii, “K-means++: The advantages of careful seeding,” in Proc. of the 18th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2007, pp. 1027–1035.
  28. G. Croes, “A method for solving traveling salesman problems,” Oper. Res., vol.  6, pp. 791–812, 1958.
    [CrossRef]
  29. J. Xu, S. Chiu, and F. Glover, “Optimizing a ring-based private line telecommunication network using tabu search,” Manage. Sci., vol.  45, no. 3, pp. 330–345, 1999.
  30. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT, 2009.
  31. E. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol.  1, no. 1, pp. 269–271, 1959.
    [CrossRef]
  32. R. Daamen, “Heuristic methods for the design of edge disjoint circuits,” M.Sc. thesis, Tilburg University and TNO, 2013.

2014

D. Tipper, “Resilient network design: Challenges and future directions,” Telecommun. Syst., vol.  56, no. 1, pp. 5–16, 2014.

2012

K. Vajanapoom, D. Tipper, and S. Akavipat, “Risk based resilient network design,” Telecommun. Syst., vol.  52, pp. 799–811, 2012.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.

2011

S. Gollowitzer, L. Gouveia, and I. Ljubić, “A node splitting technique for two level network design problems with transition nodes,” Lect. Notes Comput. Sci., vol.  6701, pp. 57–70, 2011.

S. Gollowitzer and I. Ljubić, “MIP models for connected facility location: A theoretical and computational study,” Comput. Oper. Res., vol.  38, pp. 435–449, 2011.

2010

A. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recogn. Lett., vol.  31, pp. 651–666, 2010.
[CrossRef]

2009

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
[CrossRef]

2007

R. Baldacci, M. Dell’Amico, and J. S. González, “The capacitated m-ring-star problem,” Oper. Res., vol.  55, no. 6, pp. 1147–1162, 2007.
[CrossRef]

2005

T. Thomadsen and T. Stidsen, “Hierarchical ring network design using branch-and-price,” Telecommun. Syst., vol.  29, no. 1, pp. 61–76, 2005.

2004

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

2002

M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.

1999

J. Xu, S. Chiu, and F. Glover, “Optimizing a ring-based private line telecommunication network using tabu search,” Manage. Sci., vol.  45, no. 3, pp. 330–345, 1999.

1995

M. Gendreau, M. Labbé, and G. Laporte, “Efficient heuristics for the design of ring networks,” Telecommun. Syst., vol.  4, no. 1, pp. 177–188, 1995.

1994

G. Mateus, F. Cruz, and H. Luna, “An algorithm for hierarchical network design,” Location Sci., vol.  2, no. 3, pp. 149–164, 1994.

1988

K. Darby-Dowman and H. Lewis, “Lagrangian relaxation and the single-source capacitated facility-location problem,” J. Oper. Res. Soc., vol.  39, no. 11, pp. 1035–1040, 1988.

1982

S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, vol.  IT-28, no. 2, pp. 129–137, 1982.

1964

G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol.  12, no. 4, pp. 568–581, 1964.
[CrossRef]

1959

E. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol.  1, no. 1, pp. 269–271, 1959.
[CrossRef]

1958

G. Croes, “A method for solving traveling salesman problems,” Oper. Res., vol.  6, pp. 791–812, 1958.
[CrossRef]

Akavipat, S.

K. Vajanapoom, D. Tipper, and S. Akavipat, “Risk based resilient network design,” Telecommun. Syst., vol.  52, pp. 799–811, 2012.

Aloise, D.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
[CrossRef]

Arthur, D.

D. Arthur and S. Vassilvitskii, “K-means++: The advantages of careful seeding,” in Proc. of the 18th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2007, pp. 1027–1035.

Baldacci, R.

R. Baldacci, M. Dell’Amico, and J. S. González, “The capacitated m-ring-star problem,” Oper. Res., vol.  55, no. 6, pp. 1147–1162, 2007.
[CrossRef]

Bennet, K.

P. Bradley, K. Bennet, and A. Demiriz, “Constrained K-means clustering,” Microsoft Research, , 2000.

Bradley, P.

P. Bradley, K. Bennet, and A. Demiriz, “Constrained K-means clustering,” Microsoft Research, , 2000.

Chardy, M.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.

Chiu, S.

J. Xu, S. Chiu, and F. Glover, “Optimizing a ring-based private line telecommunication network using tabu search,” Manage. Sci., vol.  45, no. 3, pp. 330–345, 1999.

Clarke, G.

G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol.  12, no. 4, pp. 568–581, 1964.
[CrossRef]

Cormen, T.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT, 2009.

Costa, M.-C.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.

Croes, G.

G. Croes, “A method for solving traveling salesman problems,” Oper. Res., vol.  6, pp. 791–812, 1958.
[CrossRef]

Cruz, F.

G. Mateus, F. Cruz, and H. Luna, “An algorithm for hierarchical network design,” Location Sci., vol.  2, no. 3, pp. 149–164, 1994.

Daamen, R.

R. Daamen, “Heuristic methods for the design of edge disjoint circuits,” M.Sc. thesis, Tilburg University and TNO, 2013.

Darby-Dowman, K.

K. Darby-Dowman and H. Lewis, “Lagrangian relaxation and the single-source capacitated facility-location problem,” J. Oper. Res. Soc., vol.  39, no. 11, pp. 1035–1040, 1988.

Dell’Amico, M.

R. Baldacci, M. Dell’Amico, and J. S. González, “The capacitated m-ring-star problem,” Oper. Res., vol.  55, no. 6, pp. 1147–1162, 2007.
[CrossRef]

Demiriz, A.

P. Bradley, K. Bennet, and A. Demiriz, “Constrained K-means clustering,” Microsoft Research, , 2000.

Deshpande, A.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
[CrossRef]

Dijkstra, E.

E. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol.  1, no. 1, pp. 269–271, 1959.
[CrossRef]

Faye, A.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.

Fink, A.

A. Fink, G. Schneidereit, and S. Voß, “Solving general ring network design problems by meta-heuristics,” in Computing Tools for Modeling, Optimization and Simulation. Springer, 2000, pp. 91–113.

Gan, C.

Y. Gong, C. Gan, C. Wu, and R. Wang, “Novel ring-based WDM-PON architecture with high-reliable remote nodes,” Telecommun. Syst., to be published.
[CrossRef]

Gendreau, M.

M. Gendreau, M. Labbé, and G. Laporte, “Efficient heuristics for the design of ring networks,” Telecommun. Syst., vol.  4, no. 1, pp. 177–188, 1995.

Glover, F.

J. Xu, S. Chiu, and F. Glover, “Optimizing a ring-based private line telecommunication network using tabu search,” Manage. Sci., vol.  45, no. 3, pp. 330–345, 1999.

Gollowitzer, S.

S. Gollowitzer, L. Gouveia, and I. Ljubić, “A node splitting technique for two level network design problems with transition nodes,” Lect. Notes Comput. Sci., vol.  6701, pp. 57–70, 2011.

S. Gollowitzer and I. Ljubić, “MIP models for connected facility location: A theoretical and computational study,” Comput. Oper. Res., vol.  38, pp. 435–449, 2011.

Gong, Y.

Y. Gong, C. Gan, C. Wu, and R. Wang, “Novel ring-based WDM-PON architecture with high-reliable remote nodes,” Telecommun. Syst., to be published.
[CrossRef]

González, J.

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

González, J. S.

R. Baldacci, M. Dell’Amico, and J. S. González, “The capacitated m-ring-star problem,” Oper. Res., vol.  55, no. 6, pp. 1147–1162, 2007.
[CrossRef]

Gouveia, L.

S. Gollowitzer, L. Gouveia, and I. Ljubić, “A node splitting technique for two level network design problems with transition nodes,” Lect. Notes Comput. Sci., vol.  6701, pp. 57–70, 2011.

Hansen, P.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
[CrossRef]

Henningsson, M.

M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.

Holmberg, K.

M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.

Imai, H.

M. Inaba, N. Katoh, and H. Imai, “Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering,” in Proc. of 10th ACM Symp. on Computational Geometry, 1994, pp. 332–339.

Inaba, M.

M. Inaba, N. Katoh, and H. Imai, “Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering,” in Proc. of 10th ACM Symp. on Computational Geometry, 1994, pp. 332–339.

Jain, A.

A. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recogn. Lett., vol.  31, pp. 651–666, 2010.
[CrossRef]

José, J.

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

Kalsch, M.

M. Kalsch, M. Koerkel, and R. Nitsch, “Embedding ring structures in large fiber networks,” in Proc. of Telecommunications Network Strategy and Planning Symp. (NETWORKS), Rome, Italy, 2012.

Katoh, N.

M. Inaba, N. Katoh, and H. Imai, “Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering,” in Proc. of 10th ACM Symp. on Computational Geometry, 1994, pp. 332–339.

Koerkel, M.

M. Kalsch, M. Koerkel, and R. Nitsch, “Embedding ring structures in large fiber networks,” in Proc. of Telecommunications Network Strategy and Planning Symp. (NETWORKS), Rome, Italy, 2012.

Labbé, M.

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

M. Gendreau, M. Labbé, and G. Laporte, “Efficient heuristics for the design of ring networks,” Telecommun. Syst., vol.  4, no. 1, pp. 177–188, 1995.

Laporte, G.

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

M. Gendreau, M. Labbé, and G. Laporte, “Efficient heuristics for the design of ring networks,” Telecommun. Syst., vol.  4, no. 1, pp. 177–188, 1995.

Lehnert, R.

R. Zhao, H. Liu, and R. Lehnert, “Topology design of hierarchical hybrid fiber-VDSL access networks with ACO,” in Proc. of the 4th Advanced Int. Conf. on Telecommunications, Athens, Greece, 2008.

Leiserson, C.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT, 2009.

Lewis, H.

K. Darby-Dowman and H. Lewis, “Lagrangian relaxation and the single-source capacitated facility-location problem,” J. Oper. Res. Soc., vol.  39, no. 11, pp. 1035–1040, 1988.

Liu, H.

R. Zhao, H. Liu, and R. Lehnert, “Topology design of hierarchical hybrid fiber-VDSL access networks with ACO,” in Proc. of the 4th Advanced Int. Conf. on Telecommunications, Athens, Greece, 2008.

Ljubic, I.

S. Gollowitzer, L. Gouveia, and I. Ljubić, “A node splitting technique for two level network design problems with transition nodes,” Lect. Notes Comput. Sci., vol.  6701, pp. 57–70, 2011.

S. Gollowitzer and I. Ljubić, “MIP models for connected facility location: A theoretical and computational study,” Comput. Oper. Res., vol.  38, pp. 435–449, 2011.

Lloyd, S.

S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, vol.  IT-28, no. 2, pp. 129–137, 1982.

Luna, H.

G. Mateus, F. Cruz, and H. Luna, “An algorithm for hierarchical network design,” Location Sci., vol.  2, no. 3, pp. 149–164, 1994.

MacQueen, J.

J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proc. of 5th Berkeley Symp. on Mathematical Statistics and Probability, 1967, pp. 281–297.

Martín, I. R.

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

Mateus, G.

G. Mateus, F. Cruz, and H. Luna, “An algorithm for hierarchical network design,” Location Sci., vol.  2, no. 3, pp. 149–164, 1994.

Nitsch, R.

M. Kalsch, M. Koerkel, and R. Nitsch, “Embedding ring structures in large fiber networks,” in Proc. of Telecommunications Network Strategy and Planning Symp. (NETWORKS), Rome, Italy, 2012.

Phillipson, F.

F. Phillipson, “A cost effective topology migration path toward fibre,” in Proc. of the 3rd Int. Conf. on Information Communication and Management (ICICM2013), Paris, France, 2013.

F. Phillipson, “Fast roll-out of fibre to the cabinet: Practical approach for activation of cabinets,” in 19th Eur. Conf. on Networks and Optical Communications (NOC 2014), Milano, Italy, 2014.

F. Phillipson, “Efficient clustering of cabinets at FttCab,” in Internet of Things, Smart Spaces, and Next Generation Networking. Berlin, Germany: Springer, 2013, pp. 201–213.

Popat, P.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
[CrossRef]

Rivest, R.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT, 2009.

Rönnqvist, M.

M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.

Schneidereit, G.

A. Fink, G. Schneidereit, and S. Voß, “Solving general ring network design problems by meta-heuristics,” in Computing Tools for Modeling, Optimization and Simulation. Springer, 2000, pp. 91–113.

Stein, C.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT, 2009.

Stidsen, T.

T. Thomadsen and T. Stidsen, “Hierarchical ring network design using branch-and-price,” Telecommun. Syst., vol.  29, no. 1, pp. 61–76, 2005.

Thomadsen, T.

T. Thomadsen and T. Stidsen, “Hierarchical ring network design using branch-and-price,” Telecommun. Syst., vol.  29, no. 1, pp. 61–76, 2005.

Tipper, D.

D. Tipper, “Resilient network design: Challenges and future directions,” Telecommun. Syst., vol.  56, no. 1, pp. 5–16, 2014.

K. Vajanapoom, D. Tipper, and S. Akavipat, “Risk based resilient network design,” Telecommun. Syst., vol.  52, pp. 799–811, 2012.

Trampont, M.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.

Vajanapoom, K.

K. Vajanapoom, D. Tipper, and S. Akavipat, “Risk based resilient network design,” Telecommun. Syst., vol.  52, pp. 799–811, 2012.

Värbrand, P.

M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.

Vassilvitskii, S.

D. Arthur and S. Vassilvitskii, “K-means++: The advantages of careful seeding,” in Proc. of the 18th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2007, pp. 1027–1035.

Voß, S.

A. Fink, G. Schneidereit, and S. Voß, “Solving general ring network design problems by meta-heuristics,” in Computing Tools for Modeling, Optimization and Simulation. Springer, 2000, pp. 91–113.

Wang, R.

Y. Gong, C. Gan, C. Wu, and R. Wang, “Novel ring-based WDM-PON architecture with high-reliable remote nodes,” Telecommun. Syst., to be published.
[CrossRef]

Wright, J.

G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol.  12, no. 4, pp. 568–581, 1964.
[CrossRef]

Wu, C.

Y. Gong, C. Gan, C. Wu, and R. Wang, “Novel ring-based WDM-PON architecture with high-reliable remote nodes,” Telecommun. Syst., to be published.
[CrossRef]

Xu, J.

J. Xu, S. Chiu, and F. Glover, “Optimizing a ring-based private line telecommunication network using tabu search,” Manage. Sci., vol.  45, no. 3, pp. 330–345, 1999.

Zhao, R.

R. Zhao, H. Liu, and R. Lehnert, “Topology design of hierarchical hybrid fiber-VDSL access networks with ACO,” in Proc. of the 4th Advanced Int. Conf. on Telecommunications, Athens, Greece, 2008.

Comput. Oper. Res.

S. Gollowitzer and I. Ljubić, “MIP models for connected facility location: A theoretical and computational study,” Comput. Oper. Res., vol.  38, pp. 435–449, 2011.

Eur. J. Oper. Res.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FttH network,” Eur. J. Oper. Res., vol.  222, no. 3, pp. 430–440, 2012.

IEEE Trans. Inf. Theory

S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, vol.  IT-28, no. 2, pp. 129–137, 1982.

J. Oper. Res. Soc.

K. Darby-Dowman and H. Lewis, “Lagrangian relaxation and the single-source capacitated facility-location problem,” J. Oper. Res. Soc., vol.  39, no. 11, pp. 1035–1040, 1988.

Lect. Notes Comput. Sci.

S. Gollowitzer, L. Gouveia, and I. Ljubić, “A node splitting technique for two level network design problems with transition nodes,” Lect. Notes Comput. Sci., vol.  6701, pp. 57–70, 2011.

Location Sci.

G. Mateus, F. Cruz, and H. Luna, “An algorithm for hierarchical network design,” Location Sci., vol.  2, no. 3, pp. 149–164, 1994.

Mach. Learn.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Mach. Learn., vol.  75, pp. 245–248, 2009.
[CrossRef]

Manage. Sci.

J. Xu, S. Chiu, and F. Glover, “Optimizing a ring-based private line telecommunication network using tabu search,” Manage. Sci., vol.  45, no. 3, pp. 330–345, 1999.

Networks

M. Labbé, G. Laporte, I. R. Martín, J. José, and J. González, “The ring star problem: Polyhedral analysis and exact algorithm,” Networks, vol.  43, pp. 177–189, 2004.
[CrossRef]

Numer. Math.

E. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol.  1, no. 1, pp. 269–271, 1959.
[CrossRef]

Oper. Res.

G. Croes, “A method for solving traveling salesman problems,” Oper. Res., vol.  6, pp. 791–812, 1958.
[CrossRef]

R. Baldacci, M. Dell’Amico, and J. S. González, “The capacitated m-ring-star problem,” Oper. Res., vol.  55, no. 6, pp. 1147–1162, 2007.
[CrossRef]

G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol.  12, no. 4, pp. 568–581, 1964.
[CrossRef]

Pattern Recogn. Lett.

A. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recogn. Lett., vol.  31, pp. 651–666, 2010.
[CrossRef]

Telecommun. Syst.

D. Tipper, “Resilient network design: Challenges and future directions,” Telecommun. Syst., vol.  56, no. 1, pp. 5–16, 2014.

K. Vajanapoom, D. Tipper, and S. Akavipat, “Risk based resilient network design,” Telecommun. Syst., vol.  52, pp. 799–811, 2012.

M. Gendreau, M. Labbé, and G. Laporte, “Efficient heuristics for the design of ring networks,” Telecommun. Syst., vol.  4, no. 1, pp. 177–188, 1995.

M. Henningsson, K. Holmberg, M. Rönnqvist, and P. Värbrand, “Ring network design by Lagrangian based column generation,” Telecommun. Syst., vol.  21, no. 2–4, pp. 301–318, 2002.

T. Thomadsen and T. Stidsen, “Hierarchical ring network design using branch-and-price,” Telecommun. Syst., vol.  29, no. 1, pp. 61–76, 2005.

Other

R. Zhao, H. Liu, and R. Lehnert, “Topology design of hierarchical hybrid fiber-VDSL access networks with ACO,” in Proc. of the 4th Advanced Int. Conf. on Telecommunications, Athens, Greece, 2008.

M. Kalsch, M. Koerkel, and R. Nitsch, “Embedding ring structures in large fiber networks,” in Proc. of Telecommunications Network Strategy and Planning Symp. (NETWORKS), Rome, Italy, 2012.

F. Phillipson, “A cost effective topology migration path toward fibre,” in Proc. of the 3rd Int. Conf. on Information Communication and Management (ICICM2013), Paris, France, 2013.

J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proc. of 5th Berkeley Symp. on Mathematical Statistics and Probability, 1967, pp. 281–297.

A. Fink, G. Schneidereit, and S. Voß, “Solving general ring network design problems by meta-heuristics,” in Computing Tools for Modeling, Optimization and Simulation. Springer, 2000, pp. 91–113.

Y. Gong, C. Gan, C. Wu, and R. Wang, “Novel ring-based WDM-PON architecture with high-reliable remote nodes,” Telecommun. Syst., to be published.
[CrossRef]

F. Phillipson, “Fast roll-out of fibre to the cabinet: Practical approach for activation of cabinets,” in 19th Eur. Conf. on Networks and Optical Communications (NOC 2014), Milano, Italy, 2014.

F. Phillipson, “Efficient clustering of cabinets at FttCab,” in Internet of Things, Smart Spaces, and Next Generation Networking. Berlin, Germany: Springer, 2013, pp. 201–213.

M. Inaba, N. Katoh, and H. Imai, “Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering,” in Proc. of 10th ACM Symp. on Computational Geometry, 1994, pp. 332–339.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT, 2009.

P. Bradley, K. Bennet, and A. Demiriz, “Constrained K-means clustering,” Microsoft Research, , 2000.

D. Arthur and S. Vassilvitskii, “K-means++: The advantages of careful seeding,” in Proc. of the 18th Annu. ACM-SIAM Symp. on Discrete Algorithms, 2007, pp. 1027–1035.

R. Daamen, “Heuristic methods for the design of edge disjoint circuits,” M.Sc. thesis, Tilburg University and TNO, 2013.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (11)

Fig. 1.
Fig. 1.

Four topologies.

Fig. 2.
Fig. 2.

Starting point.

Fig. 3.
Fig. 3.

Which cabinets must be activated?

Fig. 4.
Fig. 4.

Which cabinets are together on one ring?

Fig. 5.
Fig. 5.

Physical route of the fiber ring.

Fig. 6.
Fig. 6.

Overview of the heuristic.

Fig. 7.
Fig. 7.

Possible situation before swap.

Fig. 8.
Fig. 8.

Possible situation after swap.

Fig. 9.
Fig. 9.

Solution for Delft: assigned cascades.

Fig. 10.
Fig. 10.

Flow diagram of the proposed heuristic.

Fig. 11.
Fig. 11.

Solution for Amstelveen: assigned clusters.

Tables (13)

Tables Icon

Algorithm 1 Activation

Tables Icon

TABLE I Selected Cases for Testing

Tables Icon

TABLE II Results for tj=2

Tables Icon

TABLE III Results for tj=4

Tables Icon

TABLE IV Results in Percentage of Maximum Costs

Tables Icon

Algorithm 2 Lloyd’s Based on [25]

Tables Icon

Algorithm 3 Bradley’s Based on [26]

Tables Icon

Algorithm 4 Clustering

Tables Icon

TABLE V Results of the Clustering for the Cases

Tables Icon

Algorithm 5 Dijkstra (G,w,s) Based on [30]

Tables Icon

TABLE VI Selected Cases, Calculation Time for Routing

Tables Icon

TABLE VII Selected Cases, Total Calculation Time

Equations (23)

Equations on this page are rendered with MathJax. Learn more.

xij={1if cabinetiis connected to cabinetj,0otherwise.yj={1if cabinetjis activated,0otherwise.
mini=1nj=1ncijxij+j=1ncjjyj,
j=1nxij=1(i=1,,n),
i=1nj=1nbijxijD,
i=1nxijtj(j=1,,n),
i=1nbiixijwjyj(j=1,,n),
xij,yj{0,1}(i,j=1,,n).
xij={1ifi=j,0else.yj=1j=1,,n.
Ti,h={1if data pointxiis assigned to centerCh,0otherwise.
Ch=i=1mTi,hxii=1mTi,h.
minTi=1mh=1kTi,h(xiCh22).
x2=(x12+x22++xn2)12.
i=1mTi,huiτh=1,,k.
h=1kTi,h=1i=1,,mTi,h{0,1}i=1,,mh=1,,k.
minTi=1mh=1kTi,h(xiCh,t22)
i=1mTi,hτhh=1,,k(*),h=1kTi,h=1i=1,,n;
xij={1if nodeiis linked to nodej0otherwise.zj={1if nodejis used,0otherwise.
mini=1N+Mj=1N+Mcijxij.
zi=1i=1,,n,
xij(zi+zj)/2i,j=1,,N+Mi<j,
j=1n+mxij+j=1n+mxji=2zii=1,,n+m,
iHjHxijiHlzi+1zt,
lHHN|H|3tNH,xij{0,1}i,j=1,,N+M,zj{0,1}jN.