The collaborative consistent vehicle routing problem with workload balance

The rising competition in the logistics sector forces companies to be more economically efficient. One of the major sources of inefficiency is the incomplete usage of available resources, such as vehicles’ capacities. Mechanism that allow to better exploit such resources by enabling carrier collaborations are on the rise. Our study examines a centrally organized multi-period collaborative vehicle routing problem, where carriers can exchange customers who have to be serviced on a regular basis. Collaborations, where carriers serve frequent customers, are supposed to face the problem of (i) time consistency in terms of visiting time, and of (ii) service consistency. The latter ensures that customers are visited by the same collaboration partner throughout the whole planning horizon. Additionally, carriers might only be willing to enter a collaboration if a minimum market share can be guaranteed. In order to take all these issues into account, we introduce the collaborative vehicle routing problem with time and service consistency and workload balance. The mathematical model including several valid inequalities is presented. In a computational study, we solve small-sized instances to optimality. In order to tackle larger instances, we propose an efficient and effective matheuristic and an iterated local search algorithm. We show that both methods reach near optimal solutions within very short computational times. Managerial insights on the cost of imposing time and service consistency as well as workload balancing constraints are presented and discussed. We show that, according to our computational study, consistency constraints can be imposed for almost no additional cost, while workload balancing constraints do not have any negative effect on the total collaboration profit. This is a meaningful insight and might be a strong argument for carriers to enter collaborations.