1.在这种情况下,他是否可以终止租赁合同基于military orders
No, he is not. Only military transfer order can break the lease.
2.如果没有,我可以向他收取租金损失,以及租赁中间更换租户的费用.清洁费用等吗?
Only rent loss, but not turnover expenses e.g. cleaning, because you are responsible for turnover expense no matter when he moves out.
3.我是否可以适当收取我个人花在 寻找新房客的时间的费用。 如果可以,$20-30/hour
No, again, you are responsible for tenant search time no matter when he moves out
4, 当我找到新房客的时候,我是否可以要求比我现在更高的房租(我给他租金低于市场价格是因为他签了三年租约)
Yes, you have duty to use "reasonable" effort to find new tenants. This means no lower of rent, no lower of credit/income requirement, following market rate at the time of the search etc.