Skip to main content
Kent Academic Repository

Solving the hierarchical windy postman problem with variable service costs using a math-heuristic algorithm

Keskin, Muhammed Emre, Yılmaz, Mustafa, Triki, Chefi (2023) Solving the hierarchical windy postman problem with variable service costs using a math-heuristic algorithm. Soft Computing, 27 (13). pp. 8789-8805. ISSN 1432-7643. E-ISSN 1433-7479. (doi:10.1007/s00500-023-08032-z) (KAR id:100835)

PDF Publisher pdf
Language: English


Download this file
(PDF/727kB)
[thumbnail of C. Triki - solving the hierarchical windy postman problem - PPDF.pdf]
Preview
Request a format suitable for use with assistive technology e.g. a screenreader
PDF Author's Accepted Manuscript
Language: English

Restricted to Repository staff only
Contact us about this Publication
[thumbnail of C. Triki - solving the hierarchical windy postman problem - AAM.pdf]
Official URL:
https://doi.org/10.1007/s00500-023-08032-z

Abstract

The Hierarchical Windy Postman Problem (HWPP) is an arc routing problem in which an order relation is imposed on the arcs/edges of the graph, and one has to pass through each edge at least once while adhering to the hierarchical priority relations. The tour starts from and ends at a specific node and the aim is to minimize the length of the tour. We consider a variant of the HWPP in which (i) the precedence order of the edge hierarchies is linear and edges within each hierarchy are connected and (ii) the cost of serving each edge decreases with the number of times it is traversed, and we refer to it as HWPP with variable service costs. An integer non-heuristic linear mathematical formulation is proposed, and a solution approach is designed. Our solution heuristic adapts the layer algorithm of Dror et al. (Networks 17:283–294, 1987) but employs an integer mathematical formulation as a sub-procedure instead of the blossom algorithm to find the least cost path between the nodes of the graph. This choice is based on the fact that the blossom algorithm requires a symmetric cost structure while we deal here with the general case of asymmetric cost structure, which makes our problem a windy variant of the postman problem. It should be noted that our problem is not asymmetric in the sense that there are no opposite arcs with different costs but there are edges which have different costs depending on the traversal direction. In order to compare the performance of our heuristic algorithm with respect to the performance of the mathematical model that is solved by the commercial solver Gurobi, 84 test instances are generated having varying sizes and densities and with different number of hierarchies. These test instances are solved by both methods and the generated results show that the proposed heuristic method is much faster and generates better quality solutions.

Item Type: Article
DOI/Identification number: 10.1007/s00500-023-08032-z
Uncontrolled keywords: Routing, Hierarchical windy postman problem, Variable service cost, Windy layer algorithm
Subjects: H Social Sciences > HF Commerce > HF5351 Business
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Funders: University of Kent (https://ror.org/00xkeyj56)
Depositing User: Chefi Triki
Date Deposited: 11 Apr 2023 08:54 UTC
Last Modified: 19 Jan 2024 11:25 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/100835 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.