Global corporations frequently grapple with a dilemma between fulfilling business needs and adhering to travel policies to mitigate excessive fare expenditures. This research examines the multifaceted nature of business travel, delving into its key characteristics and the inherent complexities faced by management in formulating effective policies. An optimal travel policy must both be practical to implement and contribute to budget optimization. The specific requirements of each company necessitate tailored policies; for instance, a manufacturing company with scheduled trips demands a distinct policy, unlike a consulting firm with unplanned travel. This study proposes a modified regression decision tree machine learning algorithm to incorporate the unique features of corporate travel policies. Our algorithm is designed to self-adjust based on the specific data of each individual company. The authors implement the proposed approach using travel data from a real-world company and conduct simulations in various scenarios, comparing the results with the industry standard. This research offers a machine-learning-based approach to determining the optimal advance booking policy for corporate travel.