An Assignment Model for Scheduling Vehicles with Refueling

Abstract

The vehicle scheduling problem consists of scheduling a fleet of vehicles to cover a set of tasks at a minimum cost. The tasks are given in predetermined time intervals, and the vehicles are supplied by different depots. There are several known mathematical models that can be used to solve this problem, resulting in a valid vehicle schedule. One such approach is the multi-commodity network flow model, where the optimal schedule is computed by solving a linear integer programming problem. The main disadvantage of this model is that it can be intractable for practical scenarios that include additional vehicle constraints. These are specific restrictions that come from real-world applications, such as the refueling requirement of vehicles. When vehicles of different fuel types, including environmentally friendly ones, are considered, decisions about their refueling include many additional constraints that a valid assignment must meet. This paper presents how these vehicle-specific tasks can be included in the vehicle assignment phase. An IP-based heuristic solution is given for this specific variant of the vehicle assignment with multiple depots. Computational results on real-life and randomly generated test instances are presented where the vehicle assignment model uses an input schedule generated by the time-space network approach. The resulting integer programming problem for this assignment can be solved extremely quickly, even with a large number of variables. Computational results demonstrate that the model can effectively extend the capabilities of the standard models to be able to handle the assignment with vehicle-specific task requirements.