| A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem (2007) | |||||||||||||||
Abstract | |||||||||||||||
| The Vehicle Scheduling Problem is an important combinatorial optimization problem arising in the management of transportation companies. It consists in assigning a set of time-tabled trips to a set of vehicles so as to minimize a given objective function. In particular, we consider the Multiple Depot version of the problem (MDVSP) , in which one also has to assign vehicles to depots. This problem is known to be NP-hard. In this paper we introduce two main classes of valid inequalities for MD-VSP, and propose efficient separation algorithms along with effective heuristic strategies to speed up cutting-plane convergence. These results are used within a branch-and-cut scheme for the exact solution of the problem. The method uses a new branching strategy based on the concept of "fractionality persistency", a completely general criterion that can be extended to other combinatorial problems. The performance of the branch-and-cut scheme is evaluated through extensive computational ... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||