A branch-and-bound algorithm for the time-Dependent rural postman problem. (February 2019)

• Record Type: Journal Article
• Authors: Calogiuri, Tobia; Ghiani, Gianpaolo; Guerriero, Emanuela; Mansini, Renata
• Is Part Of: Computers & operations research. Volume 102(2019)
• Page Start: 150
• Page End: 157
• Publication Date: 2019-02
• Subjects: Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.07.016
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A branch-and-bound algorithm for solving the time-dependent rural postman problem. A procedure to compute lower and upper bounds on the optimal solution value. Computational experiments show that the algorithm can successfully solve some instances with up to 60 required arcs. Abstract: This paper deals with the time-dependent version of the classical Rural Postman Problem in which arc traversal times vary along the planning horizon. The relationship with the time-invariant counterpart is investigated and a branch-and-bound algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported.