Japan’s logistics industry faces severe driver shortages and excessive working hours, particularly in long-distance trucking. Optimizing transportation scheduling is critical to reduce driver workload and improving efficiency, yet the combinatorial complexity of assigning numerous requests to drivers makes hard traditional manual planning. This paper proposes a novel solution method using integer programming; the long-distance truck transportation scheduling problem is formulated as a minimum-cost flow problem on a directed graph where nodes represent transportation requests and arcs show feasible sequential assignments. The objective is to minimize total deadhead distance, while following to constraints provided by Japan’s latest working hour regulations (the Improvement Standards Notification), including maximum daily restricted hours and minimum rest periods. By modeling driver assignments as flow paths, the proposed method reduces the computational burden associated with conventional set partitioning approaches. Computational experiments on two real-scale datasets reflecting long-distance operations demonstrate the method’s effectiveness; high loaded vehicle ratios (96.18% and 89.66%) are achieved, exceeding the national average and indicating deadhead reduction. Furthermore, optimal solutions are obtained within practical computation time (under 30 min) even for the larger dataset, confirming the approach’s scalability and potential for practical application.