A Branch-and-Price Algorithm for the Bilevel Network Maintenance Scheduling Problem

David Rey (), Hillel Bar-Gera (), Vinayak V. Dixit () and S. Travis Waller ()
Additional contact information
David Rey: School of Civil and Environmental Engineering, UNSW Sydney, New South Wales 2052, Australia;
Hillel Bar-Gera: Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel;
Vinayak V. Dixit: School of Civil and Environmental Engineering, UNSW Sydney, New South Wales 2052, Australia;
S. Travis Waller: School of Civil and Environmental Engineering, UNSW Sydney, New South Wales 2052, Australia;

Transportation Science, 2019, vol. 53, issue 5, 1455-1478

Abstract: We address the network maintenance scheduling problem, which consists of finding the optimal schedule for the coordination of road maintenance projects in a transport network over a planning period. Road works and maintenance operations that require partial or total road closures over a period of time may considerably impact network performance and result in significant delays. In addition, the effects of conducting multiple maintenance projects simultaneously may be nonadditive, hence increasing the difficulty to anticipate congestion effects. In this paper, we propose a new bilevel mixed integer programming formulation for the network maintenance scheduling problem, which relies on the enumeration of maintenance project combinations—patterns—to incorporate congestion effects within the scheduling process. We present a new branch-and-price algorithm that relies on customized branching and bounding rules, and a tailored column generation framework to price patterns. In addition, a statistical regression model is introduced to approximate congestion effects and provide approximate lower bounds on the formulations therein. The proposed branch-and-price algorithm is implemented on instances derived from realistic transport networks and is shown to be able to solve the network maintenance scheduling problem in a reasonable time using only a fraction of the patterns.

Keywords: bilevel optimization; branch and price; column generation; mixed integer programming; network maintenance; scheduling; traffic assignment (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0896 (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:ortrsc:v:53:y:2019:i:5:p:1455-1478

Access Statistics for this article

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