Memetic fireworks algorithm for solving N-vehicle exploration problem

The N-vehicle exploration problem is a class of NP-hard problem, which aims to schedule a fleet of N vehicles' trip sequence under limited oil to ensure one of the vehicles visit the farthest distance. A Memetic fireworks algorithm(MFWA) with local search enhancement is proposed to solve this discrete optimization problem. According to the characteristic of equivalence to permutation, a ranked-order value(ROV) scheme is adopted to encode the candidate solution, and the fireworks algorithm with dynamic radius of explosion is employed to search the solution space globally. To enhance the local search ability, three neighbor operations by insertion, exchange and reverse are employed to carry out local refinement. The effect of key parameters with regard to the performance is investigated. Numerical results about 14 benchmark instances are provided, and the comparisons suggest that the MFWA is superior to(at least not inferior to) the standard fireworks algorithm(FWA), the existing heuristic algorithms(H1-H4), particle swarm optimization(PSO) and water wave optimization(WWO) in terms of solution accuracy and stability; compared with the MFWA, tabu-based variable neighborhood local search(TBVLS) obtains a maximal competitive ratio of 1.126 at the expense of nearly 55 times computational efforts. These results indicate that the MFWA can achieve satisfactory results in reasonable time. © 2018, Editorial Office of Control and Decision. All right reserved.