TY - JOUR
T1 - Data envelopment analysis for evaluating the efficiency of genetic algorithms on solving the vehicle routing problem with soft time windows
AU - Lu, Chung-Cheng
AU - Yu, Vincent F.
PY - 2012/9/1
Y1 - 2012/9/1
N2 - This study proposes an alternative to the conventional empirical analysis approach for evaluating the relative efficiency of distinct combinations of algorithmic operators and/or parameter values of genetic algorithms (GAs) on solving the pickup and delivery vehicle routing problem with soft time windows (PDVRPSTW). Our approach considers each combination as a decision-making unit (DMU) and adopts data envelopment analysis (DEA) to determine the relative and cross efficiencies of each combination of GA operators and parameter values on solving the PDVRPSTW. To demonstrate the applicability and advantage of this approach, we implemented a number of combinations of GA's three main algorithmic operators, namely selection, crossover and mutation, and employed DEA to evaluate and rank the relative efficiencies of these combinations. The numerical results show that DEA is well suited for determining the efficient combinations of GA operators. Among the combinations under consideration, the combinations using tournament selection and simple crossover are generally more efficient. The proposed approach can be adopted to evaluate the relative efficiency of other meta-heuristics, so it also contributes to the algorithm development and evaluation for solving combinatorial optimization problems from the operational research perspective.
AB - This study proposes an alternative to the conventional empirical analysis approach for evaluating the relative efficiency of distinct combinations of algorithmic operators and/or parameter values of genetic algorithms (GAs) on solving the pickup and delivery vehicle routing problem with soft time windows (PDVRPSTW). Our approach considers each combination as a decision-making unit (DMU) and adopts data envelopment analysis (DEA) to determine the relative and cross efficiencies of each combination of GA operators and parameter values on solving the PDVRPSTW. To demonstrate the applicability and advantage of this approach, we implemented a number of combinations of GA's three main algorithmic operators, namely selection, crossover and mutation, and employed DEA to evaluate and rank the relative efficiencies of these combinations. The numerical results show that DEA is well suited for determining the efficient combinations of GA operators. Among the combinations under consideration, the combinations using tournament selection and simple crossover are generally more efficient. The proposed approach can be adopted to evaluate the relative efficiency of other meta-heuristics, so it also contributes to the algorithm development and evaluation for solving combinatorial optimization problems from the operational research perspective.
KW - Algorithm evaluation
KW - Data envelopment analysis
KW - Genetic algorithm
KW - Pickup and delivery
KW - Soft time windows
KW - Vehicle routing problem
UR - http://www.scopus.com/inward/record.url?scp=84861328994&partnerID=8YFLogxK
U2 - 10.1016/j.cie.2012.04.005
DO - 10.1016/j.cie.2012.04.005
M3 - Article
AN - SCOPUS:84861328994
SN - 0360-8352
VL - 63
SP - 520
EP - 529
JO - Computers and Industrial Engineering
JF - Computers and Industrial Engineering
IS - 2
ER -