A Parallel Simulated Annealing Algorithm for Weapon-Target Assignment Problem

Weapon-target assignment (WTA) is a combinatorial optimization problem and is known to be NP-complete. The WTA aims to best assignment of weapons to targets to minimize the total expected value of the surviving targets. Exact methods can solve only small-size problems in a reasonable time. Although many heuristic methods have been studied for the WTA in the literature, a few parallel methods have been proposed. This paper presents parallel simulated algorithm (PSA) to solve the WTA. The PSA runs on GPU using CUDA platform. Multi-start technique is used in PSA to improve quality of solutions. 12 problem instances (up to 200 weapons and 200 targets) generated randomly are used to test the effectiveness of the PSA. Computational experiments show that the PSA outperforms SA on average and runs up to 250x faster than a single-core CPU.

@article{SONUC2017,
  title     = {A Parallel Simulated Annealing Algorithm for Weapon-Target Assignment Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {8},
  number    = {4},
  year      = {2017},
  publisher = {The Science and Information Organization},
  author    = {Emrullah SONUC and Baha SEN and Safak BAYIR},
  doi       = {10.14569/IJACSA.2017.080412},
  url       = {https://doi.org/10.14569/IJACSA.2017.080412}
}