Heterogeneous multi-depot collaborative vehicle routing problem

Collaborative vehicle routing of multiple logistics providers is an important component of horizontal logistic collaboration that generates economic and societal benefits. Existing research on collaborative vehicle routing is limited to the homogeneous setting where the logistics providers transport the same product. To better address the need of a general modeling framework and fast computational methods for the growth of collaboration among logistics providers carrying various products, we investigate a heterogeneous multi-depot collaborative vehicle routing problem (HMCVRP) in this paper. The key operational and computational challenge of realizing the collaborative route planning is to properly select transfer points for product transshipment between vehicles of different depots. We propose a Benders-based branch-and-cut algorithm with the technique of combinatorial Benders' cuts to solve a mixed-integer programming formulation of HMCVRP. Numerical experiments indicate that the proposed algorithm significantly outperforms the CPLEX solver using the commonly adopted big-M transformation-based method. Additional computational study further reveals the importance of the locations of depots and having a well-designed cost savings allocation mechanism in practice.