HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem. We present HAS-SOP, a new approach to solving sequential ordering problems. HAS-SOP combines the ant colony algorithm, a population-based metaheuristic, with a new local optimizer, an extension of a TSP heuristic which directly handles multiple constraints without increasing computational complexity. We compare different implementations of HAS-SOP and present a new data structure that improves system performance. Experimental results on a set of twenty-three test problems taken from the TSPLIB show that HAS-SOP outperforms existing methods both in terms of solution quality and computation time. Moreover, HAS-SOP improves most of the best known results for the considered problems.

References in zbMATH (referenced in 14 articles )

Showing results 1 to 14 of 14.
Sorted by year (citations)

  1. Shobaki, Ghassan; Jamal, Jafar: An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers (2015)
  2. Pintea, Camelia-Mihaela: Advances in bio-inspired computing for combinatorial optimization problems (2014)
  3. Changdar, C.; Mahapatra, G. S.; Pal, R. K.: An ant colony optimization approach for binary knapsack problem under fuzziness (2013)
  4. Xu, Zilong; Zhao, Hong; Min, Fan; Zhu, William: Ant colony optimization with three stages for independent test cost attribute reduction (2013) ioport
  5. Sharma, Vikas K.; Agarwal, Manju; Sen, Kanwar: Reliability evaluation and optimal design in heterogeneous multi-state series-parallel systems (2011) ioport
  6. Agarwal, Manju; Sharma, Vikas K.: Ant colony approach to constrained redundancy optimization in binary systems (2010)
  7. Donati, Alberto V.; Montemanni, Roberto; Casagrande, Norman; Rizzoli, Andrea E.; Gambardella, Luca M.: Time dependent vehicle routing problem with a multi ant colony system (2008)
  8. Lim, Kwee Kim; Ong, Yew-Soon; Lim, Meng Hiot; Chen, Xianshun; Agarwal, Amit: Hybrid ant colony algorithms for path planning in sparse graphs (2008) ioport
  9. Felner, Ariel; Shoshani, Yaron; Altshuler, Yaniv; Bruckstein, Alfred M.: Multi-agent physical A* with large pheromones. (2006) ioport
  10. Pour, Hamid Davoud; Nosraty, Mostafa: Solving the facility and layout and location problem by ant-colony optimization-meta heuristic (2006)
  11. Dulluri, Sandeep; Srinivasa Raghavan, N. R.: Allocation of advertising space by a web service provider using combinatorial auctions (2005)
  12. Guerriero, F.; Mancini, M.: Parallelization strategies for rollout algorithms (2005)
  13. Ying, Kuo-Ching; Liao, Ching-Jong: An ant colony system for permutation flow-shop sequencing (2004)
  14. Eggers, Jan; Feillet, Dominique; Kehl, Steffen; Wagner, Marc Oliver; Yannou, Bernard: Optimization of the keyboard arrangement problem using an ant colony algorithm. (2003)