Article 2023 · 0 citations

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

Abstract

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.

Keywords

Optimization arc routing problems chance-constrained stochastic programming new efficient algorithm hierarchical Chinese postman problem VEHICLE-ROUTING PROBLEM HARD TIME WINDOWS ALGORITHM

WoS Categories

Computer Science, Artificial Intelligence

Sustainable Development Goals

Sustainable Cities and Communities

Citation

Journal: JOURNAL OF INTELLIGENT & FUZZY SYSTEMS
Year: 2023
Volume: 44
Issue: 5
Pages: 8471-8492
ISSN: 1064-1246
eISSN: 1875-8967
DOI: 10.3233/JIFS-222097
WoS UID: WOS:000980903000095

Open via DOI