For reducing traffic jams without widening streets, we come up with a tenement rearrangement problem. In this paper, we study a tenement allocation model which includes two types of tenants, i.e., typical tenants and special tenants who owned houses by themselves. The optimal allocation is that total transportation cost is minimized without undermining tenants’ individual housing preference or increasing individual cost. Besides, we present a Modified Hungarian Algorithm for the above tenement allocation problem and prove that it can be solved in polynomial time. Furthermore, computational tests show that this algorithm has a good performance.