In the recent years new regulations on driving and working hours of truck drivers entered into force in the U.S., Canada, Australia and the European Union. Neglecting regulatory constraints when scheduling driving and working hours of drivers may lead to infringements and/or delayed arrival times due to required break and rest periods which have not been scheduled. This results in low customer satisfaction and/or high risk of fatigue related accidents. Consequently, road transport undertakings must ensure that truck driver schedules comply with respective regulations when generating vehicle routes. Scheduling driving and working hours of truck drivers is a difficult task if service times are constrained. In this research we develop analytical models fully describing regulatory constraints in the U.S. and the European Union. Furthermore, we develop algorithmic methods allowing for an automatic generation of truck driver schedules complying with the regulations.