A branch-And-Cut algorithm for the mixed fleet green vehicle routing problem
提出一种分支切割算法，通过新不等式处理电池容量和时间约束，高效求解含燃油车和电动车的混合车队绿色车辆路径问题，可解决多达100个客户的基准实例。
• We develop a branch-and-cut algorithm for solving the mixed fleet green vehicle routing problem. • Several new inequalities are introduced to address driving range and duration constraints. • We perform extensive computational tests to highlight the performance of the algorithm. • The algorithm efficiently solves benchmark instances with up to 100 customers. In this paper, we propose a new branch-and-cut algorithm for solving the mixed-fleet green vehicle routing problem (MFGVRP). The MFGVRP is an NP-hard optimisation problem that generalises both the capacitated vehicle routing problem and the green vehicle routing problem. To efficiently utilise a branch-and-cut framework, we introduce several new classes of inequalities, used as cutting planes, focusing on both battery capacities and time constraints. Extensive computational experiments demonstrate the effectiveness of our methodology. Our algorithm successfully solves several benchmark instances with up to 100 customers within one hour of computation time for both a heterogeneous fleet of internal combustion engine vehicles and electric vehicles, as well as a homogeneous fleet of electric vehicles. Additionally, we find the optimal solution for two previously unsolved instances from the literature. A comparative analysis with a compact integer programming model shows that our method outperforms the formulation in terms of computational efficiency, making it a competitive alternative for large-scale MFGVRP instances.