Background: The Vehicle Routing Problem with Time Windows (VRPTW) has been extensively researched due to its applicability across various real-world domains, including logistics, healthcare, and distribution systems. With the global elderly population projected to continue increasing, the demand for home healthcare (HHC) services is also on the rise. This work focuses on a specific application within an HHC system, aiming to minimize the total completion time for a fleet of vehicles delivering healthcare services to patients at home. Methods: We propose a mathematical model for the VRPTW, targeting a reduction in both customer and server waiting times on each route and seeking to decrease the total completion time. Our proposed algorithm employs a tabu search to narrow the search space, leveraging a greedy algorithm to establish the tabu list. Results: Our experimental results, based on Solomon’s benchmark datasets, demonstrate that the proposed algorithms achieve optimal solutions, particularly in minimizing total completion time compared to traditional methods, in a case study involving 400 customers where vehicles’ hours are restricted to align with caregivers’ average daily working hours. Conclusions: Our algorithm resulted in a 59% reduction in the number of vehicles required compared to the most recent algorithms, which combine k-mean clustering and local search.

This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.