Advanced search
Start date

The vehicle allocation problem: Alternative formulation and branch-and-price method

Full text
Cruz, Cesar Alvarez ; Costa, Alysson M. ; Munari, Pedro ; Morabito, Reinaldo
Total Authors: 4
Document type: Journal article
Source: Computers & Operations Research; v. 144, p. 18-pg., 2022-08-01.

The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles across a set of terminals over a given planning horizon so as to maximize the profits generated from serving demand for transportation of goods between pair of terminals. This problem has been classically modeled using an extended space-time network which captures the staging of the decision-making process. The present paper proposes a new integer linear programming (ILP) model based on the idea of representing the demands to be met as nodes on a graph. We also derive a Dantzig-Wolfe reformulation which is solved with a branch-and-price (BP) method. The proposed BP uses a stabilized interior-point column generation approach and a branching procedure that imposes constraints in the master problem, thus not damaging the structure of the subproblems. Additionally, we show that these subproblems can be solved efficiently using a shortest path algorithm on directed acyclic graphs (DAG). Computational experiments are carried out on realistic-sized benchmark instances commonly used in the literature. The results show the efficacy of the proposed strategies. In particular, the BP method solved the whole set of instances to proven optimality for the first time and in faster competitive times. (AU)

FAPESP's process: 19/22235-6 - Aircraft routing under uncertainty via robust optimization
Grantee:Rafael Ajudarte de Campos
Support Opportunities: Scholarships in Brazil - Master
FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
Grantee:Reinaldo Morabito Neto
Support Opportunities: Research Projects - Thematic Grants