DEVELOPING HEURISTIC METHOD FOR PICKUP AND DELIVERY VEHICLE ROUTING PROBLEM WITH TIME WINDOW (PDVRPTW)

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

Vehicle Routing Problem, commonly abbreviated as VRP, is a globally studied problem on assigning a set of location to vehicles to minimize an objective calculated from routes scheduled on each vehicles. This problem is considered to be NP-Hard and comes with a lot of variants. Relevant to this paper, the variants contains capacity, time window, and pickup delivery constraints, combined abbreviated as PDVRPTW. Studies on VRP variants usually consist of initial solution generation followed by optimization strategy. In this paper, a heuristic method is developed utilizing balanced graph clustering and dynamic programming for hierarchically breakdown large graphs, also reassignments and bipartite matching for incorporating time window. This solution is then experimented on each optimization strategy, namely steepest hill climbing, simulated annealing, and tabu search. Results shows that balanced k-medoids is the best clustering method that generates TSP solution 3-15% worse than best known solutions. This heuristic method also generates solution with number of vehicles less than 130% of best known solutions on PDVRPTW instances.