CSOP Framework for Lowest Hamiltonian Circuit in 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 in problem finding the shortest Hamiltonian circuit in a graph. The aim 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. To find the shortest path, we test the CSOP formalism on real data of the transportation system using CPLEX and compare the results with other models.
Keywords - Optimization problems, Constraint satisfaction problems, Graph theory, Hamiltonian circuit, Superimposed graphs