Tuesday , August 14 2018

Vol.23-Issue3-2014-LAGOS

Combining Tabu Search and Genetic Algorithms to Solve
the Capacitated Multicommodity Network Flow Problem

Carolina LAGOS1, Broderick CRAWFORD1, Ricardo SOTO2,
Jose-Miguel RUBIO1, Enrique CABRERA1, Fernando PARADES3

1 Pontificia Universidad Católica de Valparaíso,
2340025 Valparaíso, Chile carolina.lagos@mail.pucv.cl
2 CIMFAV, Universidad de Valparaíso,
Valparaíso, Chile
3 Escuela de Ingeniería Industrial, Universidad Diego Portales,
8370179 Santiago, Chile

Abstract: Network design has been an important issue in logistics during the last century. This is due to the significant impact that an efficient distribution network design can have over both costs and service level. In this article, we present a heuristic solution approach for the well-known capacitated multicommodity network flow problem. The heuristic approach combines two well-known algorithms namely Tabu Search and Genetic Algorithms. While the main algorithm is Tabu Search, the Genetic Algorithm is used to select the best option among the neighbours of the current solution. To be able to do that some well-known evolutionary operators such as cross-over and mutation are made use of. This hybrid approach obtains important improvements when compared to the ones presented previously in the literature.

Keywords: Multicommodity network flow problem, network design, probabilistic neighbour selection criterion, tabu search, genetic algorithms.

>>Full Text
CITE THIS PAPER AS:
Carolina LAGOS, Broderick CRAWFORD, Enrique CABRERA, Ricardo SOTO, Jose-Miguel RUBIO,  Fernando PARADES, Combining Tabu Search and Genetic Algorithms to Solve the Capacitated Multicommodity Network Flow Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 23 (3), pp. 265-276, 2014.

1. Introduction

Network design has been an important issue in logistics during the last century. This is due to the impact that an efficient distribution network design can have over both cost and service level. One specific problem arising in network design is the problem of moving different commodities over a network from different sources to several destinations. This problem is called Multicommodity Network Flow (MNF) problem and is mostly encountered in telecommunications and transportation network planning. Several models have been proposed in literature to represent different real life situations where this kind of problems can be found (see [19]).

In this article, we consider a transportation problem of multiple products (commodities) through a network with capacity constraint, fixed demands and both fixed and variables costs in edges construction and flows, respectively. The capacity constraint considered in this article is an important element for the complexity of the capacitated MNF (CMNF) problem. In fact, several articles in literature confirm that this problem is NP-Hard [19, 6, 7, 20]. Thus, when this problem becomes bigger in terms of the number of decision variables, mathematical programming techniques are not able to find the optimal solution within reasonable time. Therefore other techniques such as heuristic procedures must be considered to find an acceptable approximation of the actual optimal solution within some time limits. In this article we consider a hybrid algorithm of Tabu Search (TS) and Genetic Algorithms (GA) to approximately solve this problem. We chose these two strategies based on the good performance that they have shown when applied on other complex combinatorial optimization problems such as routing, facility location, set covering, among others.

The hybrid algorithm is mainly based on TS. We use the GA in order to increase the algorithm diversification degree. Increasing the algorithm diversification degree allows the algorithm to increase its exploration level over the set of feasible solutions, raising the likelihood of finding good quality neighbourhoods. A large number of techniques have been applied to this problem previously in literature; in [7] the authors present a multilevel cooperative TS algorithm for the CMNF problem, using different levels of cooperation, as well as a set of new cooperation operators. In [17] the authors propose a Lagrangean heuristic within a branch-and-bound framework. The Lagrangean heuristic uses a Lagrangean relaxation to obtain easily handled sub-problems and solves the Lagrangean dual by sub-gradient optimization. The Lagrangean heuristic is then embedded into a branch-and-bound scheme that yields further primal improvements. In [11] authors propose a path re-linking procedure.

Cycle-based neighbourhoods are used to move along paths between elite solutions and to generate the elite candidate set, like in local search procedures. In [2] the authors present an efficient procedure using a scatter search framework, which is modified in [3] through an embedded greedy random adaptive search procedure (GRASP). More recently, [26] have presented a hybrid simulated annealing and column generation approach to solve this problem. In their paper, simulated annealing manages open and closed arcs while column generation is used to solve (exactly) the resulting sub-problem.

In [24] the authors present a three-phase strategy that combines TS with path re-linking and exact techniques. While heuristics are used to explore the solution set, the exact algorithm is used to intensify the search in a specific part of the solution set.

In this article we present a TS-based algorithm which selects at each iteration a candidate from a list through a probabilistic criterion based on evolutionary algorithms. TS algorithms have been applied on a wide range of different combinatorial optimization problems [1, 4, 5, 15, 22]. Different implementations of TS have been also used to solve the CMNF problem (see e.g. [7]). Regarding the hybridization proposed in this work, the literature reports many different hybrid approaches of TS and evolutionary algorithms [8, 9, 13, 14, 18, 21, 23, 27, 28, 29]. In the majority of these works, authors rely on the exploration capabilities of GA while using TS to refine and exploit the neighbourhood of the best solution obtained by the GA. Unlike these approaches, in this article we make use of the evolutionary algorithm only to choose the next solution among the set of neighbours candidates of the current solution in the TS algorithm.

Moreover, to the best of our knowledge, no hybrid algorithm of TS and GA to solve the CMNF problem, such as the one presented in this article, has been reported in the literature.

REFERENCES

  1. Al-SULTAN, K., M. Al-FAWZAN, A Tabu Search Approach to the Uncapacitated Facility Location Problem, Annals of Operation Research, vol. 86, 1999, pp. 91-103.
  2. ALVAREZ, A., J. GONZALEZ-VELARDE, K. DE-ALBA, GRASP Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem, Journal of Heuristics, vol. 11, 2005, pp. 233-257.
  3. ALVAREZ, A., J. GONZALEZ-VELARDE, K. DE-ALBA, Scatter Search for Network Design Problem, Annals of Operation Research, vol. 138, 2005, pp. 159-178.
  4. BRANDÃO, J., A. MERCER, A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem, European Journal of Operational Research, vol. 100, 1997, pp. 180-191.
  5. CABRERA, G., P. A. MIRANDA, E. CABRERA, R. SOTO, B. CRAWFORD, J. M. RUBIO, F. PAREDES, Solving A Novel Inventory Location Model with Stochastic Constraints and (R, s, S) Inventory Control Policy, Mathematical Problems in Engineering, vol. 2013, Article ID 670528, 12 pages, 2013.
  6. COBOS, N., A. ALVAREZ, Tabu Search-Based Algorithm for Capacitated Multicommodity Network Design Problem, 14th International Conference on Electrical, Communication & Computing – ICECC, 2004, p. 144.
  7. CRAINIC, T. G., Y. LI, M. TOULOUSE, A First Multilevel Cooperative Algorithm for Capacitated Multicommodity Network Design, Computers & Operations Research, vol. 33, 2006, pp. 2602-2622.
  8. DAVIDOVIC, T., P. HANSEN, N. MLADENOVIC, Permutation-based Genetic, Tabu, and Variable Neighborhood Search Heuristics for Multiprocessor Scheduling with Communication Delays, Asia-Pacific Journal of Operational Research, vol. 22,, 2005, pp. 297-326.
  9. GARAI, G., B. CHAUDHURII, A Novel Hybrid Genetic Algorithm with Tabu Search for Optimizing Multi-dimensional Functions and Point Pattern Recognition, Information Sciences, vol. 221, 2013, pp. 28-48.
  10. GENDRON, B., T. CRAINIC, A. FRANGIONI, Multicommodity Capacitated Network Design, Telecommunications Network Planning, 1999, pp. 1-19.
  11. GHAMLOUCHE, I., T. CRAINIC, M. GENDREAU, Path Relinking, Cycle-based Neighbourhoods and Capacitated Multicomodity Network Design, Annals of Operation Research, vol. 131, 2004,     pp. 109-133.
  12. GLOVER, F., B. MELIÁN, Tabu Search, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial vol. 19, 2003, pp. 29-48.
  13. GONZALEZ, M., C. VELA, R. VARELA, Genetic Algorithm Combined with Tabu Search for the Job Shop Scheduling Problem with Setup Times, Methods and Models in Artificial and Natural Computation, 2009, pp. 265-274.
  14. El FERCHICHI, S., K. LAABIDI, S. ZIDI, Genetic Algorithm and Tabu Search for Feature Selection, Studies in Informatics and Control, 2009, vol. 18(2), pp. 181-187.
  15. HANAFI, S., A. FREVILLE, An Efficient Tabu Search Approach for the 0 – 1 Multidimensional Knapsack Problem, European Journal of Operational Research, vol. 106, 1998, pp. 659-675.
  16. HOLLAND, J., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, 1975.
  17. HOLMBERG, K., D. YUAN, A Lagrangian Heuristic based Branch-and-Bound Approach for the Capacitated Network Design Problem, Operations Research, vol. 48, 2000, pp. 461-481.
  18. CABRERA, G., S. RONCAGLIOLO, J.P. RIQUELME, C. CUBILLOS, R. SOTO. A Hybrid Particle Swarm Optimization – Simulated Annealing Algorithm for the Probabilistic Travelling Salesman Problem, Studies in Informatics and Control, 2012, vol. 21(1), pp. 49-58.
  19. MAGNANTI, T., R. WONG, Network Design, and Transportation Planning: Models and Algorithms, Transportation Science, vol. 1, 1984, pp. 1-55.
  20. MINOUX, M., Networks Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications, Networks, vol. 19, 1988,     pp. 313-360.
  21. TING, C. K., C. F. KO, C. H. HUANG, Selecting Survivors in Genetic Algorithm using Tabu Search Strategies, Memetic Computing vol. 1, 2009, pp. 191-203.
  22. VALLS, V., M. PEREZ, M. QUINTANILLA, A Tabu Search Approach to Machine Scheduling, European Journal of Operational Research, vol. 106, 1998, pp. 277-300.
  23. VILCOT, G., J. C. BILLAUT, A Tabu Search and a Genetic Algorithm for Solving a Bicriteria General Job Shop Scheduling Problem, European Journal of Operational Research, vol. 190, 2008, pp. 398-411.
  24. VU, D., T. CRAINIC, M. TOULOUSE, A Three-phase Matheuristic for Capacitated Multi-Commodity Fixed-Cost Network Design with Design-Balance Constraints, Journal of Heuristics vol. 19, 2013, pp. 757-795.
  25. WESLEY BARNES, J., M. LAGUNA, A Tabu Search Experience in Production Scheduling, Annals of Operation Research, vol. 41, 1993, pp. 139-156.
  26. YAGHINI, M., M. RAHBAR, M. KARIMI, Hybrid Simulated Annealing and Column Generation Approach, Journal of the Operational Research Society, vol. 64, 2013, pp. 1010-1020.
  27. HAGEMAN, J., R. WEHRENS, H. van SPRANG, L. BUYDENS, Hybrid Genetic Algorithm-Tabu Search Approach for Optimising Multilayer Optical Coatings, Analytica Chimica Acta vol. 490, 2003, pp. 211-222.
  28. JAT, S. N., S. YANG, A Hybrid Genetic Algorithm and Tabu Search Approach for Post Enrolment Course Timetabling, Journal of Scheduling vol. 14, 2011,         pp. 617-637.
  29. DURAN, O., L. PEREZ, Solution of the Spare Parts Joint Replenishment Problem with Quantity Discounts using a Discrete Particle Swarm Optimization Technique, Studies in Informatics and Control, 2013, vol. 22(4), pp. 319-328.

https://doi.org/10.24846/v23i3y201405