I would store the data in a graph to help with pathfinding - nodes are intersections and edges are streets (with one-way, no pedestrian, etc flags). Then for storing the data I would take a multi-layered approach
Gather the Source Data
First find some way to define (or import) the data. Likely a visual tool would help, but you could get away with something that supports real-world coordinates (latitude, longitude, etc). You will want to support connectivity at this stage, but also allow objects to be just 'placed' in the world (cinemas, etc), since writing the tedious connectivity code in XML, JSON or a non-visual tool will be cumbersome. File format of this might be useful to be somewhat human readable, so XML or JSON, as long as the format supports circular references and links. Nodes likely should be stored in a text-editor searchable format - GUID, or some such - to help authoring and debugging.
Add Connections & Validate
Now you need a tool that takes **all* of the world data and creates any game-specific connections, intersects roads and makes connections, annotates the world with one-way-streets. The data should be loaded all at once, in an offline tool, into some kind of verbose/fat format. It would have all the useful information in it so you can write validation steps. It should also allow debug pathfinding so you can run offline tests that you can truly get from the Eiffel Tower to the Louvre. Having a separate tool in an offline process for this is great because you can add as much cumbersome debugging information to it but you never have to feel like your game code is getting dirty. Plus the format you store this in memory will likely be vary different than in games - adjacent nodes will be in a dynamic list, whereas at runtime it will be in a fixed sized array, or a linked list, for example.
To make searches efficient you will want to store the data in some kind of efficient representation. That means your GUIDS will be compressed down to some kind of incrementing ID, and adjacency/edge information will be stored in flat arrays, or linked lists. All of this is really important to get your searches fast. Furthermore, specific entities (such as restaurants, or cinemas, would be stored in a separate data structure so you can quickly locate their positions in the world. That structure might be a database of restaurants, say, or it might be a uniform grid where each grid stores all of the buildings in it in order to make searches for 'nearest things' faster, or both. I suspect both. By making the emitting stage separate from the validate stage you can write code that compresses the data into game-ready format without worrying that you've broken the preprocessing or validation stage. Your writing code might be sharable with the reading code in the game, too. You might also want to chunk up the data into pieces to stream in, or implement a hierarchical path finding system on top of it so you don't need all of the fine-grained data loaded all the time.
Load the data
Now the game loads the data and starts working on it. Ideally the data is loaded with as little work possible. I always strive to make my data memory imaged so it loads in place without any allocations, but that's for my commercial production game environment.