January  2012, 8(1): 87-102. doi: 10.3934/jimo.2012.8.87

Solving Partitioning-Hub Location-Routing Problem using DCA

1. 

CRP Henri Tudor, 29 avenue John F. Kennedy, 1855 Kirchberg, Luxembourg, Luxembourg

2. 

Laboratory of Theoretical and Applied Computer Science (LITA), Paul Verlaine - Metz University, Ile du Saulcy, 57045, Metz, France

3. 

Laboratory of Modelling, Optimization & Operations Research, National Institute for Applied Sciences - Rouen, 76801 Saint-Etienne-du-Rouvray Cedex, France

Received  February 2011 Revised  July 2011 Published  November 2011

The Partitioning-Hub Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as in the deployment of network routing protocol problems and in the planning of freight distribution problems. We first present the formulation of this problem as an Binary Integer Linear Programming (BILP) and then investigate a new method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results are compared with CPLEX, the best solver for BILP. These results show that the proposed algorithm is efficient.
Citation: Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial & Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87
References:
[1]

S. Alumur and B. Y. Kara, Network hub location problems: The state of the art,, European Journal of Operational Research, 190 (2008), 1.  doi: 10.1016/j.ejor.2007.06.008.  Google Scholar

[2]

J. F. Campbell, Strategic network design for motor carriers,, in, (2005).  doi: 10.1007/0-387-24977-X_8.  Google Scholar

[3]

D. Catanzaro, E. Gourdin, M. Labbé and F. A. Özsoy, A branch-and-cut algorithm for the partitioning-hub location-routing problem,, Computers & Operations Research, 38 (2011), 539.  doi: 10.1016/j.cor.2010.07.014.  Google Scholar

[4]

M. Grotschel and Y. Wakabayashi, Facets of the clique partitioning polytope,, Mathematical Programming, 47 (1990), 367.  doi: 10.1007/BF01580870.  Google Scholar

[5]

Le Thi Hoai An and Pham Dinh Tao, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem,, Optimization, 50 (2001), 93.   Google Scholar

[6]

Le Thi Hoai An and Pham Dinh Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world non convex optimization problems,, Annals of Operations Research, 133 (2005), 23.  doi: 10.1007/s10479-004-5022-1.  Google Scholar

[7]

F. A. Ozsoy, M. Labbe and E. Gourdin, Analytical and empirical comparison of integer programming formulations for a partitioning-hub location-routing problem,, Technical Report 586, (2008).   Google Scholar

[8]

Pham Dinh Tao and Le Thi Hoai An, Convex analysis approach to DC programming: Theory, Algorithms and Applications,, Acta Mathematica Vietnamica, 22 (1997), 289.   Google Scholar

[9]

Pham Dinh Tao and Le Thi Hoai An, A DC optimization algorithm for solving the trust-region subproblem,, SIAM J.Optimization, 8 (1998), 476.  doi: 10.1137/S1052623494274313.  Google Scholar

[10]

Pham Dinh Tao, N. Nguyen Canh and Le Thi Hoai An, An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs,, J. Global Optimization, 48 (2010), 595.  doi: 10.1007/s10898-009-9507-y.  Google Scholar

show all references

References:
[1]

S. Alumur and B. Y. Kara, Network hub location problems: The state of the art,, European Journal of Operational Research, 190 (2008), 1.  doi: 10.1016/j.ejor.2007.06.008.  Google Scholar

[2]

J. F. Campbell, Strategic network design for motor carriers,, in, (2005).  doi: 10.1007/0-387-24977-X_8.  Google Scholar

[3]

D. Catanzaro, E. Gourdin, M. Labbé and F. A. Özsoy, A branch-and-cut algorithm for the partitioning-hub location-routing problem,, Computers & Operations Research, 38 (2011), 539.  doi: 10.1016/j.cor.2010.07.014.  Google Scholar

[4]

M. Grotschel and Y. Wakabayashi, Facets of the clique partitioning polytope,, Mathematical Programming, 47 (1990), 367.  doi: 10.1007/BF01580870.  Google Scholar

[5]

Le Thi Hoai An and Pham Dinh Tao, A Continuous approach for globally solving linearly constrained quadratic zero-one programming problem,, Optimization, 50 (2001), 93.   Google Scholar

[6]

Le Thi Hoai An and Pham Dinh Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world non convex optimization problems,, Annals of Operations Research, 133 (2005), 23.  doi: 10.1007/s10479-004-5022-1.  Google Scholar

[7]

F. A. Ozsoy, M. Labbe and E. Gourdin, Analytical and empirical comparison of integer programming formulations for a partitioning-hub location-routing problem,, Technical Report 586, (2008).   Google Scholar

[8]

Pham Dinh Tao and Le Thi Hoai An, Convex analysis approach to DC programming: Theory, Algorithms and Applications,, Acta Mathematica Vietnamica, 22 (1997), 289.   Google Scholar

[9]

Pham Dinh Tao and Le Thi Hoai An, A DC optimization algorithm for solving the trust-region subproblem,, SIAM J.Optimization, 8 (1998), 476.  doi: 10.1137/S1052623494274313.  Google Scholar

[10]

Pham Dinh Tao, N. Nguyen Canh and Le Thi Hoai An, An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs,, J. Global Optimization, 48 (2010), 595.  doi: 10.1007/s10898-009-9507-y.  Google Scholar

[1]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[2]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[3]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[4]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[5]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[6]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302

[7]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[8]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[9]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[10]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (51)
  • HTML views (0)
  • Cited by (5)

[Back to Top]