Artur Alves Pessoa – Optimization Online

A heuristic framework for a class of vehicle routing problems

Published: 2026/10/23

Combinatorial Optimization, Meta Heuristics, Transportation column generation, metaheuristics, resource extension functions, routing

We propose GenericILS, a general-purpose heuristic framework for generating high-quality upper bounds for Vehicle Routing Problems whose pricing subproblems are modeled, in column-generation-based exact algorithms, as resource-constrained shortest path problems described through Resource Extension Functions (REFs), the standard device for encoding constraints in branch-and-price algorithms. GenericILS reuses REFs implemented for the exact method, without a … Read more

Hybrid iterated local search algorithm for the vehicle routing problem with lockers

Published: 2024/09/24

Combinatorial Optimization, Integer Programming, Meta Heuristics Hybrid algorithm, iterated local search, last mile logistics, vehicle routing

In the Vehicle Routing Problem (VRP) with Lockers, the vertices in a graph are divided into two key subsets: a customer set and a locker set, with lockers serving as alternative delivery points for the customer’s parcel. This paper presents a generic VRP with lockers, where a customer’s parcel can be delivered either to its … Read more

Optimizing with Column Generation: Advanced Branch-Cut-and-Price Algorithms (Part I)

Published: 2024/08/30, Updated: 2025/03/13

Cutting Plane Approaches, Integer Programming

We are excited to present the early release of Part I of our book “Optimizing with Column Generation: advanced Branch-Cut-and-Price Algorithms”. While the book’s ultimate goal, as suggested by its subtitle, is to describe cutting-edge techniques in these algorithms, this objective is primarily addressed in the forthcoming Part II. However, we feel that the completed … Read more

New cuts and a branch-cut-and-price model for the Multi Vehicle Covering Tour Problem

Published: 2024/04/16

Combinatorial Optimization, Cutting Plane Approaches, Integer Programming branch-cut-and-price, combinatorial optimization, covering, cutting inequalities, vehicle routing problem

The Multi-Vehicle Covering Tour Problem (m-CTP) involves a graph in which the set of vertices is partitioned into a depot and three distinct subsets representing customers, mandatory facilities, and optional facilities. Each customer is linked to a specific subset of optional facilities that define its coverage set. The goal is to determine a set of … Read more

A new family of route formulations for split delivery vehicle routing problems

Published: 2022/05/13, Updated: 2023/05/31

Combinatorial Optimization, Integer Programming, Transportation branch-cut-and-price, non-robust cuts, split-delivery, time windows, vehicle routing

We propose a new family of formulations with route-based variables for the split delivery vehicle routing problem with and without time windows. Each formulation in this family is characterized by the maximum number of different demand quantities that can be delivered to a customer during a vehicle visit. As opposed to previous formulations in the … Read more

A Generic Exact Solver for Vehicle Routing and Related Problems

Published: 2019/06/04

(Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems column generation, integer programming, routing

Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This … Read more

Branch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty

Published: 2018/09/11

Branch and Cut Algorithms, Robust Optimization

We examine the robust counterpart of the classical Capacitated Vehicle Routing Problem (CVRP). We consider two types of uncertainty sets for the customer demands: the classical budget polytope introduced by Bertsimas and Sim (2003), and a partitioned budget polytope proposed by Gounaris et al. (2013). We show that using the set-partitioning formulation it is possible … Read more

A Bucket Graph Based Labeling Algorithm with Application to Vehicle Routing

Published: 2017/10/18

Combinatorial Optimization, Dynamic Programming, Integer Programming

We consider the Resource Constrained Shortest Path problem arising as a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for vehicle routing problems. We propose a variant of the bi-directional label correcting algorithm in which the labels are stored and extended according to so-called bucket graph. Such organization of labels helps to decrease significantly the number of dominance … Read more

Robust network design with uncertain outsourcing cost

Published: 2014/11/27

Robust Optimization

The expansion of a telecommunications network faces two sources of uncertainty, which are the demand for traffic that shall transit through the expanded network and the outsourcing cost that the network operator will have to pay to handle the traffic that exceeds the capacity of its network. The latter is determined by the future cost … Read more

Robust constrained shortest path problems under budgeted uncertainty

Published: 2014/10/15

Combinatorial Optimization, Robust Optimization budgeted uncertainty, constrained shortest path, dynamic programming, np-hard, robust optimization

We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is \NPhard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the … Read more