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

Abstract

This paper aims at presenting the multiple depot vehicle scheduling problem with heterogeneous fleet and 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.