Travel restrictions are often imposed to limit the spread of infectious diseases. As uniform restrictions can be inefficient and incur unnecessarily high costs, this paper examines the optimal design of restrictions that target specific travel routes. We propose a model with trade-offs between costs of infections and costs of travel restrictions, where decisions are made with or without coordination between local jurisdictions and provide a computational feasible way to solve the optimization problem. We illustrate the model using the COVID-19 data in China. When travel restrictions target key routes, only around 5% of the possible routes need to be closed in order to have the same number of confirmed COVID-19 cases in the initial outbreaks. Uncoordinated travel restrictions ignore policy externalities and therefore are sub-optimal in comparison to coordinated restrictions.