Optimization Online


A Branch-and-Benders-Cut Algorithm for the Road Restoration Crew Scheduling and Routing Problem

Alfredo Moreno(alfredmorenoarteaga***at***gmail.com )
Pedro Munari(munari***at***dep.ufscar.br)
Douglas Alem(douglas***at***ufscar.br)

Abstract: Extreme events such as disasters cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers or affected areas. The road restoration crew scheduling and routing problem (RRCSRP) addresses decisions in post-disaster situations with the aim of minimizing the time that affected areas remain inaccessible. The integration of crew scheduling and routing decisions makes this problem too complicated to be effectively solved for practical instances using mixed integer programming (MIP) formulations recently proposed in the literature. Therefore, we propose a branch-and-Benders-cut (BBC) algorithm that decomposes the integrated problem into a master problem (MP) with scheduling decisions and subproblems with routing decisions. Computational tests based on instances from the literature show that the proposed exact method improves the results of MIP formulations and other exact and metaheuristic methods proposed in literature. The BBC algorithm provides feasible solutions and optimality gaps for instances that thus far have not been possible to solve by exact methods in the literature.

Keywords: Combinatorial optimization, Benders decomposition, Branch-and-cut, Crew scheduling and routing, Road restoration

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Report number 001/2018, Operations Research Group, Production Engineering Department, Federal University of Sao Carlos, Brazil

Download: [PDF]

Entry Submitted: 01/19/2018
Entry Accepted: 01/19/2018
Entry Last Modified: 01/19/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society