Modifikasi Algoritma Simulated Annealing dengan Operator Crossover pada Capacitated Vehicle Routing Problem (CVRP)

Hakristuti, Tanti (2024) Modifikasi Algoritma Simulated Annealing dengan Operator Crossover pada Capacitated Vehicle Routing Problem (CVRP). Sarjana thesis, UIN Sunan Gunung Djati Bandung.

Preview	Text (COVER) Cover Skripsi.pdf Download (43kB) | Preview
Preview	Text (DAFTAR ISI) Daftar Isi Skripsi.pdf Download (84kB) | Preview
Preview	Text (ABSTRAK) Abstrak Skripsi.pdf Download (27kB) | Preview
Preview	Text (BAB I) BAB 1.pdf Download (137kB) | Preview
	Text (BAB II) BAB 2.pdf Restricted to Registered users only Download (295kB)
	Text (BAB III) BAB 3.pdf Restricted to Registered users only Download (393kB)
	Text (BAB IV) BAB 4.pdf Restricted to Registered users only Download (517kB)
	Text (BAB V) BAB 5.pdf Restricted to Registered users only Download (89kB)
	Text (DAFTAR PUSTAKA) Daftar Pustaka.pdf Restricted to Registered users only Download (129kB)

Abstract

Capacitated Vehicle Routing Problem (CVRP) is a route optimization problem that finds the best route for vehicles to deliver goods from one depot to several customers, considering the vehicle capacity constraints. This study aims to propose and evaluate an enhanced Simulated Annealing algorithm with crossover operator, called SA-OC, to improve the quality of CVRP solutions as well as identify appropriate initial parameters and develop computationally efficient techniques. This algorithm uses a population-based approach, where solutions are developed through local search operators such as swap, scramble, insertion, and reversion. The concept of split routes is used to develop routes in the solution. The crossover operators Partially Mapped Crossover (PMX) and Order Crossover (OX) are applied to solutions in the population to accelerate convergence. Crossover iterations are performed to generate variations in child solutions, increase genetic diversity, and help the algorithm avoid local traps. A selection method is used to ensure a balance between finding new solutions (exploration) and maximizing the benefits of existing good solutions (exploitation). The analysis results show that SA-OC with crossover iterations in 100 iterations achieves a good balance between solution quality and computational time. On 7 datasets, SA-OC with crossover iterations showed better solution quality than the version without iterations. Although the version with 1000 iterations produced the best solution, its computation time was much longer. Crossover iterations in 100 iterations allowed more effective exploration in the solution space, resulting in a good solution in a shorter time.

Actions (login required)

View Item