An Algorithm Combining Linear Programming and an Ant System for the Sequential Ordering Problem

DOI: 10.5176/2251-2179_ATAI34

Authors: M. Mojana, R. Montemanni, G. Di Caro and L.M. Gambardella

Abstract:

The Sequential Ordering Problem is a combinatorial optimization problem that can be used to model many real world applications arising in different fields. A vast collection of exact and heuristic algorithms has been proposed for the problem over the years. Exact methods are mainly based on solving mixed integer linear programming models of the problem, while heuristic approaches are typically based on the imitation of phenomenon observed in Nature. In this paper we hybridize a solver working on a mixed integer programming model with an Ant System algorithm (inspired by real ants), ending up with a hybrid matheuristic approach. Experimental results are finally presented and discussed.

Keywords: Sequential ordering problems; matheuristic algorithms; ant colony optimization; linear programming; hybrid metaheuristic algorihtms.