Solving the Messenger problem using Large Neighborhood Search

Abstract

This research studies the vehicle routing problem of parcel shipping. Which, instead of using one trip per job, this study introduces a more efficient approach by combining several jobs and turning them into a series of pickup and delivery services. Large Neighborhood Search Metaheuristics is used to solve a mathematical model formulated based on the characteristics of problem such as vehicle capacity and service time windows, seeking the most efficient route and pickup and delivery order. For simplicity, the impact of road traffic is disregarded. The study shows that the total cost of this approach is significantly lower compared to the conventional method.