Abstract
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 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. 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
LACOMME: Philippe, PRINS, Christian and SEVAUX, Marc.: Algorithmes de graphes. Eyrolles Paris (2003)
Wu, E.-F., Jin, Y., Bao, J.-S., Hu, X.-F.: A branch-and-bound algorithm for two-sided assembly line balancing. Int. J. Adv. Manuf. Technol. 39(9–10), 1009–1015 (2008)
Zeng, W., Church, R.L.: Finding shortest paths on real road networks. Int. J. Geograph. Inf. Sci. 23(4), 531–543 (2009)
Wang, F.-Y., Zhang, H., Liu, D.: Adaptive dynamic programming: an introduction. IEEE Comput. Intell. Mag. 4(2), 41–43 (2009)
Nesmachnow, S.: An overview of metaheuristics: accurate and efficient methods for optimisation. Int. J. Metaheuristics 3(4), 320–347 (2014)
Sörensen, K., Glover, F.W.: Metaheuristics. In: Gass, S.I., Fu, M.C. (eds.) Encyclopedia of Operations Research and Management Science, pp. 960–970. Springer, Boston (2013). https://doi.org/10.1007/978-1-4419-1153-7
Hoffman, K.L., Padberg, M., Rinaldi, G.: Traveling salesman problem. In: Gass, S.I., Fu, M.C. (eds.) Encyclopedia of Operations Research and Management Science, pp. 1573–1578. Springer, Boston (2013). https://doi.org/10.1007/978-1-4419-1153-7
Lalla-Ruiz, E., Expósito-Izquierdo, C., Taheripour, S., Vo, S.: An improved formulation for the multi-depot open vehicle routing problem. OR Spectrum 38(1), 175–187 (2016)
Bolaños, R., Echeverry, M., Escobar, J.: A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the multiple travelling salesman problem. Decis. Sci. Lett. 4(4), 559–568 (2015)
Mnif, M., Bouamama, S.: A multi-objective formulation for multimodal transportation network’s planning problems. In: IEEE International Conference on Service Operations and Logistics, and Informatics, pp. 144–149 (2017)
Braun, U., Muldoon, S.F., Bassett, D.S.: On human brain networks in health and disease. eLS (2015)
Bouazzi, K., Hammami, M., Bouamama, S.: Modelling the shortest hamiltonian circuit problem in superimposed graphs with distributed constraint optimization problems. In: International Conference on Metaheuristics and Nature Inspired Computing, Marrakech in Morocco (2018)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics, vol. 1, no. 244, p. 2 (2008)
Tsang, E.: Foundations of Constraint Satisfaction: The Classic Text. BoD–Books on Demand (2014)
Pesant, G., Gendreau, M., Potvin, J.-Y., Rousseau, J.-M.: An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transp. Sci. 32(1), 12–29 (1998)
Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60–100 (1991)
Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S.: Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl. Soft Comput. 12(3), 1231–1237 (2012)
Talbi, E.-G.: Metaheuristics from Design to Implementation, vol. 74. Wiley, Hoboken (2009)
Chen, S., Claramunt, C., Ray, C.: A spatio-temporal modelling approach for the study of the connectivity and accessibility of the Guangzhou metropolitan network. J. Transp. Geogr. 36, 12–23 (2014)
Bouazzi, K., Hammami, M., Bouamama, S.: CSOP framework for lowest hamiltonian circuit in superimposed graph. In: The International Society for Engineers and Researchers - International Conference on Science, Technology, Engineering and Management (ICSTEM), New York, USA (2018)
Aguayo, M.M., Sarin, S.C., Sherali, H.D.: Solving the single and multiple asymmetric Travelling Salesmen Problems by generating subtour elimination constraints from integer solutions. IISE Trans. 50(1), 45–53 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Bouazzi, K., Hammami, M., Bouamama, S. (2019). Hybrid Genetic Algorithm for CSOP to Find the Lowest Hamiltonian Circuit in a Superimposed Graph. In: Rutkowski, L., Scherer, R., Korytkowski, M., Pedrycz, W., Tadeusiewicz, R., Zurada, J. (eds) Artificial Intelligence and Soft Computing. ICAISC 2019. Lecture Notes in Computer Science(), vol 11509. Springer, Cham. https://doi.org/10.1007/978-3-030-20915-5_46
Download citation
DOI: https://doi.org/10.1007/978-3-030-20915-5_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-20914-8
Online ISBN: 978-3-030-20915-5
eBook Packages: Computer ScienceComputer Science (R0)