Stochastic Bi-level Programming Model for Home Healthcare Scheduling Problems Considering the Degree of Satisfaction with Visit Time

Abstract

Home health care (HHC) includes a wide range of healthcare services that are performed in customers’ homes to help them recover. With the constantly increasing demand for health care, HHC policymakers are eager to address routing and scheduling problems from the perspective of optimization. In this paper, a bi-level programming model for HHC routing and scheduling problems with stochastic travel times is proposed, in which the degree of satisfaction with the visit time is simultaneously considered. The upper-level model is formulated for customer assignment with the aim of minimizing the total operating cost, and the lower-level model is formulated as a routing problem to maximize the degree of satisfaction with the visit time. Consistent with Stackelberg game decision-making, the trade-off relationship between these two objectives can be achieved spontaneously so as to reach an equilibrium state. A three-stage hybrid algorithm combining an iterated local search framework, which uses a large neighborhood search procedure as a sub-heuristic, a set-partitioning model, and a post-optimization method is developed to solve the proposed model. Numerical experiments on a set of instances including 10 to 100 customers verify the effectiveness of the proposed model and algorithm.

Keywords

Home health care / bi-level programming / stochastic travel times / routing / meta-heuristic

References

[1] Bahadori-Chinibelagh S, Fathollahi-Fard A M, Hajiaghaei-Keshteli M (2019). Two constructive algorithms to address a multi-depot home healthcare routing problem. IETE Journal of Research: 1–7.

[2] Berhan E, Beshah B, Kitaw D, Abraham A. Stochastic vehicle routing problem: A literature survey. Journal of Information & Knowledge Management, 2014, 13(03): 1450022.

[3] Bertels S, Fahle T. A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Computers & Operations Research, 2006, 33(10): 2866-2890.

[4] Braekers K, Hartl R F, Parragh S N, Tricoire F. A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience. European Journal of Operational Research, 2016, 248(2): 428-443.

[5] Calvete H I, Galé C. On linear bilevel problems with multiple objectives at the lower level. Omega, 2011, 39(1): 33-40.

[6] Calvete H I, Galé C. Linear bilevel programming with interval coefficients. Journal of Computational and Applied Mathematics, 2012, 236(15): 3751-3762.

[7] Calvete H I, Galé C, Mateo P M. A new approach for solving linear bilevel problems using genetic algorithms. European Journal of Operational Research, 2008, 188(1): 14-28.

[8] Cheng G, Zhao S, Zhang T. A bi-level programming model for optimal bus stop spacing of a bus rapid transit system. Mathematics, 2019, 7(7): 625.

[9] Chiou S W. A bi-level decision support system for uncertain network design with equilibrium flow. Decision Support Systems, 2015, 69: 50-58.

[10] Choi E, Tcha D W. A column generation approach to the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 2007, 34(7): 2080-2095.

[11] Cissé M, Yalçındağ S, Kergosien Y, Şahin E, Lenté C, Matta A. OR problems related to Home Health Care: A review of relevant routing and scheduling problems. Operations Research for Health Care, 2017, 13: 1-22.

[12] Colson B, Marcotte P, Savard G. Bilevel programming: A survey. 4OR, 2005, 3(2): 87-107.

[13] Colson B, Marcotte P, Savard G. An overview of bilevel optimization. Annals of Operations Research, 2007, 153(1): 235-256.

[14] Cordeau J F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 2001, 52(8): 928-936.

[15] Decerle J, Grunder O, El Hassani A H, Barakat O. A memetic algorithm for multi-objective optimization of the home health care problem. Swarm and Evolutionary Computation, 2019, 44: 712-727.

[16] Dempe S (2002). Foundations of Bilevel Programming, Springer Science Business Media.

[17] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 1992, 40(2): 342-354.

[18] Duque P M, Castro M, Sörensen K, Goos P. Home care service planning. The case of Landelijke Thuiszorg. European Journal of Operational Research, 2015, 243(1): 292-301.

[19] Fathollahi-Fard A M, Ahmadi A, Goodarzian F, Cheikhrouhou N. A bi-objective home healthcare routing and scheduling problem considering patients’ satisfaction in a fuzzy environment. Applied Soft Computing, 2020, 93(1): 106385.

[20] Fathollahi-Fard A M, Govindan K, Hajiaghaei-Keshteli M, Ahmadi A. A green home health care supply chain: New modified simulated annealing algorithms. Journal of Cleaner Production, 2019, 240: 118200.

[21] Fathollahi-Fard A M, Hajiaghaei-Keshteli M, Mirjalili S. A set of efficient heuristics for a home healthcare problem. Neural Computing and Applications, 2020, 32(10): 6185-6205.

[22] Fathollahi-Fard A M, Hajiaghaei-Keshteli M, Tavakkoli-Moghaddam R. Abi-objective green home health care routing problem. Journal of Cleaner Production, 2018, 200: 423-443.

[23] Feillet D, Dejax P, Gendreau M, Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks: An International Journal, 2004, 44(3): 216-229.

[24] Fikar C, Hirsch P. Home health care routing and scheduling: A review. Computers & Operations Research, 2017, 77: 86-95.

[25] Gendreau M, Hertz A, Laporte G, Stan M. A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 1998, 46(3): 330-335.

[26] Gendreau M, Marcotte P, Savard G. A hybrid tabuascent algorithm for the linear bilevel programming problem. Journal of Global Optimization, 1996, 8(3): 217-233.

[27] Grenouilleau F, Legrain A, Lahrichi N, Rousseau L M. A set partitioning heuristic for the home health care routing and scheduling problem. European Journal of Operational Research, 2019, 275(1): 295-303.

[28] Grieco L, Utley M, Crowe S (2020). Operational research applied to decisions in home health care: A systematic literature review. Journal of the Operational Research Society: 1–32.

[29] Hajiaghaei-Keshteli M, Fathollahi-Fard A M. A set of efficient heuristics and metaheuristics to solve a twostage stochastic bi-level decision-making model for the distribution network problem. Computers & Industrial Engineering, 2018, 123: 378-395.

[30] Hejazi S R, Memariani A, Jahanshahloo G, Sepehri M M. Linear bilevel programming solution by genetic algorithm. Computers & Operations Research, 2002, 29(13): 1913-1925.

[31] Kheirkhah A, Navidi H, Messi Bidgoli M. A bi-level network interdiction model for solving the hazmat routing problem. International Journal of Production Research, 2016, 54(2): 459-471.

[32] Kuo R, Huang C. Application of particle swarm optimization algorithm for solving bi-level linear programming problem. Computers & Mathematics with Applications, 2009, 58(4): 678-685.

[33] Laumanns M, Zenklusen R. Stochastic convergence of random search methods to fixed size Pareto front approximations. European Journal of Operational Research, 2011, 213(2): 414-421.

[34] Li H, Bai M, Zhao Y, Dai. Vehicle flow formulation for two-echelon time-constrained vehicle routing problem. Journal of Management Science and Engineering, 2019, 4(2): 75-90.

[35] Liu R, Yuan B, Jiang Z. A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times. Flexible Services and Manufacturing Journal, 2019, 31(4): 989-1011.

[36] Lourenço H R, Martin O C, Stützle T (2019). Iterated local search: Framework and applications. Handbook of Metaheuristics: 129–168.

[37] Lu J, Han J, Hu Y, Zhang G. Multilevel decisionmaking: A survey. Information Sciences, 2016, 346: 463-487.

[38] Marinakis Y, Migdalas A, Pardalos P M. A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm. Journal of Global Optimization, 2007, 38(4): 555-580.

[39] Mersha A G, Dempe S. Linear bilevel programming with upper level constraints depending on the lower level solution. Applied Mathematics and Computation, 2006, 180(1): 247-254.

[40] Ning Y, Su T. A multilevel approach for modelling vehicle routing problem with uncertain travelling time. Journal of Intelligent Manufacturing, 2017, 28(3): 683-688.

[41] Parvasi S P, Mahmoodjanloo M, Setak M. A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing. Applied Soft Computing, 2017, 61: 222-238.

[42] Penna P H V, Subramanian A, Ochi L S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 2013, 19(2): 201-232.

[43] Pisinger D, Ropke S. A general heuristic for vehicle routing problems. Computers & Operations Research, 2007, 34(8): 2403-2435.

[44] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 2006, 40(4): 455-472.

[45] Russell R A, Urban T L. Vehicle routing with soft time windows and Erlang travel times. Journal of the Operational Research Society, 2008, 59(9): 1220-1228.

[46] Sameh A, Mohammad A. Multi-objective optimization for the multi-mode finance-based project scheduling problem. Frontiers of Engineering Management, 2020, 7(2): 223-237.

[47] Santos M J, Curcio E, Amorim P, Carvalho M, Marques A. A bilevel approach for the collaborative transportation planning problem. International Journal of Production Economics, 2021, 233: 108004.

[48] Shaw P (1998). Using constraint programming and local search methods to solve vehicle routing problems. International Conference on Principles and Practice of Constraint Programming Heidelberg, German, Octomber 26, 1998.

[49] Shi Y, Boudouh T, Grunder O. A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 2017, 72: 160-176.

[50] Shi Y, Boudouh T, Grunder O. Arobust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transportation Research Part E: Logistics and Transportation Review, 2019, 128: 52-95.

[51] Shi Y, Boudouh T, Grunder O, Wang D. Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care. Expert Systems with Applications, 2018, 102: 218-233.

[52] Subramanian A, Penna P H V, Uchoa E, Ochi L S. A hybrid algorithm for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 2012, 221(2): 285-295.

[53] Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 1997, 31(2): 170-186.

[54] Tang Q, Fu Z, Qiu M (2019). A bilevel programming model and algorithm for the static bike repositioning problem. Journal of Advanced Transportation. DOI:https://doi.org/10.1155/2019/8641492.

[55] Taş D, Dellaert N, VanWoensel T, De Kok T. Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computers & Operations Research, 2013, 40(1): 214-224.

[56] Taş D, Dellaert N, van Woensel T, De Kok T. The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transportation Research Part C: Emerging Technologies, 2014, 48: 66-83.

[57] Taş D, Gendreau M, Dellaert N, Van Woensel T, De Kok A. Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach. European Journal of Operational Research, 2014, 236(3): 789-799.

[58] Trautsamwieser A, Hirsch P. Optimization of daily scheduling for home health care services. Journal of Applied Operational Research, 2011, 3(3): 124-136.

[59] Wen U, Huang A. A simple tabu search method to solve the mixed-integer linear bilevel programming problem. European Journal of Operational Research, 1996, 88(3): 563-571.

[60] Yuan B, Liu R, Jiang Z. A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements. International Journal of Production Research, 2015, 53(24): 7450-7464.