A branch-and-price method for the vehicle allocation problem. (November 2020)

• Record Type: Journal Article
• Authors: Cruz, Cesar Alvarez; Munari, Pedro; Morabito, Reinaldo
• Is Part Of: Computers & industrial engineering. Volume 149(2020)
• Publication Date: 2020-11
• Subjects: Vehicle allocation problem -- Dantzig–Wolfe decomposition -- Branch-and-price -- Freight road transportation -- Logistics; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106745
• Languages: English
• ISSNs: 0360-8352

Abstract

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. Highlights: We study a vehicle allocation problem in the context of freight road transportation. The problem consists of allocating empty vehicles to different terminals. This paper contributes with a tailored exact solution method. It is a branch-and-price method based on the Dantzig–Wolfe decomposition. The results show that the method improves previous results for realistic instances.