On the periodic hierarchical Chinese postman problem

Autor:	Muhammed Emre Keskin, Chefi Triki
Rok vydání:	2021
Předmět:	Set (abstract data type) Route inspection problem Theoretical computer science Computer science Heuristic Horizon Binary number Computational intelligence Geometry and Topology New variant Solver Software Theoretical Computer Science
Zdroj:	Soft Computing. 26:709-724
ISSN:	1433-7479 1432-7643
DOI:	10.1007/s00500-021-06213-2
Popis:	This paper presents a mathematical formulation and a heuristic approach for a new variant of the Hierarchical Chinese Postman Problem (HCPP). Indeed, we introduce the concept of periodicity, and we define and solve, for the first time, the Periodic-HCPP, denoted as P-HCPP. Given that the resulting integer programming model makes use of a big number of binary variables and given the extended time horizon considered, 30 days in our case, the problem is characterized by a high level of complexity. However, our developed heuristic is able to solve instances having up to 40 nodes, 520 arcs and 5 hierarchies, whereas a general-purpose solver like Gurobi was not able to provide solutions for instances having more than 10 nodes. While the collected results are very encouraging, we provide at the end of this paper a set of possible future extensions of this work.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f786931694ece0023a5bd4c4a0bf273e https://doi.org/10.1007/s00500-021-06213-2 Zobrazit plný text záznamu Full text from SpringerLink