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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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

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

OriginalspracheEnglisch
Seiten (von - bis)1455-1478
Seitenumfang24
FachzeitschriftTransportation Science
Jahrgang53
Ausgabenummer5
PublikationsstatusVeröffentlicht - 2019
Peer-Review-StatusJa
Extern publiziertJa

Externe IDs

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

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

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