Vol.23-Issue3-2014-LAGOS

Carolina LAGOS¹, Broderick CRAWFORD¹, Ricardo SOTO²,
Jose-Miguel RUBIO¹, Enrique CABRERA¹, Fernando PARADES^3
1 Pontificia Universidad Católica de Valparaíso,
2340025 Valparaíso, Chile carolina.lagos@mail.pucv.cl
² CIMFAV, Universidad de Valparaíso,
Valparaíso, Chile
³ 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. https://doi.org/10.24846/v23i3y201405

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.