Modeling and Solving the Intersection Inspection Rural Postman Problem

Debdatta Sinha Roy (), Adriano Masone (), Bruce Golden () and Edward Wasil ()
Additional contact information
Debdatta Sinha Roy: Staples Inc., Framingham, Massachusetts 01702
Adriano Masone: Department of Electrical Engineering and Information Technology, University of Naples Federico II, 80125 Napoli, Italy
Bruce Golden: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742
Edward Wasil: Kogod School of Business, American University, Washington, District of Columbia 20016

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 1245-1257

Abstract: Local governments inspect roads to decide which segments and intersections to repair. Videos are taken using a camera mounted on a vehicle. The vehicle taking the videos proceeds straight or takes a left turn to cover an intersection fully. We introduce the intersection inspection rural postman problem (IIRPP), which is a new variant of the rural postman problem (RPP) that involves turns. We develop integer programming formulations of the IIRPP based on two different graph transformations to generate least-cost vehicle routes. One formulation is based on a new idea of transforming a graph. A second formulation is based on a graph transformation idea from the literature. Computational experiments show that the formulation involving the new graph transformation idea performs much better than the other formulation. We also develop an RPP-based heuristic and a heuristic based on a modified RPP. Heuristic solutions are improved by solving integer programming formulations on an induced subgraph. Computational experiments show that the heuristics based on the modified RPP perform much better than the RPP-based heuristics. The best-performing heuristic generates very good quality IIRPP-feasible routes on large street networks quickly. Summary of Contribution. Our paper addresses a real-world problem faced by local governments during road inspections. The real-world problem that we solve and the methodologies that we use fall at the intersection of computing and operations research. We introduce the intersection inspection rural postman problem, which is a new variant of the rural postman problem that involves turns to capture this real-world scenario. The rural postman problem is an important problem in vehicle routing. Studying new variants of this problem is key to extending the practice and theory of vehicle routing. We develop an integer programming formulation based on a new idea of transforming a graph and also develop heuristics based on the rural postman problem.

Keywords: rural postman problem; node routing; arc routing; integer programming; heuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1013 (application/pdf)

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:inm:orijoc:v:33:y:2021:i:3:p:1245-1257

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().