2-Approximation and Hybrid Genetic Algorithm for Long Chain Design Problem in Process Flexibility - Intelligent Computing for Sustainable Energy and Environment - page 232

(TSP), the triangle inequality, which is the key assumption for most of the
effective TSP approximation algorithms, doesn't hold. We analyze the dicul-
ties in implementing the well-known Christofides's algorithm [17],which is 3 / 2-
approximation algorithm for TSP, in long chain design problem, and under the
quadrangle inequality assumption we presents 2-approximation algorithm, i.e.,
the upper bound of its solution is no more than 2 time of the optimal solution. In
the first step of the 2-approximation algorithm, a lower bound can be obtain by
solving a linear programming. At last, based on the presented 2-approximation
algorithm and 2-opt local search, a hybrid genetic algorithm (HGA) is presented
to improved the solution quality. Numerical experiments and comparisons with
the commercial solver CPLEX 11.1 validate the effectiveness of the presented
2-approximation algorithm and the HGA.
The paper proceeds as follows. Section 2 gives the mixed 0-1 linear program-
ming model and analyzes the complexity of the long chain design problem. Sec-
tion 3 analyzes the dicult in implementing the Christofides's algorithm and
presents the 2-approximation algorithm. HGA is developed in section 4 and nu-
merical experiments are carried out in section 5. Section 6 concludes this paper
and give future research directions.

2 Long Chain Model

2.1 Formulation

A undirected bipartite graph G =( I

J,E ) represents the flexibility structures,
where set I and J denote plant and product set, E denotes the link set. A link
( i,j )

∪

E means that plant i is assigned to produce j . We further define the
link cost d ( i,j ) for link ( i,j ) . The objective is determine the optimal long chain
design with the minimal total link cost. See Fig. 1. The notation is summarized
as follows:

∈

Fig. 1. Two example of long chains in bipartite graph with n =4