A Label Setting Algorithm for the Truck Driver Scheduling Problem considering the European Community Social Legislation
Authors : T. Garaix, P. Lacomme, I. Peña-Arenas and N. Tchernev
This is the companion web page of the paper submitted to the Expert Systems with Applications.
We used two original sets of instances in this section. The set named GOEL corresponds to the 157 routes - visiting from four to nineteen customers - obtained from solutions of the Vehicle Routing and Truck Driver Scheduling Problem solved by Goel (2018). We also used the set PGLT of 40 instances, with two to fourteen customers proposed in Peña-Arenas et al. (2021). The creation of this second set was motivated by the application of all the EU rules. Thus, some instances are unfeasible. In all these instances every customer corresponds to one service activity (other work). One driving activity separates two consecutive customers. The sequence of activities starts and ends by some service activities at the depot.
In GOEL instances all values are in minutes. We derived three sets of instances with different rounding values, 1 (the original ones), 5 and 15 minutes. The rounding procedure lets the solutions of Goel (2018) feasible and they are computed as the lower multiple for all values, except the latest service time that is rounded to the greater multiple. In PGLT all data are multiples of 15 min. except in instance 29. For a sake of clarity, the new set of instances are denoted RX-GOEL or RX-PGLT, where X is the rounding value.
All the experiments have been achieved on a single processor of an Intel® Core™i5-8400 at 2.81 GHz under Windows 10, using C++ and Gurobi 8.1.1. In this web page you find all instances and results. A limit on the computation time has been imposed after 15 minutes.
Example of an instance:
Each file contains:
• The name of the instance.
• Number of clients.
• Travel time to the next client.
• Service time of the client.
• Earliest starting time of the service.
• Latest starting time of the service.
Figure 1. Example Instance 8.
Instances
Instance |
Rounding 5min. |
Rounding 15min. |
|---|---|---|
PGLT |
||
GOEL |
Table 1. Set of instances PGLT and GOEL for the TDS.
Instances GOEL
The following set of original instances come from the solutions obtained by Goel[1] for the Truck Drivers Scheduling Problem.
7.1 MILP performance
Results of the MILP model on R15-GOEL instances, using 1 to 3 nodes per activity and a tight number of nodes (TN). The statistics are computed over 140 instances where the time limit was not reached.
Number of nodes |
Results (per instance) |
Aggregated |
|---|---|---|
1 |
||
2 |
||
3 |
||
TN |
Table 2. MILP performance according to the number of nodes per activity on R15-GOEL.
Nodes per instance
Number of nodes per instance used in the setting TN on R15-GOEL.
Nodes per Instance - R15-GOEL.
Extra material Table 9 (Page 25)
MILP performance according to the number of nodes per activity on R15-GOEL.
7.2 Label Setting performance
Table 3 shows the running times of the LS-15 and LS-5 on instances R15-PGLT and R15-GOEL. The statistics are computed over the instances where the maximum running time was not reached. Note that under this setting both algorithms are optimal.
δ |
Instance |
Results (per instance) |
Aggregated |
|---|---|---|---|
5min. |
R15-PGLT |
||
5min. |
R15-GOEL |
15min. |
R15-PGLT |
15min. |
R15-GOEL |
Table 3. Effect of the time step δ on the LS running times using instances R15-PGLT and R15-GOEL.
Extra material Table 10 (Page 26)
Effect of the time step δ on the LS running times using instances R15-PGLT and R15-GOEL.
Table 4 presents the running times and the GAP of the LS-5 and LS-15 using the set of instances rounded to 5 minutes. The statistics are computed over the instances where the maximum running time was not reached.
δ |
Instance |
Results (per instance) |
Aggregated |
|---|---|---|---|
5min. |
R5-PGLT |
||
5min. |
R5-GOEL |
15min. |
R5-PGLT |
15min. |
R5-GOEL |
Table 4. Results LS using δ=15min and δ=5min on the set of instances R5-PGLT and R5-GOEL.
Extra material Table 11 (Page 27)
Results LS using δ=15min and δ=5min on the set of instances R5-PGLT and R5-GOEL.
Extra material Table 12 (Page 27)
Comparison completion time of LS-5 on the set of instances PGLT and GOEL rounded to 15 and 5 minutes.
Extra material Table 13 (Page 28)
Running times MILP-TN and LS-15 on the set of instances R15-PGLT and R15-GOEL.
Results per instance MILP-TN on R15-PGLT instances.
Aggregated results MILP-TN - R15-PGLT.
Nodes per instance
Number of nodes per instance used in the setting TN on R15-PGLT.
Nodes per Instances - R15-PGLT.
7.3 Night working rule effect on the schedules
Table 5 presents the results for the LS using δ=15min is modified to work under three assumptions: No-Night, FNW and EURULE. The comparison is done using the set of instances R15-PGLT. the statistics are computed over the set of feasible instances found by the LS-15 under FNW, which is the most constrained assumption for the night.
Night rule |
Results (per instance) |
Aggregated |
|---|---|---|
No-Night |
||
FNW |
||
EURULE |
Table 5. Night effect on the LS performance and the quality of the solutions over R15-PGLT instances.
Extra material Table 14 (Page 28)
Night effect on the LS performance and the quality of the solutions over R15-PGLT instances.
MILP source code
C++ code for the MILP model.
©2023