A Branch-and-Price Algorithm for the Mixed Capacitated Arc Routing Problem with Intermediate Facilities

Speaker: Juan Sebastian Riveros Perez

July 28^th, 2026 | 11:00 am
DEIB, PT2 Meeting Room  (Bld. 20A)

Contact:  Prof. Ola Jabali 

Abstract

On July 28^th, 2026, at 11:00 am the seminar on "A Branch-and-Price Algorithm for the Mixed Capacitated Arc Routing Problem with Intermediate Facilities" will take place in DEIB PT2 Meeting Room (Building 20A).

Residential waste collection is naturally modeled as an arc routing problem in which service is performed along streets. This work studies the Mixed Capacitated Arc Routing Problem with Intermediate Facilities. We propose the first Branch-and-Price algorithm for this problem, based on a set-covering reformulation that exploits the sparsity of arc routing networks and tailored pricing subproblems. The closest existing exact approach reformulates the problem as a node routing problem and applies only to the undirected case. Computational experiments assess the two approaches and compare their performance.

Short Bio

Juan Sebastian Riveros Perez is a Ph.D. student in Logistics and Operations Management at HEC Montréal, supervised by Jorge E. Mendoza and Jean-François Cordeau. His research focuses on exact and heuristic methods for complex arc routing problems arising in urban services, with a particular emphasis on municipal waste collection. Before joining HEC Montréal, he completed his bachelor’s and master’s degrees in Industrial Engineering at Universidad de los Andes in Bogotá, Colombia.