The n-vehicle exploration problem is NP-complete

The $n$-vehicle exploration problem (NVEP) is a combinatorial search problem, which tries to find a permutation of $n$ vehicles to make one of the vehicles travel the maximal distance. Assuming the $n$ vehicles travel together, with some vehicles being used to refuel others, and at last all the vehicles return to the start point. NVEP has a fractional form of objective function, and its computational complexity of general case remains open. Given a directed graph $G$, if it has a Hamiltonian path, then the Hamiltonian path can be reduced in polynomial time to a single instance of NVEP, in which the traveling distance is at least $n$. The total length consists of $n$ parts, each of which is required to equal to $1$. We prove that $G$ has a hamiltonian path of total weight of $n$ if and only if the reduced NVEP instance has a sequence of length at least $n$ with each term equals to $1$. Therefore we show that Hamiltonian path $\leq_P$ NVEP, and consequently prove that NVEP is NP-complete.