A rich vehicle routing problem in express freight transportation

We consider the rich VRP arising at Trans-Cel, an Italian freight transportation company owning a fleet of 15 trucks with different capacities, loading facilities and operational costs. The company receives short- and medium-haul transportation demands consisting of a pick-up and a delivery with soft or hard time windows falling in the same day or in two consecutive days. Routes are planned on a daily basis taking into account constraints on maximum duration, number of consecutive driving hours and compulsory drivers' rest periods. Routes may not terminate at the depot, the termination point determining the next-day starting point. Several additional issues are considered among which: soft and hard constraints on route termination points, transshipment at the depot, fast route re-optimization triggered by additional real-time demands or vehicle faults, preferences on demands to be satisfied by a same vehicle. The objective is to maximize the profit defined as the difference between the revenue associated to satisfied demands and the operational costs, mainly depending on vehicles' type and on route length. In order to provide the core of a decision support tool to be used at the planning and operational stages, we propose a heuristic algorithm. Initial routes are determined by an enhanced least-cost insertion heuristic. The solution is then improved by a granular tabu search with intensification and diversification phases, and neighborhood based on selected insertion, swap and 2-opt moves. Results validated on the field attest for an estimated 9% profit improvement with respect to the current policy based on human expertise.