Article 2022 · 2 atıf

On the periodic hierarchical Chinese postman problem

Ö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.

Anahtar Kelimeler

Hierarchical Chinese postman problem Periodicity restrictions Layer algorithm Simulated annealing Etc ARC-ROUTING PROBLEM TRAVELING SALESMAN PROBLEM ALGORITHM SEARCH

WoS Kategorileri

Computer Science, Artificial Intelligence Computer Science, Interdisciplinary Applications

Sürdürülebilir Kalkınma Amaçları

Sürdürülebilir Şehirler ve Topluluklar

Künye

Dergi: SOFT COMPUTING
Yıl: 2022
Cilt: 26
Sayı: 2
Sayfa: 709-724
ISSN: 1432-7643
eISSN: 1433-7479
DOI: 10.1007/s00500-021-06213-2
WoS UID: WOS:000713107000001

Yayını aç (DOI)