Hybrid Genetic Algorithm for CSOP to Find the Lowest Hamiltonian Circuit in a Superimposed Graph

摘要

Many fields use the graphs as a tool of representation such as multimodal networks, computer networks, wireless sensor networks, energy distribution. But, beyond the representation of data, the graphs also serve to propose solutions to certain problems mentioning the well-known problem finding the shortest Hamiltonian circuit in a graph. The arm of this paper is to elucidate a mechanism to obtain the most efficient Hamiltonian circuit among specified nodes in a given superimposed graphs (SGs). The Hamiltonian circuit is a circuit that visits each node on the graph exactly once. The SG represents a scheme of multimodal transportation systems and takes into account distance among other variables. The Hamiltonian path may be constructed and adjusted according to specific constraints such as time limits. This paper introduces new constraint satisfaction optimization problem formalism (CSOP) for the problem of finding the lowest Hamiltonian circuit in superimposed graphs, and as a resolution method, we use the genetic algorithm. As a case study, we adopt the transportation data of Guangzhou, in China.