It looks like you edited the deadlock graph to take the object and index names out, unfortunately that's made it hard to see what's going on. Can you either edit the XML and put the names back (obsfucated is fine, but I need to be able to see what locks are on what indexes), or attach an unmodified .xdl file.

Also can you please post the definition of the MasterItinerary table and all indexes (CREATE TABLE and CREATE INDEX statements)?