MULTITASK n-VEHICLE EXPLORATION PROBLEM:COMPLEXITY AND ALGORITHM  

作　　者：Yangyang XU Jinchuan CUI 

机构地区：[1]Institute of Applied Mathematics,Academy of Mathematics and Systems Science,Chinese Academy of Sciences

出　　处：《Journal of Systems Science & Complexity》2012年第6期1080-1092,共13页系统科学与复杂性学报（英文版）

基　　金：partly supported by Daqing Oilfield Company Project of PetroCHINA under Grant No.dqc- 2010-xdgl-ky-002;Key Laboratory of Management,Decision and Information Systems,Chinese Academy of Sciences

摘　　要：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.

关 键 词：Multitask n-Vehicle Exploration Problem （MTNVEP） NP-HARD strongly NP-hard heuristic algorithm. 

分 类 号：U491[交通运输工程—交通运输规划与管理]