Solving Partitioning-Hub Location-Routing Problem using DCA

Anh Son Ta; Le  Thi Hoai An; Djamel Khadraoui; Pham Dinh Tao

doi:10.3934/jimo.2012.8.87

Article Contents

2012, Volume 8, Issue 1: 87-102. Doi: 10.3934/jimo.2012.8.87

This issue Previous Article Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP Next Article A tropical cyclone-based method for global optimization

Solving Partitioning-Hub Location-Routing Problem using DCA

1.
CRP Henri Tudor, 29 avenue John F. Kennedy, 1855 Kirchberg
2.
Laboratory of Theoretical and Applied Computer Science (LITA), Paul Verlaine - Metz University, Ile du Saulcy, 57045, Metz
3.
Laboratory of Modelling, Optimization & Operations Research, National Institute for Applied Sciences - Rouen, 76801 Saint-Etienne-du-Rouvray Cedex

Received: January 31, 2011

Revised: June 30, 2011

Published: December 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Hub location,
DC programming,
DC Algorithm (DCA),
exact penalty,
Binary Integer Linear Programming (BILP).

Mathematics Subject Classification: Primary: 90C10, 90C35; Secondary: 90C27.

Citation:

Related Papers

Cited by

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-21.doi: 10.1016/j.ejor.2007.06.008.
[2]	J. F. Campbell, Strategic network design for motor carriers, in "Logistics Systems: Design and Optimization" (eds. A. Langevin and D. Riopel), Springer, U.S.A., 2005.doi: 10.1007/0-387-24977-X_8.
[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-549.doi: 10.1016/j.cor.2010.07.014.
[4]	M. Grotschel and Y. Wakabayashi, Facets of the clique partitioning polytope, Mathematical Programming, 47 (1990), 367-387.doi: 10.1007/BF01580870.
[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-120.
[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-46.doi: 10.1007/s10479-004-5022-1.
[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, ULB, Department of Computer Science, 2008.
[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-355.
[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-505.doi: 10.1137/S1052623494274313.
[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-632.doi: 10.1007/s10898-009-9507-y.