A Novel MILP Model for N-vehicle Exploration Problem

The N-vehicle exploration problem (NVEP) is a nonlinear discrete scheduling problem, and the complexity status remains open. To our knowledge, there is no literature until now employing mixed integer linear programming (MILP) technology to solve this problem except for Wang (J Oper Res Soc China 3(4):489–498, 2015). However, they did not give numerical experiments since their model existed strictly inequalities and the number of constraints was up to O(n3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^3)$$\end{document}, which was inefficient to solve practical problems. This paper establishes a more concise MILP model, where the number of constraints is just O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^2)$$\end{document}. Therefore, the existing efficient MILP algorithms can be used to solve NVEP. Secondly, we provide some properties of N-vehicle problem and give three methods for cutting plane construction, which can increase the solving speed significantly. Finally, a numerical experiment is provided to verify the effectiveness and robustness for different instances and scales of acceleration techniques.