The new approaches for solving hierarchical Chinese postman problem with stochastic travel times

Çomaklı Sökmen Ö., Yilmaz M.

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, cilt.44, sa.5, ss.8471-8492, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 44 Sayı: 5
  • Basım Tarihi: 2023
  • Doi Numarası: 10.3233/jifs-222097
  • Dergi Adı: JOURNAL OF INTELLIGENT & FUZZY SYSTEMS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.8471-8492
  • Anahtar Kelimeler: Optimization, arc routing problems, chance-constrained stochastic programming, new efficient algorithm, hierarchical Chinese postman problem, VEHICLE-ROUTING PROBLEM, HARD TIME, WINDOWS, ALGORITHM
  • Atatürk Üniversitesi Adresli: Evet

Özet

The hierarchical Chinese postman problem (HCPP) aims to find the shortest tour or tours by passing through the arcs classified according to precedence relationship. HCPP, which has a wide application area in real-life problems such as shovel snow and routing patrol vehicles where precedence relations are important, belongs to the NP-hard problem class. In real-life problems, travel time between the two locations in city traffic varies due to reasons such as traffic jam, weather conditions, etc. Therefore, travel times are uncertain. In this study, HCPP was handled with the chance-constrained stochastic programming approach, and a new type of problem, the hierarchical Chinese postman problem with stochastic travel times, was introduced. Due to the NP-hard nature of the problem, the developed mathematical model with stochastic parameter values cannot find proper solutions in large-size problems within the appropriate time interval. Therefore, two new solution approaches, a heuristic method based on the Greedy Search algorithm and a meta-heuristic method based on ant colony optimization were proposed in this study. These new algorithms were tested on modified benchmark instances and randomly generated problem instances with 817 edges. The performance of algorithms was compared in terms of solution quality and computational time.