MySQL Latest Deadlock Explanation
From the output the two inserts are doing gap locking on the index index_shipments_on_ci_ai_tn_sti. Without knowing the table definition, I think the index is a UNIQUE index.

Here is a decent blog explaining the reason UNIQUE constraints can cause deadlocks on concurrent inserts. Snippet here:


  Mysql innodb engine performs row locking on inserts. If column A has a unique key constraint, and we are adding the value "bbb" for column A in an insert statement, mysql needs to lock any gap in the index between the two current records where "bbb" will be inserted at.


More information on gap locking can be found in the docs: http://dev.mysql.com/doc/refman/5.6/en/innodb-record-level-locks.html