A branch-and-price algorithm for the bilevel network maintenance scheduling problem

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • David Rey - , University of New South Wales (Author)
  • Hillel Bar-Gera - , Ben-Gurion University of the Negev (Author)
  • Vinayak V. Dixit - , University of New South Wales (Author)
  • S. Travis Waller - , University of New South Wales (Author)

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-andprice 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.

Details

Original languageEnglish
Pages (from-to)1455-1478
Number of pages24
JournalTransportation Science
Volume53
Issue number5
Publication statusPublished - 2019
Peer-reviewedYes
Externally publishedYes

External IDs

ORCID /0000-0002-2939-2090/work/141543713

Keywords

Keywords

  • Bilevel optimization, Branch and price, Column generation, Mixed integer programming, Network maintenance, Scheduling, Traffic assignment