A branch-and-price method for the vehicle allocation problem

Author(s)

Cruz, Cesar Alvarez ^[1] ; Munari, Pedro ^[1] ; Morabito, Reinaldo ^[1]

Affiliation

^[1] Univ Fed Sao Carlos, Prod Engn Dept, Rodovia Washington Luis Km 235, BR-13565905 Sao Carlos, SP - Brazil

• Document type: Journal article
• Source: COMPUTERS & INDUSTRIAL ENGINEERING; v. 149, NOV 2020.
• Web of Science Citations: 0

Abstract

The Vehicle Allocation Problem (VAP) consists of allocating a fleet of vehicles to attend to the expected demand for freight transportation between terminals along a finite multiperiod planning horizon. The objective is to maximize the profits generated for the completed services. The previous deterministic and stochastic approaches used heuristic procedures and approximations for solving large-scale instances of this problem. This paper proposes a Branch-and-Price method which is the first tailored exact solution approach for the VAP. This method provides proven optimal solutions within reasonable computational times, even for large-scale problem instances, and it is based on reformulating a compact Integer Linear Programming model of the VAP through the Dantzig-Wolfe decomposition and using efficient procedures for solving each component of the reformulation. The Primal-Dual Column Generation Method (PDCGM) is used to solve the master problem, while the subproblem is modeled as a Maximum Cost Flow Problem and is solved using the aggregation of the optimal longest paths on Directed Acyclic Graphs (DAG). Finally, we use three branching procedures (branching on a set of arcs, on the original variables and on the demand constraints) to obtain the optimal integer solution of the VAP. Computational experiments with 30 instances from a case study and 200 random realistic-sized instances are presented and analyzed, which show that the method has superior performance with respect to other exact approaches in solving large-scale VAP instances. (AU)

• 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
• FAPESP's process: 16/23366-9 - Models and solution methods for variants of the inventory routing problem
• Grantee: Pedro Augusto Munari Junior
• Support Opportunities: Regular Research Grants