PICKUP AND DELIVERY VEHICLE ROUTING PROBLEM TIME WINDOW (PDVRPTW) OPTIMIZATION SYSTEM WITH APPLIED DISTRIBUTION AND PARALLELIZATION PRINCIPLES

• Main Author: Arya Bagaspati, Kinantan
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/86562
• Institution: Institut Teknologi Bandung

It is not uncommon for the concepts of distribution and parallelization to be applied in solving combinatorial optimization problems. One of the relevant and well-known NP-hard combinatorial optimizations is the Vehicle Routing Problem (VRP). In this case, delivery constraints, service time, and capacity are imposed on the problem, turning it into PDVRPTW. A heuristic method is used as a reference, aimed at solving the soft constraint problem of PDVRPTW by utilizing Hierarchical Graph Clustering with Balanced K-means, along with time and capacity constraints as the main objective functions, and incorporating several Local Search optimization strategies with insertion operators to generate neighboring solutions. In order to apply the principles of distribution and parallelization, a modified model of the reference method has been designed. From the perspective of graph processing, Affinity Hierarchical Clustering utilizing Adaptive Massively Parallel Computation is applied in the graph processing of the reference method. Additionally, a new reachability objective function is designed and added to the existing multi-objective framework. Finally, regarding optimization strategies, the reference method, which has already demonstrated optimal performance with the Tabu Search strategy, shows further improvement when integrated with Genetic Algorithm into a hybrid optimization approach due to the significant parallelization potential of Genetic Algorithms. The parallel and distributed model testing was conducted using the Solomon dataset and several adapted variants from VRP-REP 100, 200, 400, and 800 task counts. For a fairly large number of tasks, the modified reference method and optimization that had integrated the Genetic Algorithm yielded an error of 4-10% from the best solution, showing a significant improvement over the reference method, which had an error ranging around 15%. As the number of computing units increases, the speedup factor also approaches the number of computing units used, which demonstrates that the modifications made to enable parallelism are quite successful.