On the periodic hierarchical Chinese postman problem

Keskin M. E., Triki C.

SOFT COMPUTING, cilt.26, sa.2, ss.709-724, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 26 Sayı: 2
  • Basım Tarihi: 2022
  • Doi Numarası: 10.1007/s00500-021-06213-2
  • Dergi Adı: SOFT COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Sayfa Sayıları: ss.709-724
  • Anahtar Kelimeler: Hierarchical Chinese postman problem, Periodicity restrictions, Layer algorithm, Simulated annealing, Etc, ARC-ROUTING PROBLEM, TRAVELING SALESMAN PROBLEM, ALGORITHM, SEARCH
  • Atatürk Üniversitesi Adresli: Evet

Özet

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.