Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning
2026-06-29 • Machine Learning
Machine Learning
AI summaryⓘ
The authors designed a new way to plan routes for taxis that help people needing nursing care, considering special needs like wheelchair access and strict pick-up times. Because their problem is more complex than usual vehicle routing tasks, they used a machine learning method called a Transformer trained on high-quality solutions from a classical solver. They also added a step to fix routes so all the rules are followed. Compared to other methods, their approach finds good routes faster, reduces total driving time, and keeps mistakes very low, especially when serving fewer than 30 users.
Vehicle Routing ProblemNursing Care Taxi DispatchTransformer (machine learning)Supervised LearningInteger Linear ProgrammingRoute OptimizationConstraint SatisfactionWheelchair AccessibilityPick-up and Drop-off SchedulingComputational Efficiency
Authors
Riku Nakao, Akihito Hiromori, Hamada Rizk, Hirozumi Yamaguchi
Abstract
In this paper, we formulate a new vehicle dispatch optimization problem, called Nursing Care Taxi Dispatch, as a variant of the Vehicle Routing Problem, considering constraints related to wheelchair use, user compatibility, pick-up and drop-off times, and vehicle limitations. Previous neural-based methods for Vehicle Routing Problems have typically addressed a few simple constraints, while our new problem involves multiple complex constraints, resulting in having fewer destinations to select. This complexity makes it more difficult to obtain solutions that allow all nodes to be visited with a limited number of vehicles. To balance low violation rate, computational efficiency, and solution quality, we propose a supervised machine learning approach based on the Transformer architecture. We first obtain a set of high-quality solutions using an integer linear programming solver for given inputs and then train our learning model through supervised learning. Additionally, we introduce the post-processing of the paths generated by the learning model, ensuring that all constraints are satisfied. We compared each instance's objective function value (operating time), execution time, and constraint violation rate across different methods: our proposed method and some existing methods including integer linear programming and machine learning-based methods, using real-world facility data. Our method successfully produced balanced solutions regarding operating time, execution time, and constraint violation rate. Notably, we observed a decrease in the operating time for all problem sizes and regions, while keeping constraint violations to a minimum compared to existing methods. Especially, the decrease reached up to 8% for problem sizes with fewer than 30 users.