Adaptation of ant supercolony behavior to solve route assignment problem in integers

Until now, the algorithms used to compute an equilibrate route assignment do not return an integer solution. This disagreement constitutes a non-negligible drawback. In fact, it is shown in the literature that a fractional solution is not a good approximation of the integer one. The purpose of this paper is to find an integer route assignment.

The static route assignment problem is modeled as an asymmetric network congestion game. Then, an algorithm inspired from ant supercolony behavior is constructed, in order to compute an approximation of the Pure Nash Equilibrium (PNE) of the considered game. Several variants of the algorithm, which differ by their initializing steps and/or the kind of the provided algorithm information, are proposed.

An evaluation of these variants over different networks is conduced and the obtained results are encouraging. Indeed, the adaptation of ant supercolony behavior to solve the problem under consideration shows interesting results, since most of the algorithm’s variants returned high-quality approximation of PNE in more than 91 percent of the treated networks.

The asymmetric network congestion game is used to model route assignment problem. An algorithm with several variants inspired from ant supercolony behavior is developed. Unlike the classical ant colony algorithms where there is one nest, herein, several nests are considered. The deposit pheromone of an ant from a given nest is useful for the ants of the other nests.