Complain on
http://community.virginmedia.com/ and provide the info they ask for. They should come back with a fault reference and projected fix date. When they've missed that date ask again. Repeat until you are either out of minimum term or can afford the cancellation fee.
I doubt that any local problems will get fixed now except as part of the nationwide upgrade to come close to supporting the speeds they are currently selling in advance of doubling them so that the pattern can repeat.
In the meantime downgrade to 10Mbps - it won't fix anything but it will be cheaper and from the look of your graph you won't lose much either.
This is almost the same as me except I've now given up complaining on the community board (but not here or other boards) and am waiting for Infinity rather than the end of my contract.