Optimization of Block Ice Distribution Route using Insertion and Swap-based Local Search Improvement method: A Case Study

Abstract

PT X is a company engaged in the production of block ice and tube (crystal) ice, which currently faces the problem of unplanned and non-systematic distribution routes. This problem falls within the category of the Vehicle Routing Problem (VRP), specifically the Multi-Trip Vehicle Routing Problem (MTVRP). This study aims to determine new distribution routes for 25 kg block ice at PT X that minimize total travel distance by applying the Saving Matrix and Nearest Neighbour methods, followed by route improvement using Local Search techniques, namely 1–Insertion Intra-Route and (1–1) Swap Intra-Route. The results indicate that the Local Search-based Insertion and Swap Intra-Route method yields the greatest improvement, achieving a distance reduction of 44.59% compared to the company’s existing route.