Local search-based heuristics for the vehicle routing problem with arrival smoothing at the depot

Abstract

In this work, we address a classical multi-trip vehicle routing problem with capacity and time windows, adding the goal of smoothing vehicle arrivals at the final depot. A fleet must collect items from a set of prioritized vendors, each with time windows and item quantities. The depot has a piecewise constant receiving capacity, limiting how many items can be handled at any given time. The objective is to plan routes that maximize the total priority of visited vendors while respecting the depot’s receiving limits and maintaining route quality. We propose constructive and local search heuristics and evaluate their performance on real-world instances.