Abstract

Capacitated vehicle routing problem (CVRP) is one of the vehicle routing problem (VRP) that uses capacity restriction on the vehiclesk used. There are many methods have been studied to solve CVRP. To solve CVRP, it is possible to decompose CVRP into regions (sub problems) that can be solved independently. A two-step genetic algorithm (TSGA) is formulated in this paper. TSGA is used to decompose CVRP and then find the shortest route for each region using two different simple genetic algorithms. TSGA is then compared with genetic algorithm (GA). To compare these two algorithms, four instances is formed, those are P50, P75, P100, and P125. For each instance, fourteen different vehicle capacities is used. The results show that TSGA is better than GA in terms of computational time and distance except for some small vehicle capacities at P50 and P75.

Original languageEnglish
Pages (from-to)461-468
Number of pages8
JournalJournal of Theoretical and Applied Information Technology
Volume87
Issue number3
Publication statusPublished - 31 May 2016

Keywords

  • Capacitated vehicle routing problem (CVRP)
  • Decomposition
  • Genetic algorithm (GA)
  • Two-step genetic algorithm (TSGA)

Fingerprint

Dive into the research topics of 'Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)'. Together they form a unique fingerprint.

Cite this