A time-dependent hierarchical Chinese postman problem

Merve Kayacı Çodur () and Mustafa Yılmaz ()
Additional contact information
Merve Kayacı Çodur: Atatürk University
Mustafa Yılmaz: Atatürk University

Central European Journal of Operations Research, 2020, vol. 28, issue 1, No 17, 337-366

Abstract: Abstract The hierarchical Chinese postman problem (HCPP), a variant of the Chinese postman problem, is an arc routing problem. HCPP is NP-hard and several methods have been developed to solve this problem. Many studies in the literature have taken the minimum distance covered between nodes into consideration. All of these studies ignore time-dependent travel speeds between two locations. Travel speeds (and time) in almost all metropolitan areas change drastically during the day due to a variety of different factors, such as weather condition, peak traffic hours and accidents, along with the distance. Spending minimum time to travel streets is of great importance to ensure traffic flow and road safety, particularly in many practical implementation areas of HCPP, such as snow plowing winter, garbage collection and routing security patrol vehicles. This study introduces a new problem called the time-dependent hierarchical Chinese postman problem that aims to minimize the total travel time, while obeying precedence relationships between edges. This problem differs from most arc routing problems because the duration of traversing a street changes depending on the time of day. The problem was formulated as a mixed integer linear programme. Two metaheuristics were built: a genetic algorithm (GA) and a hybrid simulated annealing (hSA). The proposed model and metaheuristics were tested on modified benchmark instances and randomly generated problem instances with as many as 490 edges. The performance of GA and hSA were compared in terms of solution quality and computational time.

Keywords: Arc routing problems; Hierarchical Chinese postman problem; Time dependent routing; Genetic algorithm; Simulated annealing (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-018-0598-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:28:y:2020:i:1:d:10.1007_s10100-018-0598-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-018-0598-8

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().