ABSTRACT This article studies the impact of social constraints on the vehicle routing problem, with a particular focus on allowing overtimes for the drivers. Working overtime is common in practice, as it may improve driver utilization, but it also requires a more detailed cost structure in the routing problem. Motivated by an application at a florist company performing daily routes in a network of stores in Norway, we address a problem characterized by deliveries and split pickups, a heterogeneous fleet of capacitated trucks and a heterogeneous workforce of drivers. We tackle the problem by a route‐based mixed integer linear programming model. The objective of the model is to minimize a cost function, which includes route‐driving costs for ordinary working hours, overtime costs, plus the additional time picking up carts at pickup locations. The time workload of the drivers is also captured in several social constraints. The results outperform manually produced solutions and a commercial software, with cost reductions totaling 17.4%–36.4% and 9.7%–25.5%, respectively. The results also show how the routes and costs differ when different allowances of overtime are used in the model. Notably, the results illustrate that overtimes are beneficial for cost savings and they are most valuable to serve locations far away from the headquarters. We also compute results for when the cost minimization objective function is replaced by a distance minimization function. A comparison reveals that the distance minimization results may deviate significantly from the cost minimization results.
Braathen et al. (Fri,) studied this question.