A mi tambien me pasaba y era un problema de configuración.
Vete a ajustes-aplicaciones-administrar aplicaciones y busca waze. Una vez que dentro de ella, comprueba que este activado el inicio automatico y que en ahorro de batería este sin restricciones.
Ami así me funciona