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

Autor(es)

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

Afiliação do(s) autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 149, NOV 2020.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/23366-9 - Modelos e métodos de solução para variantes do problema de roteamento de estoques
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular