The vehicle allocation problem: Alternative formulation and branch-and-price method. (August 2022)

• Record Type: Journal Article
• Authors: Cruz, Cesar Alvarez; Costa, Alysson M.; Munari, Pedro; Morabito, Reinaldo
• Is Part Of: Computers & operations research. Volume 144(2022)
• Publication Date: 2022-08
• Subjects: Vehicle allocation problem -- Dantzig–Wolfe decomposition -- Branch-and-price -- Empty repositioning -- Logistics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105784
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: We study a problem of repositioning empty vehicles across a set of terminals. We propose a new integer linear programming formulation for this problem. We also propose an effective branch-and-price method to optimally solve the problem. Computational results are carried out on realistic-sized benchmark instances. The method solved the whole set of instances to proven optimality for the first time.