Advanced search
1 file | 3.97 MB

Mixed integer optimization for the combined capacitated facility location-routing problem

Dimitrios Papadimitriou (UGent) , Didier Colle (UGent) and Piet Demeester (UGent)
(2018) ANNALS OF TELECOMMUNICATIONS. 73(1-2). p.37-62
Author
Organization
Abstract
This paper combines the multi-product variant of the capacitated facility location problem with multicommodity flow routing. This problem shares many similarities with the digital content placement and retrieval problem when minimizing the cost of installing a set of servers for storing multiple sets of data objects (files) and connecting clients to them in order to satisfy their demands while accounting for the induced arc load. However, the regular formulation of the facility location problem models the cost of allocating the demand originated by individual clients independently of the others. The combination of this problem with flow routing removes the demand allocation independence property, leading to strongly interrelated facility location and routing decisions. Moreover, involving multiple types of data objects yields facility capacity constraints with a more complex structure than the simple superposition of per-product constraints. This paper proposes a mixed integer programming formulation for this combined problem and evaluate the computational performance for solving it. Experimental results obtained with this combined formulation are provided and compared with those obtained when solving these two problems sequentially. With the latter, the routing cost increases (up to doubling) or the facility installation cost increases (up to requiring more than twice the number of facilities) compared to the cost values obtained by solving the combined problem. This paper also extends the combined model with demand rerouting to evaluate its cost gain compared to demand protection as provided by the reliable facility location model. The results obtained with the combined formulation indicate that when subject to representative failure probabilities, demand rerouting can significantly outperform demand protection up to a factor four.
Keywords
IBCN, Mixed integer programming, Capacitated facility location, Flow routing

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 3.97 MB

Citation

Please use this url to cite or link to this publication:

Chicago
Papadimitriou, Dimitrios, Didier Colle, and Piet Demeester. 2018. “Mixed Integer Optimization for the Combined Capacitated Facility Location-routing Problem.” Annals of Telecommunications 73 (1-2): 37–62.
APA
Papadimitriou, Dimitrios, Colle, D., & Demeester, P. (2018). Mixed integer optimization for the combined capacitated facility location-routing problem. ANNALS OF TELECOMMUNICATIONS, 73(1-2), 37–62. Presented at the 12th International Conference on the Design of Reliable Communication Networks (DRCN).
Vancouver
1.
Papadimitriou D, Colle D, Demeester P. Mixed integer optimization for the combined capacitated facility location-routing problem. ANNALS OF TELECOMMUNICATIONS. Mar 14-17, 2016; 2018;73(1-2):37–62.
MLA
Papadimitriou, Dimitrios, Didier Colle, and Piet Demeester. “Mixed Integer Optimization for the Combined Capacitated Facility Location-routing Problem.” ANNALS OF TELECOMMUNICATIONS 73.1-2 (2018): 37–62. Print.
@article{8551530,
  abstract     = {This paper combines the multi-product variant of the capacitated facility location problem with multicommodity flow routing. This problem shares many similarities with the digital content placement and retrieval problem when minimizing the cost of installing a set of servers for storing multiple sets of data objects (files) and connecting clients to them in order to satisfy their demands while accounting for the induced arc load. However, the regular formulation of the facility location problem models the cost of allocating the demand originated by individual clients independently of the others. The combination of this problem with flow routing removes the demand allocation independence property, leading to strongly interrelated facility location and routing decisions. Moreover, involving multiple types of data objects yields facility capacity constraints with a more complex structure than the simple superposition of per-product constraints. This paper proposes a mixed integer programming formulation for this combined problem and evaluate the computational performance for solving it. Experimental results obtained with this combined formulation are provided and compared with those obtained when solving these two problems sequentially. With the latter, the routing cost increases (up to doubling) or the facility installation cost increases (up to requiring more than twice the number of facilities) compared to the cost values obtained by solving the combined problem. This paper also extends the combined model with demand rerouting to evaluate its cost gain compared to demand protection as provided by the reliable facility location model. The results obtained with the combined formulation indicate that when subject to representative failure probabilities, demand rerouting can significantly outperform demand protection up to a factor four.},
  author       = {Papadimitriou, Dimitrios and Colle, Didier and Demeester, Piet},
  issn         = {0003-4347},
  journal      = {ANNALS OF TELECOMMUNICATIONS},
  keywords     = {IBCN,Mixed integer programming,Capacitated facility location,Flow routing},
  language     = {eng},
  location     = {CNAM, Paris, FRANCE},
  number       = {1-2},
  pages        = {37--62},
  title        = {Mixed integer optimization for the combined capacitated facility location-routing problem},
  url          = {http://dx.doi.org/10.1007/s12243-017-0620-5},
  volume       = {73},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: