MULTITASK n-VEHICLE EXPLORATION PROBLEM:COMPLEXITY AND ALGORITHM

This paper extends the single-task n-Vehicle Exploration Problem to Multitask n-Vehicle Exploration Problem （MTNVEP）, by combining n-Vehicle Exploration Problem with Job Scheduling Problem. At first, the authors prove that MTNVEP is NP-hard for fixed number of tasks, and it is strongly NP-hard for general number of tasks. Then they propose an improved accurate algorithm with computing time O（n3n）, which is better than O（n!） as n becomes sufficiently large. Moreover, four heuristic algorithms are proposed. Effectiveness of the heuristic algorithms is illustrated by experiments at last.

Research on the Efficient Computation Mechanism-in the Case of N-vehicle Exploration Problem

The research of efficient computation focus on special structures of NP-hard problem instances and request providing reasonable computing cost of instances in polynomial time. Based on the theory of combinatorial optimization, by studying the clusters partition and the clusters complexity measurement in Nvehicle exploration problem, we build a frame of efficient computation and provide an application of tractability for NP-hard problem. Three N-vehicle examples show that when we use efficient computation mechanism on N-vehicle, through polynomial steps of tractability analysis, decision makers can get the computing cost of searching optimal solution before practical calculation.

A Linear Mixed Integer Programming Model for N-Vehicle Exploration Problem

Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties.The model is then proved equivalent to the original problem.Given the model,one can apply the already existed methods and algorithms for mixed integer linear programming on N-vehicle exploration problem,which helps to enrich methods for solving N-vehicle exploration problem.

A Variant of Multi-task n-vehicle Exploration Problem: Maximizing Every Processor's Average Profit

We discuss a variant of the multi-task n-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same destination. Given n tasks with assigned consume-time and profit, it may also be viewed as a maximization of every processor＇s average profit. Further, we propose a new kind of partition problem in fractional form and analyze its computational complexity. By regarding fractional partition as a special case, we prove that the average profit maximization problem is NP-hard when the number of processors is fixed and it is strongly NP- hard in general. At last, a pseudo-polynomial time algorithm for the average profit maximization problem and the fractional partition problem is presented, using the idea of the pseudo-polynomial time algorithm for the classical partition problem.

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),which was inefficient to solve practical problems.This paper establishes a more concise MILP model,where the number of constraints is just O(n2).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.