But it does get a bit frustrating.
This is the problem, just change your mindset and do not allow yourself to become frustrated. Understanding accents gets better with time. Frustration is a personal issue you need to resolve.
General rule of thumb is not to project your personal issues on others in the workplace but resolve them yourself. If it's not their problem, don't make it their problem.