Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning

• URL: http://arxiv.org/abs/2606.29725v1
• Date: Mon, 29 Jun 2026 03:05:58 GMT
• Title: Optimizing Nursing Care Taxi Dispatch Leveraging Integer Linear Programming Solvers and Machine Learning
• Abstract summary: We formulate a new vehicle dispatch optimization problem, called Nursing Care Taxi Dispatch, as a variant of the Vehicle Routing Problem.<n>Our new problem involves multiple complex constraints, resulting in having fewer destinations to select.<n>To balance low violation rate, computational efficiency, and solution quality, we propose a supervised machine learning approach.
• Score: 5.716454975957337
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees [20.469394148261838]
  Mixed-integer nonlinear programs (MINLPs) arise in domains as diverse as energy systems and transportation, but are notoriously difficult to solve.<n>We propose a novel L2O approach with two integer correction layers to ensure the integrality of the solution and a projection step to ensure the feasibility of the solution.<n>Our experiments show that our methods efficiently solve MINLPs with up to tens of thousands of variables, providing high-quality solutions within milliseconds.
  arXiv  Detail & Related papers  (2024-10-14T20:14:39Z)
• Machine Learning and Constraint Programming for Efficient Healthcare Scheduling [0.8287206589886879]
  We tackle the Nurse Scheduling Problem (NSP) In the implicit solving approach, we rely on Machine Learning methods using historical data to learn and generate new solutions through the constraints and objectives that may be embedded in the learned patterns. To compensate for the uncertainty related to the implicit approach given that the constraints and objectives may not be concretely visible in the produced solutions, we propose an explicit approach where we first model the NSP using the Constraint Satisfaction Problem framework. Since our implicit approach may not guarantee the feasibility or optimality of the generated solution, we propose a data-driven approach to passively learn the NSP as a constraint
  arXiv  Detail & Related papers  (2024-09-11T18:09:25Z)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation.<n>We introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  We study sequential decision-making with known rewards and unknown constraints. As an application, we consider learning constraints to represent human preferences in a driving simulation.
  arXiv  Detail & Related papers  (2022-06-10T17:52:58Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Machine-learning-based arc selection for constrained shortest path problems in column generation [5.08128537391027]
  In this work, we propose a new pricing algorithm based on machine learning. The objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows.
  arXiv  Detail & Related papers  (2022-01-07T16:49:12Z)
• Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size [3.5235974685889397]
  Learning to solve optimization problems, such as the vehicle routing problem, offers great computational advantages. We propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of vehicles. In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also competitive results.
  arXiv  Detail & Related papers  (2022-01-05T10:32:18Z)
• A Case Study of Vehicle Route Optimization [2.2101681534594237]
  In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
  arXiv  Detail & Related papers  (2021-11-17T13:10:55Z)
• Learning to Delegate for Large-scale Vehicle Routing [4.425982186154401]
  Vehicle routing problems (VRPs) are a class of problems with wide practical applications. Previous or learning-based works achieve decent solutions on small problem instances of up to 100 customers. This article presents a novel learning-augmented local search algorithm to solve large-scale VRP.
  arXiv  Detail & Related papers  (2021-07-08T22:51:58Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.