{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T05:28:11Z","timestamp":1790832491770,"version":"4.1.0"},"reference-count":68,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T00:00:00Z","timestamp":1564444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Home Healthcare (HHC) is an emerging and fast-expanding service sector that gives rise to challenging vehicle routing and scheduling problems. Each day, HHC structures must schedule the visits of caregivers to patients requiring specific medical and paramedical services at home. These operations have the potential to be unsuitable if the visits are not planned correctly, leading hence to high logistics costs and\/or deteriorated service level. In this article, this issue is modeled as a vehicle routing problem where a set of routes has to be built to visit patients asking for one or more specific service within a given time window and during a fixed service time. Each patient has a preference value associated with each available caregiver. The problem addressed in this paper considers two objectives to optimize simultaneously: minimize the caregivers\u2019 travel costs and maximize the patients\u2019 preferences. In this paper, different methods based on the bi-objective non-dominated sorting algorithm are proposed to solve the vehicle routing problem with time windows, preferences, and timing constraints. Numerical results are presented for instances with up to 73 clients. Metrics such as the distance measure, hyper-volume, and the number of non-dominated solutions in the Pareto front are used to assess the quality of the proposed approaches.<\/jats:p>","DOI":"10.3390\/a12080152","type":"journal-article","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T11:15:56Z","timestamp":1564485356000},"page":"152","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Bicriteria Vehicle Routing Problem with Preferences and Timing Constraints in Home Health Care Services"],"prefix":"10.3390","volume":"12","author":[{"given":"Syrine Roufaida","family":"Ait Haddadene","sequence":"first","affiliation":[{"name":"Natan, 44 Rue Notre Dame Des Victoires, 75002 Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nacima","family":"Labadie","sequence":"additional","affiliation":[{"name":"ICD-LOSI, University of Technology of Troyes, 12 Rue Marie Curie, CEDEX CS 42060-10004 Troyes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Caroline","family":"Prodhon","sequence":"additional","affiliation":[{"name":"ICD-LOSI, University of Technology of Troyes, 12 Rue Marie Curie, CEDEX CS 42060-10004 Troyes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,7,30]]},"reference":[{"key":"ref_1","first-page":"274","article-title":"A GRASP \u00d7 ILS for the vehicle routing problem with time windows, synchronization and precedence constraints","volume":"6","author":"Labadie","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The truck dispatching problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications, SIAM.","DOI":"10.1137\/1.9781611973594"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10288-013-0240-5","article-title":"General solution approaches for multi-attribute vehicle routing and scheduling problems","volume":"12","author":"Vidal","year":"2014","journal-title":"4OR"},{"key":"ref_5","unstructured":"Aarts, E., and Lenstra, J. (1997). Vehicle routing: Handling edge exchanges. Local Search in Combinatorial Optimization, Wiley."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1287\/trsc.1030.0057","article-title":"Vehicle routing problem with time windows, part I: Route construction and local search algorithms","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_7","unstructured":"Nagata, Y. (2007, January 25\u201328). Efficient Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows: Edge Assembly Crossover for the VRPTW. Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore."},{"key":"ref_8","unstructured":"Br\u00e4ysy, O., Gendreau, M., and Tarantilis, C. (2010). Solving Large-Scale Vehicle Routing Problems with Time Windows: The State-of-the-Art, Montreal. Technical Report."},{"key":"ref_9","first-page":"73","article-title":"The multi-vehicle subscriber dial-a-ride problem","volume":"2","author":"Bodin","year":"1986","journal-title":"TIMS Stud. Manag. Sci."},{"key":"ref_10","unstructured":"Cheng, E., and Rich, J. (1998). A Home Health Care Routing and Scheduling Problem, Rice University. Technical Report CAAM TR98-04."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.cor.2016.07.019","article-title":"Home healthcare routing and scheduling: A review","volume":"77","author":"Fikar","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_12","first-page":"1","article-title":"OR problems related to Home Health Care: A review of relevant routing and scheduling problems","volume":"13","author":"Kergosien","year":"2017","journal-title":"Oper. Res. Health Care"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1287\/inte.27.4.35","article-title":"An integrated spatial DSS for scheduling and routing home-health-care nurses","volume":"27","author":"Begur","year":"1997","journal-title":"Interfaces"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2866","DOI":"10.1016\/j.cor.2005.01.015","article-title":"A hybrid setup for a hybrid scenario: Combining heuristics for the home healthcare problem","volume":"33","author":"Bertels","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"962","DOI":"10.1016\/j.ejor.2005.01.011","article-title":"Laps Care\u2014An operational system for staff planning of home care","volume":"171","author":"Eveborn","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1016\/j.cie.2007.06.002","article-title":"PSO-based algorithm for home care worker scheduling in the UK","volume":"53","author":"Akjiratikarl","year":"2007","journal-title":"Comput. Ind. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.ejor.2007.07.033","article-title":"Combined vehicle routing and scheduling with temporal precedence and synchronization constraints","volume":"191","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Steeg, J., and Schr\u00f6der, M. (2008). A hybrid approach to solve the periodic home healthcare problem. Operations Research Proceedings 2007, Springer.","DOI":"10.1007\/978-3-540-77903-2_46"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1057\/palgrave.jors.2602574","article-title":"A patient assignment algorithm for home care services","volume":"60","author":"Hertz","year":"2009","journal-title":"J. Oper. Res. Soc."},{"key":"ref_20","first-page":"2877","article-title":"Collaborative model for planning and scheduling caregivers\u2019 activities in homecare","volume":"44","author":"Redjem","year":"2011","journal-title":"IFAC World Congr."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1007\/s00291-011-0253-4","article-title":"Securing home healthcare in times of natural disasters","volume":"33","author":"Trautsamwieser","year":"2011","journal-title":"OR Spectr."},{"key":"ref_22","first-page":"124","article-title":"Optimization of daily scheduling for home healthcare services","volume":"3","author":"Trautsamwieser","year":"2011","journal-title":"J. Appl. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1016\/j.ejor.2011.10.042","article-title":"Mid-term and short-term planning support for home healthcare services","volume":"219","author":"Nickel","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Gamst, M., and Jensen, T. (2012). A branch-and-price algorithm for the long-term home care scheduling problem. Operations Research Proceedings 2011, Springer.","DOI":"10.1007\/978-3-642-29210-1_77"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1016\/j.ejor.2011.10.048","article-title":"The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies","volume":"219","author":"Rasmussen","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","unstructured":"Redjem, R., Kharraja, S., Xie, X., and Marcon, E. (, January June). Routing and scheduling of caregivers in home healthcare with synchronized visits. Proceedings of the 9th International Conference on Modeling, Optimization & SIMulation, Bordeaux, France."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Afifi, S., Dang, D., and Moukrim, A. (2013). A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints. Learning and Intelligent Optimization, Springer.","DOI":"10.1007\/978-3-642-44973-4_27"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.ejor.2013.04.044","article-title":"Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home healthcare","volume":"230","author":"Liu","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s10100-013-0305-8","article-title":"Metaheuristics for solving a multimodal home-healthcare scheduling problem","volume":"23","author":"Hiermann","year":"2013","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/j.endm.2013.05.127","article-title":"A matheuristic approach for solving a home healthcare problem","volume":"41","author":"Allaoua","year":"2013","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.omega.2014.03.003","article-title":"Hybridization of tabu search with feasible and infeasible local searches for periodic home healthcare logistics","volume":"47","author":"Liu","year":"2014","journal-title":"Omega"},{"key":"ref_32","unstructured":"Labadie, N., Prins, C., and Yang, Y. (2014, January 6\u20138). Iterated local search for a vehicle routing problem with synchronization constraints. Proceedings of the ICORES 2014 3rd International Conference on Operations Research and Enterprise Systems, Angers, Loire Valley, France."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Ait Haddadene, S., Labadie, N., and Prodhon, C. (2014, January 8\u201310). GRASP for the Vehicle Routing Problem With Time Windows, Synchronization and Precedence Constraints. Proceedings of the IEEE 10th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Larnaca, Cyprus.","DOI":"10.1109\/WiMOB.2014.6962152"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Ait Haddadene, S., Labadie, N., and Prodhon, C. (2014, January 5\u20137). The VRP with Time Windows, Synchronization and Precedence Constraints: Application in Home Health Care Sector. Proceedings of the MOSIM 2014, 10\u00e8me Conf\u00e9rence Francophone de Mod\u00e9lisation, Optimisation et Simulation, Nancy, France.","DOI":"10.1109\/WiMOB.2014.6962152"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.endm.2014.11.024","article-title":"New Multi-Objective Approach for the Home Care Service Problem Based on Scheduling Algorithms and Variable Neighborhood Descent","volume":"47","author":"Issaoui","year":"2015","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1016\/j.ifacol.2015.06.164","article-title":"A Multi-objective Modelling to Human Resource Assignment and Routing Problem for Home Health Care Services","volume":"48","author":"Allaoui","year":"2015","journal-title":"IFAC-PapersOnLine"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.ejor.2014.11.008","article-title":"Home care service planning. The case of Landelijke Thuiszorg","volume":"243","author":"Castro","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1016\/j.ejor.2015.07.028","article-title":"A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience","volume":"248","author":"Braekers","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s11590-015-0878-3","article-title":"Heuristic solutions for the vehicle routing problem with time windows and synchronized visits","volume":"10","author":"Afifi","year":"2016","journal-title":"Optim. Lett."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/s10696-016-9252-8","article-title":"Evaluation of trip and car sharing concepts for home healthcare services","volume":"30","author":"Fikar","year":"2016","journal-title":"Flex. Serv. Manuf. J."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/978-3-319-33954-2_14","article-title":"Scheduling home hospice care with logic-based benders decomposition","volume":"9676","author":"Heching","year":"2016","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.eswa.2016.06.010","article-title":"The therapist assignment problem in home healthcare structures","volume":"62","author":"Lin","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/s10696-015-9220-8","article-title":"Operations management in the home care services: A heuristic for the caregivers\u2019 routing problem","volume":"28","author":"Redjem","year":"2016","journal-title":"Flex. Serv. Manuf. J."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/j.eswa.2016.12.013","article-title":"A hybrid genetic algorithm for a home healthcare routing problem with time window and fuzzy demand","volume":"72","author":"Shi","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.orhc.2015.08.005","article-title":"Patient-based nurse rostering in home care","volume":"8","author":"Wirnitzer","year":"2016","journal-title":"Oper. Res. Health Care"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/s10696-015-9222-6","article-title":"The patient assignment problem in home healthcare: Using a data-driven method to estimate the travel times of care givers","volume":"28","author":"Matta","year":"2016","journal-title":"Flex. Serv. Manuf. J."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"14662","DOI":"10.1016\/j.ifacol.2017.08.1907","article-title":"A general model for the home healthcare routing and scheduling problem with route balancing","volume":"50","author":"Decerle","year":"2017","journal-title":"IFAC-PapersOnLine"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Du, G., Liang, X., and Sun, C. (2017). Scheduling optimization of home healthcare service considering patients\u2019 priorities and time windows. Sustainability, 9.","DOI":"10.3390\/su9020253"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.endm.2017.03.009","article-title":"General variable neighborhood search for home healthcare routing and scheduling problem with time windows and synchronized visits","volume":"58","author":"Frifita","year":"2017","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s10479-016-2352-8","article-title":"Decomposition techniques with mixed integer programming and heuristics for home healthcare planning","volume":"256","author":"Laesanklang","year":"2017","journal-title":"Ann. Oper. Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.orhc.2018.01.004","article-title":"A memetic algorithm for a home healthcare routing and scheduling problem","volume":"16","author":"Decerle","year":"2018","journal-title":"Oper. Res. Health Care"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jclepro.2018.07.258","article-title":"A bi-objective green home healthcare routing problem","volume":"200","year":"2018","journal-title":"J. Clean. Prod."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.cie.2017.11.004","article-title":"Jointly rostering, routing, and rerostering for home healthcare services: A harmony search approach with genetic, saturation, inheritance, and immigrant schemes","volume":"115","author":"Lin","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Nasir, J., and Dang, C. (2018). Solving a more flexible home healthcare scheduling and routing problem with joint patient and nursing staff selection. Sustainability, 10.","DOI":"10.3390\/su10010148"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/j.cor.2018.08.002","article-title":"An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits","volume":"101","author":"Liu","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.eswa.2019.02.009","article-title":"A matheuristic approach to the integration of worker assignment and vehicle routing problems: Application to home healthcare scheduling","volume":"125","author":"Moussavi","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1080\/00207543.2016.1213917","article-title":"Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements","volume":"55","author":"Liu","year":"2017","journal-title":"Int. J. Prod. Res."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1287\/trsc.1110.0400","article-title":"Synchronization in vehicle routing-A survey of VRPs with multiple synchronization constraints","volume":"46","author":"Drexl","year":"2012","journal-title":"Transp. Sci."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Jozefowiez, N., Semet, F., and Talbi, E. (2006). Enhancements of NSGAII and Its Application to the Vehicle Routing Problem with Route Balancing, Springer. Artificial Evolution.","DOI":"10.1007\/11740698_12"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"3473","DOI":"10.1016\/j.cor.2005.02.017","article-title":"A genetic algorithm for a bi-objective capacitated arc routing problem","volume":"33","author":"Lacomme","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1080\/0305215X.2011.639368","article-title":"A non-dominated sorting genetic algorithm for a bi-objective pick-up and delivery problem","volume":"44","author":"Velasco","year":"2012","journal-title":"Eng. Optim."},{"key":"ref_62","first-page":"211","article-title":"A vehicle routing problem for modeling home healthcare: A case study","volume":"5","author":"Issabakhsh","year":"2018","journal-title":"Int. J. Transp. Eng."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.simpat.2017.03.006","article-title":"A multi-agent system based on reactive decision rules for solving the caregiver routing problem in home healthcare","volume":"74","author":"Marcon","year":"2017","journal-title":"Simul. Model. Pract. Theory"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-II","volume":"6","author":"Deb","year":"2002","journal-title":"Evol. Comput. IEEE Trans."},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Labadie, N., Melechovsky, J., and Prins, C. (2014). An evolutionary algorithm with path relinking for a bi-objective multiple traveling salesman problem with profits. Applications of Multi-Criteria and Game Theory Approaches, Springer.","DOI":"10.1007\/978-1-4471-5295-8_10"},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Murata, T., Nozawa, H., Ishibuchi, H., and Gen, M. (2003). Modification of Local Search Directions for Non-Dominated Solutions in Cellular Multiobjective Genetic Algorithms for Pattern Classification Problems, Springer. Evolutionary Multi-Criterion Optimization.","DOI":"10.1007\/3-540-36970-8_42"},{"key":"ref_67","unstructured":"Schott, J. (1995). Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. [Master\u2019s Thesis, Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics]."},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/TEVC.2003.810758","article-title":"Performance assessment of multiobjective optimizers: An analysis and review","volume":"7","author":"Zitzler","year":"2003","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/152\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:11:13Z","timestamp":1760188273000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,30]]},"references-count":68,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080152"],"URL":"https:\/\/doi.org\/10.3390\/a12080152","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,30]]}}}