Anyone who doesn't use fully biodegradable bags (eg cornstarch) is evil.
Anyone who leaves them hanging on trees deserves to have their animal taken away and be given community service cleaning up excrement.
Rubbish/refuse/litter/trash though, put it in your pocket, or a shoulder bag, then dispose of it when you get home. No need to put litter bins all over the place.
The thing about litter bins, though, is that if you do put them in good spots they are effective at modifying the behavior you are against here. If you want to affect a change in behavior, you will have better success working with the flow of how we know humans interact with the environment than against it.
Put dog poo in a non-fully-degradable plastic bag and put it in a compost bin and it will just be the same poo in a decade.