Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)

Muhammad Luthfi Shahab; Daryono Budi Utomo; Mohammad Isa Irawan

Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)

Muhammad Luthfi Shahab, Daryono Budi Utomo, Mohammad Isa Irawan

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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 language	English
Pages (from-to)	461-468
Number of pages	8
Journal	Journal of Theoretical and Applied Information Technology
Volume	87
Issue number	3
Publication status	Published - 31 May 2016

Keywords

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

Cite this

@article{1ca3daca88934669bd41593d071ee0f1,

title = "Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)",

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.",

keywords = "Capacitated vehicle routing problem (CVRP), Decomposition, Genetic algorithm (GA), Two-step genetic algorithm (TSGA)",

author = "Shahab, {Muhammad Luthfi} and Utomo, {Daryono Budi} and Irawan, {Mohammad Isa}",

year = "2016",

month = may,

day = "31",

language = "English",

volume = "87",

pages = "461--468",

journal = "Journal of Theoretical and Applied Information Technology",

issn = "1992-8645",

publisher = "Little Lion Scientific",

number = "3",

}

TY - JOUR

T1 - Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)

AU - Shahab, Muhammad Luthfi

AU - Utomo, Daryono Budi

AU - Irawan, Mohammad Isa

PY - 2016/5/31

Y1 - 2016/5/31

N2 - 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.

AB - 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.

KW - Capacitated vehicle routing problem (CVRP)

KW - Decomposition

KW - Genetic algorithm (GA)

KW - Two-step genetic algorithm (TSGA)

UR - http://www.scopus.com/inward/record.url?scp=84971451919&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84971451919

SN - 1992-8645

VL - 87

SP - 461

EP - 468

JO - Journal of Theoretical and Applied Information Technology

JF - Journal of Theoretical and Applied Information Technology

IS - 3

ER -

Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)

Abstract

Keywords

Other files and links

Fingerprint

Cite this