MySQL database schema for shipping routes, avoiding complexity

I'm trying to build a MySQL schema for the following situation.

A book is being delivered from a locationA to locationB, through several other locations. e.g. For a book delivered from Vancouver to Los Angeles, we can go from Vancouver to Seattle to Portland to Los Angeles (Route 1), or alternatively it can take a different route from Vancouver to Calgary to Blaine to Seattle to Los Angeles (Route 2).

For every book delivered

• I'd like to keep track of the locations it passed through.
• I'd like to keep track of whether the book arrived at each location "on-time" or "late".

Later, when I pull up information about a given book, it's going to show the shipping route it took. Similarly, I'd be able to pull up books that were shipped through Calgary (or any other location). Also, I'd be able to show alternative shipping routes that were taken by multiple copies of the same book.

Already, a MySQL schema for this is beginning to sound very convoluted. I understand that with the proper use of foreign-keys and join-operations, we can make something work out.

However, I'm wondering whether the community can recommend a better way to organize this information. Is MySQL well-suited for this job? Should I just try to store this information on external XML files? Or should I explore a NoSQL approach? Comments would be very welcome.