A generalized set partitioning model for MinMax vehicle routing

This paper proposes a new approach to modeling of vehicle routing problems with a MinMax objective. At the core of the approach, we formulate a Generalized Set Partitioning Problem (GSPP) which is used for minimizing infeasibility of the considered vehicle routing problem for a given upper bound on the objective value. Generally, the optimal value of the MinMax objective is obtained as the smallest upper bound for which the formulated GSPP obtains a total infeasibility of zero. We propose to solve the new formulation using branch-and-price and demonstrate the effectiveness of the approach through computational results. • We propose a new modeling approach for vehicle routing with a MinMax objective. • The approach uses a Generalized Set Partitioning Problem solved by branch-and-price. • Feasibility is checked for a given route length using LP or ILP models. • The method outperforms a state-of-the-art method in solving benchmark instances. • The model structure is general and can apply to various MinMax routing problems.