Hybrid Metaheuristics for Solving Vehicle Routing Problem in Multi Bulk Product Shipments with Limited Undedicated Compartments

Studies and research related to the Vehicle Routing Problem (VRP) are mostly carried out on simple constraints. The study was conducted to find the shortest route that the carrier will take. Effective algorithms are sought to find better solutions. Another study will develop VRP cases to be closer to real conditions. In actual conditions, the VRP cases are very complex. Several solutions that are considered good can be implemented to solve this problem. VRP in shipping bulk products, such as oil, cements, and fertilizers is one of the daily logistical cases carried out in an archipelago country. Bulk products are shipped from the depot port city to other islands. The optimum solution is needed to make the delivery shorter distance and the products can be sent faster. The solution to the VRP case with a single product can no longer solve the problem of bulk product shipment. Bulk product shipment involves more than one product with more than one ship compartment. The number of ship compartments that are smaller than the number of products will further increase the complexity of the VRP of bulk product shipment. The combination of several metaheuristic methods and strategies of product selection to fill undedicated compartment of ship is used to find the shortest route. Modified Nawas Enscore Ham (M-NEH), Particle Swarm Optimization (PSO), and 3-Opt algorithms are combined to solve VRP. This hybrid algorithm called Hybrid Particle Swarm Optimization (HPSO) is improved and supports each other. HPSO provides a better solution than those algorithms separately and other metaheuristics namely Tabu Search (TS) and Genetic Algorithm (GA). The implementation of the algorithm to solve real data of bulk cement transportation supports the conclusion that HPSO is superior to the other algorithms. It has 0.99% more effective than the second best and about 3.42% more effective than the average total distance of five other compared metaheuristic methods.