Optimization models and solution methods for the vehicle allocation problem

Abstract

The Vehicle Allocation Problem (VAP) consists in allocating a fleet of vehicles to attend the expected demand for road freight transportation between terminals along a finite multiperiod planning horizon. The objective is to maximize the profits generated for the completed services. Previous deterministic and stochastic approaches used heuristic procedures and approximation methods for solving large scale instances of this problem. This thesis contributes with models and solution methods for solving effectively large-scale instances of the VAP. The first method is Branch-and-Benders-Cut (BBC) for solving the space-time network formulation of the VAP. The Benders reformulation results in each subproblem being a multiple origin-destination minimum cost flow problem among empty vehicles exclusively. We propose two valid inequalities in order to reduce the number of infeasible cuts needed to reach a feasible and optimal solution. In addition, we use network flow algorithms in trying to accelerate the process of cut generation. Computational results are shown for randomly generated instances. The second method is a tailored exact Branch-and-Price (BP) procedure, that provides optimal solutions or certificates of quality, for solving large-scale problems within reasonable computational times. This method is the result of reformulating a compact Integer Linear Programming model of the VAP through the Dantzig-Wolfe (DW) 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 solved using the aggregation of optimal longest paths problems on Directed Acyclic Graphs (DAG). Finally, we resort to three branching procedures to obtain the optimal integer solution of the VAP. Computational experiments with instances from a case study and random realistic-sized instances are presented and analyzed, showing that the method has a superior performance with respect to other exact approaches in solving large-scale VAP instances. The third method is based on preprocessing the time-space extended graph and reformulating the problem in terms of routing empty vehicles along demand nodes. The resulting model's size depends on the number of demand nodes (arcs in the previous model) and fleet size, which can be advantageous when the number of terminal-period pairs in the time-space extended network is large compared to the actual number of loads requested. We propose a BP method based on the DW reformulation of this new modelling approach. The results of both, the reformulation solved by CPLEX and the BP, shows the superior performance of this new approach in solving realistic-sized instances of the VAP.