{'fraction_non_alphanumeric': 0.018779342723004695, 'fraction_numerical': 0.0, 'mean_word_length': 5.26890756302521, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dynamic Routing with Tree Based Value Function Approximations

This paper is motivated from a collaboration with a start-up delivering on-demand health care services. In this setting, nurse practitioners need to be dynamically routed to patients' houses as service requests are received. We solve this problem using approximate dynamic programming and machine learning techniques. At every stage, an optimization problem needs to be solved to assign nurse practitioners to patients. We capture the future cost of having nurse practitioners positioned at certain locations around the city by estimating a cost-to-go function. Many previous approaches treat the cost-to-go function as a black box, which requires the enumeration of all possible actions to make a routing decision at each stage. This is an intractable problem in the reoptimization setting. Our approach overcomes this issue by approximating the cost-to-go function using a tree or tree ensemble, and leverages formulation techniques from Mixed Integer Optimization to solve the optimization problem at each stage sufficiently fast. Furthermore, this approach has the advantage of being more accurate relative to separable approximations used in the literature. We also apply this approach to several other online optimization problems in operations management which can be modeled through an underlying optimization formulation that needs to be solved at each stage, and show improvements relative to state-of-the-art methods.