The $n$-vehicle exploration problem (NVEP) is a combinatorial optimization problem, which tries to find an optimal permutation of a fleet to maximize the length traveled by the last vehicle. NVEP has a fractional form of objective function, and its computational complexity of general case remains open. We show that Hamiltonian Path $\leq_P$ NVEP, and prove that NVEP is NP-complete.
翻译:$n$-车辆探索问题(NVEP)是一个组合优化问题,其目标是找到一种最佳的车队排列方式,使得最后的车辆行驶长度最大化。NVEP的目标函数具有分数形式,它的一般情况的计算复杂度仍然未知。我们证明了哈密尔顿路径$\leq _P$ NVEP,并证明了NVEP是NP完备的。