Mathematical formulations and improvements for the multi-depot open vehicle routing problem

The multi-depot open vehicle routing problem (MDOVRP) is a hard combinatorial optimization problem belonging to the vehicle routing problem family. It considers vehicles departing from different depots to deliver goods to customers without requiring to return to the depots once all customers have been served. The aim of this work is to provide a new two-index-based mathematical formulation for the MDOVRP as well as enhancements on alternative sub-tour elimination constraints. Through numerical experiments, using traditional benchmarks for the MDOVRP, we show that the proposed formulation outperforms existing ones. In addition, we provide insights with regards to problem instance defining parameters on the models performance.

Automated summary

This work introduces a new two-index-based mathematical formulation for the multi-depot open vehicle routing problem (MDOVRP) and enhances alternative sub-tour elimination constraints. Through numerical experiments using traditional benchmarks, the proposed formulation is shown to outperform existing ones. Insights are also provided on the impact of defining problem instance parameters on the model's performance.