Introduction

The European Community social legislation is meant to improve road safety and to ensure a fair competition between road transport operators in Europe. The Regulation rules (EC) 561/2006 [1] and directive 2002/15/EC makes the transport companies legally responsible if schedules do not let time for drivers for compulsory break and rest periods. This set of rules imposes restrictions on the daily driving time, daily working time, as well as the scheduling of several types of breaks along the shift and the week. As a result, the complexity of the problem increases, and even finding a feasible solution when it exists, rises the computational effort [2]. Additionally, no polynomial-time algorithm is known for route evaluations subject to the European Union regulations [3]. Since the Truck Driver Scheduling Problem (TDSP) is a subproblem of the combined vehicle routing and truck driver scheduling problems, it is important to develop efficient methods that could find feasible or optimal schedules for a given tour sent by the routing search procedure.

Different dynamic programming models have been proposed for the TDSP, some considering mainly rules on driving time [2][4] and comparing results against optimal solutions provided by linear models. There are others, which include more rules from the social legislation [5][6][7], but they solve the TDSP using label setting heuristic approaches. A label setting algorithm is presented, which in contrast with previous label setting algorithms that include the same set of rules from the social legislation, its results are compared against a MILP model, achieving optimality for all the instances in a competitive computational time. Detail solutions are available at https://perso.isima.fr/~igpenaar/Roadef_2022/.

Label setting algorithm

A label setting algorithm is proposed to schedule driver's shifts under the European Union regulations considering pre-emption assumptions. The method considers a sequence of customers that starts and ends at the depot, each of them has time windows and two activities: service and driving, where a given activity could have a duration of zero units of time. The objective is to find the optimal schedule of breaks/rests complying with the European Union regulation, which minimizes the completion time of the sequence.

The algorithm starts with the service activity at the depot, using an initial solution set to 0 . At each activity , it determines a set of feasible solutions or labels with a minimum completion time. Each extension of a label has two components, the size of the process p, and the type of break b, in this order. The size of the process p is the maximum process time that could be developed until a rule is broken or an activity is finished; after the process time, all the types of break from the set are explored. At each extension, the possibility of waiting time or rest extension, whether the sequence is in the middle or at the beginning of a shift, is also considered. Figure 1 presents the description of the extension.

Figure 1. Extension process.

Depending on the status of the activity in process or finished , the algorithm will store the new extensions at their respective node. During the extension process, every new label goes through a feasibility test. A feasible solution should satisfy the European Union Regulation for Truck Drivers. Only non-dominated solutions should be considered, therefore, after verifying their feasibility, a dominance procedure that compares two labels , determines if label dominates label . The comparison of the attributes is done one by one over the set of labels at the current node . The complete process repeats until it reaches the depot at the end of the sequence.

Conclusion

This work presents a label setting algorithm under pre-emption assumptions for the truck driver-scheduling problem considering the EC social legislation, which achieves optimality over a set of instances in an efficient computational time. Results show that the average computational time to solve instances up to 32 activities is about 509.8 ms, and it is 9 times faster than its counterpart the MILP model. Therefore, the model could be used in a combined vehicle routing and truck driver scheduling problem arising in many real-life applications.

References

[1] European Union. 2006. Regulation (EC) No. 561/2006 of the European Parliament and of the Council of 15 March 2006 on the harmonisation of certain social legislation relating to road transport and amending Council Regulations (EEC) 3821/85 and (EC) 2135/98 and repealing Council Regulation (EEC) 3820/85. Official Journal of the European Union L 102, 11.04.2006.

[2] Goel, A. “The minimum duration truck driver scheduling problem”, EURO Journal on Transportation and Logistics. Vol. 1, pp. 285–306, 2012.

[3] Tilk, C. and Goel, A. “Bidirectional labeling for solving vehicle routing and truck driver scheduling problems”, Eur. J. Oper. Res., vol. 283, pp. 108–124, 2020.

[4] Goel, A. “Truck driver scheduling in the European Union”. Transportation Science. vol. 44, no. 4, pp. 429–441, 2010.

[5] Kok, A.L., Hans, E.W., Schutten, J.M.J. “Optimizing departure times in vehicle routes”, European Journal of Operations Research. vol. 210, no. 3, pp. 579–587, 2011.

[6] Goel, A. and Irnich, S., “An exact method for vehicle routing and truck driver scheduling problem”, Transport. Sci., vol.51, no. 2, pp. 737–754, 2016.

[7] Tilk, C. and Goel, A. “Bidirectional labeling for solving vehicle routing and truck driver scheduling problems”, Eur. J. Oper. Res., vol. 283, pp. 108–124, 2020.