Fuzzy vehicle scheduling problem

Vehicle scheduling problem is an important combinatorial optimization problem arising in the management of transportation companies. It consists in assigning a set of timetabled trips to a set of vehicles so as to minimize a given objective function and efficiency use of the resources. In this paper, vehicle scheduling problem under undeterministic conditions is considered. The problem is formulated as a credibility-based fuzzy integer multicommodity flow problem. An approach based on the combination of branch-and-price and heuristic algorithms is used to generate vehicle schedules. The heuristic algorithms are applied to accelerate branch-and-price algorithm. Two sets of benchmark examples are considered to demonstrate the applicability of the proposed algorithm in the large-scale instances. The results show that, the proposed method generates vehicle schedules with different decision maker's satisfaction degrees. The algorithm is applied to solve classical multi-depot vehicle scheduling problem as well. In this case, the results show that the proposed algorithm improves the integrality gap in comparison with the state-of-the-art algorithms. Also the proposed 〖B&P〗_H algorithm decreases the computational time in comparison with the normal branch-and-price algorithm. Finally, the approach is used to generate bus schedules in Tehran BRT network. Computational results show that the proposed method generates bus schedules with the minimum number of delayed trips.