Data envelopment analysis for evaluating the efficiency of genetic algorithms on solving the vehicle routing problem with soft time windows

Chung-Cheng Lu, Vincent F. Yu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)520-529
Number of pages10
JournalComputers and Industrial Engineering
Volume63
Issue number2
DOIs
StatePublished - 1 Sep 2012

Keywords

  • Algorithm evaluation
  • Data envelopment analysis
  • Genetic algorithm
  • Pickup and delivery
  • Soft time windows
  • Vehicle routing problem

Fingerprint Dive into the research topics of 'Data envelopment analysis for evaluating the efficiency of genetic algorithms on solving the vehicle routing problem with soft time windows'. Together they form a unique fingerprint.

Cite this