The plastic bags problem was solved years ago in many places.

In the Uk and europe (western europe anyway) supermarkets now either (a) don't let you have them at all, (b) make you pay for them, or (c) let you have them but make you ask the checkout operator instead of having a bunch that you can help yourself to.

Most supermarkets are also selling larger more sturdy plastic shopping bags. These are marketed as a 'green' iniative as using less of the other bags is supposedly good for the environment.