An improved formulation for the multi-depot open vehicle routing problem

The multi-depot open vehicle routing problem (MDOVRP) is a recent hard combinatorial optimization problem that belongs to the vehicle routing problem family. In the MDOVRP, the vehicles depart from several depots and once they have delivered the goods to the last customers in their routes they are not required to return to the depots. In this work, we propose a new mixed integer programming formulation for the MDOVRP by improving some constraints from the literature and proposing new ones. The computational experience carried out over problem instances from the literature indicates that our proposed model outperforms the existing one