Variable fixing mip heuristics for solving multiple depot vehicle scheduling problem with heterogeneous fleet and time windows

Abstract

The multiple depot heterogeneous fleet vehicle scheduling problem (MDHFVSP) consists of allocating vehicles for predetermined trips groups, taking into account multiple depots, the capacity of these depots, different types of vehicles as well as trips of various demands and vehicles with different capacities. The main objective of a transportation system planning is to reduce costs, implementation and/or operation costs, reducing vehicle utilization and minimizing fuel and crew costs. This thesis proposes a new variant of the MDHFVSP that considers the application of time windows (MDHFVSP-TW). We used a time-space network (TSN) to perform the modeling of MDHFVSP-TW, along with two methodologies to reduce its size and, therefore, its complexity. Along with size reduction methods, a mixed integer programming (MIP) heuristic with variable fixation was presented. Its operation is based on the use of the solution for this problem with relaxed variables as a basis for the removal of arcs from the problem, reducing its size and enabling its resolution in reasonable computational time. Extensive tests were performed for a collection of randomly generated instances. Subsequently, a case study arising from a real instance from a Brazilian city is presented. The computational results showed that the proposed heuristic and size reduction methods obtained good performance, providing high-quality solutions in an adequate computational time.