Solving a Vehicle Routing Problem for a Real-Life Parcel Locker-Based Delivery

In this paper a problem modeled after a real-life system of delivering orders to parcel lockers is considered. The problem is formulated as an extension of the Vehicle Routing Problem with total travel time as the goal function. Several constraints, including vehicle capacity, travel time limits as well as parking and order service times, are formulated. Two heuristics are proposed as solving methods: a Genetic Algorithm population metaheuristic and a greedy method, which is also used as a reference point. A computer experiment is performed using large-size problem instances based on real-life parcel locker locations for an existing delivery company in the city of Wrocław, Poland. The results indicate that the proposed Genetic Algorithm method vastly outperforms the greedy method, obtaining solutions with several times less total travel time and runs under 5 min even for instances with 10000 orders. The influence of the number of orders and parcel locations on the result are discussed as well.