Most algorithms will come up with a randomly generated map purely based on a seed. It would never evaluate the map, and therefore not guarantee a nice user experience.
Since you have mentioned that you would like to build a "state of the art" map generator, the first thing that comes to my mind is genetic algorithms. Such an algorithm would create many different maps, based on an underlying gene combination. With each iteration, every map would be evaluated and improved. (the gene pool can be the exact same representation as your matrix above - what's even nice about this is that you will not have such a block city effect - unless that's what you want, then you can code it that way too).
In order to implement this, all you would need is an evaluation algorithm (for any given map). If you can come up with such an evaluation algorithm and you let this map-generation process run through a couple of iterations/evolutions (e.g. 100), you would end up with some really cool maps.
An evaluation algorithm (fitness) would consist of something like:
penalty = how many roads are too close to one another +
how many cities are too close to one another
I have simplified the formula above, it should be a bit more like: the sum of how close each city is to each other city + the sum of how close ... etc
fitness = 1/penalty
I did a quick search on: "genetic algorithm & map generator" and came up with some results that claim:
"In this paper we introduce a procedural map generator for a real-time strategy (RTS) game. The main component of this generator is a genetic algorithm devoted to create and evolve balanced maps, i.e. maps where no player has any map related advantage with respect to other players."