近年來我國的人口結構逐漸朝向高齡化發展，其中獨居老人和行動不便者的比例也相對地增加，此外身心障礙的人數也是逐年增加，這表示了我國對看護的需求是非常急迫的，由於安養院有許多不便的因素，例如地理位置不佳、分布不均、資格限制…等，因此目前長期照護體系開始朝向居家式、社區式照顧服務發展。由於看護人士需要相對應的技能，故目前許多的居家看護是由民間公司外包，本研究希望能夠為居家看護的排班進行規劃，作為人力派遣公司規劃的參考。
本研究可以分為三個階段，首先界定研究的範圍與目的，接著完整定義問題，以含時間窗的定向越野問題為基礎，利用特殊時間窗限制以滿足協同服務和先後順序服務的限制，建立問題之數學規劃模型，最後發展一二階段啟發式演算法以求解此問題。先於第一階段中建構初始途程，再於第二階段中，以禁忌搜尋演算法為基礎，改善初始途程。為了驗證演算法之效果，本研究產生了56組測試例題，進行例題測試分析，進而提出結論與建議。

Recently, the proportion of elderly people is increasing in Taiwan. Moreover, the number of elderly people living alone and people with disabilities are also increasing. For this reason, there is an urgent need for healthcare services in Taiwan. Because there are many inconveniences or restrictions associated with nursing homes, such as facility location, availability, and eligibility, most people prefers homecare services or community healthcare services over nursing homes when they have long-term healthcare needs. Since professional skills are essential for homecare workers, most people hire homecare workers through agents or dispatching companies. This research studied the homecare worker scheduling problem. The results of this study may help the agents or dispatching companies in planning their homecare services and scheduling their homecare staffs.
This research can be divided into three stages. We first defined the scope and objective of this research. In the second stage, we defined the problem and developed a mathematics programming model for the problem based on the team orienteering problem with time windows. The model also includes special temporal constraints to deal with the synchronization and precedence requirements of homecare services. In the last stage, we developed a 2-stage metaheuristic to solve the problem. An initial solution is constructed in the first stage, and then improved by a tabu search heuristic in the second stage. 56 benchmark instances were created to test the applicability and the efficiency of the proposed meta-heuristic. Conclusions and suggestions are drawn based on the results of these computational experiments.

Archetti, C., Hertz, A., & Speranza, M. G. (2007). Metaheuristics for the Team Orienteering Problem. Journal of Heuristics, 13(1), 49-76.
Baker, E. K., & Schaffer, J. R. (1988). Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints. American Journal of Mathematical and Management Sciences, 6, 261-300.
Barnes, J. W., & Carlton, W. B. (1995). Solving the Vehicle Routing Problem with Time Windows using Reactive Tabu Search. presented at the Fall 1995 INFORMS Conference, New Orleans, LA.
Blanton, J. L., & Wainwright, R. L. (1993). Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms. in S. Forrest Eds, Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 452-459.
Bodin, B. G., Assad, A., & Ball, M. (1983). Routing and Scheduling of Vehicles and Crews:The State of the Art. Computers & Operations Research, 10, 63–211.
Bredström, D., & Rönnqvist, M. (2008). Combined Vehicle Routing and Scheduling with Temporal Precedence and Synchronization Constraints. European Journal of Operational Research, 191(1), 19-31.
Butt, S. E., & Cavalier, T. M. (1994). A Heuristic for the Multiple Path Maximum Collection Problem. Computers & Operations Research, 21, 101–111.
Carlton, W. B. (1995). A Tabu Search Approach to the General Vehicle Routing Problem. Ph.D. Dissertation, The University of Texas at Austin, Texas.
Chao, I.-M., Golden, B., & Wasil, E. A. (1996). Theory and Methodology: The Team Orienteering Problem. European Journal of Operational Research, 88, 464-474.
Cheng, C.-B., & Mao, C.-P. (2007). A Modified Ant Colony System for Solving the Travelling Salesman Problem with Time Windows. Mathematical and Computer Modelling, 46(9-10), 1225-1235.
Chiang , W. C., & Russell, R. A. (1993). Hybrid Heuristics for the Vehicle Routing Problem with Time Windows. Transportation Science, 29(2), 156-166.
Church, R. L., & ReVelle, C. (1974). The Maximal Covering Location Problem. Papers of the Regional Science Association, 32, 101-118.
Daskin, M. (1983). A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution. Transportation Science, 17(1), 48–70.
Derigs, U., & Grabenbauer, G. (1993). INTIME - A New Heuristic Approach to the Vehicle Routing Problem with Time Windows with a Bakery Fleet Case. American Journal of Mathematical and Management Sciences, 13, 249-266.
Desrochers, M., Desrosiers, J., & Solomon, M. M. (1992). A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operations Research, 40, 342-354.
Desrochers, M., Lenstra, J. K., Savelsbergh, M. W. P., & Soumis, F. (1988). Vehicle Routing with Time Windows: Optimization and Approximation. Optimization and Approximation, Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, 65-88.
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumi, F. (1995). Time Constrained Routing and Scheduling. in Handbooks in Operations Research and Management Science, 8, 35-139.
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E., & Gambardella, L. M. (2008). Time Dependent Vehicle Routing Problem with a Multi Ant Colony System. European Journal of Operational Research, 185(3), 1174-1191.
Duhamel, C., Garcia, B. L., & Potvin, J. Y. (1995). Accélération du Calcul des Fonctions Objectif pour les Problèmes de Tournées de Véhicules avec Fenêtres de Temps. Technical report CRT-95-04, Centre de recherche sur les transports, Université de Montréal, Montréal, Canada.
Gendreau, M., Laporte, G., & Semet , F. (1997). Solving an Ambulance Location Model by Tabu Search. Location Science, 5(2), 75-85.
Glover, F. (1986). Future Paths for Integer Programming and Links to Artifical Intelligence. Computers & Operations Research, 13, 533-549.
Golden, B., Levy, L., & Vohra, R. (1987). The Orienteering Problem. Naval Research Logistics, 34, 307-318.
Golden, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning Addison-Wesley, Reading, MA.
Hachicha, M., Hodgson, M. J., Laporte, G., & Semet, F. (2000). Heuristics for the Multi-vehicle Covering Tour Problem. Computers & Operations Research 27, 29–42.
Hodgson, M. J., Laporte, G., & Semet, F. (1998). A Covering Tour Model for Planning Mobile Health Care Facilities in Suhum district, Ghana. Journal of Regional Science, 38(4), 621–639.
Jozefowiez, N., Semet, F., & Talbi, E.-G. (2007). The Bi-objective Covering Tour Problem. Computers & Operations Research, 34, 1929–1942.
Ke, L., Archetti, C., & Feng, Z. (2008). Ants can Solve the Team Orienteering Pproblem. Computers & Industrial Engineering, 54(3), 648-665.
Kiechle, G., Doerner, K. F., Gendreau, M., & Hartl, R. F. (2007). Patient Transportation - Dynamic Dial-a-Ride and Emergency Transportation Problems. Preprints of TRISTAN 2007.
Kikuchi, S. (1990). Scheduling Demand Responsive Transponsive Transportation Vehicle Using Fuzzy Set Theory. Hokkaido University (working paper).
Kolen, A., Rinnooy Kan, A. H. G., & Trienekesn, H. (1987). Vehicle Routing with Time Windows. Operations Research 35, 266-273.
Kontoravdis, G., & Bard, J. (1995). A GRASP for the Vehicle Routing Problem with Time Windows. ORSA Journal on Computing, 7, 10-23.
Laporte, G. (1988). Location Routing Problems. Vehicle Routing: Methods and Studies, 163–197.
Marianov, V., & ReVelle, C. (1996). The Queueing Maximal Availability Location Problem: a Model for the Siting of Emergency Vehicles. European Journal of Operational Research, 93, 110–120.
Montemanni, R., & Gambardella, L. M. (2009). Ant Colony System for Team Orienteering Problems with Time Windows. Foundations of Computing and Decision Sciences 34(4), 287-306.
Or, I. (1976). Traveling Salesman-type Combinatorial Problems and their relation to the Logistics of Blood Banking. (Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL.).
Perl, J., & Daskin, M. S. (1984). A Unified Warehouse Location-routing Methodology. Journal of Business Logistics, 5, 92–111.
Potvin, J. Y., & Bengio, S. (1996). The Vehicle Routing Problem with Time Windows - Part II: Genetic Search. INFORMS Journal on Computing, 8(2), 165-172.
Potvin, J. Y., Kervahut, T., Garcia, B. L., & Rousseau, J. M. (1996). The Vehicle Routing Problem with Time Windows - Part I: Tabu Search. INFORMS Journal on Computing, 8(2), 158-164.
Potvin, J. Y., & Rousseau, J. M. (1993). A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows. European Journal of Operational Research, 66, 331-340.
Potvin, J. Y., & Rousseau, J. M. (1995). An Exchange Heuristic for Routing Problems with Time Windows. Journal of the Operational Research Society, 46, 1433-1446.
Rochat, Y., & Taillard, E. D. (1995). Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, 1, 147-167.
Russell, R. A. (1995). Hybrid Heuristics for the Vehicle Routing Problem with Time Windows. Transportation Science, 29, 156-166.
Savelsbergh, M. W. P. (1986). Local Search in Routing Problems with Time Windows. Annals of Operations Research, 4, 285-305.
Savelsbergh, M. W. P. (1990). An Efficient Implementation of Local Search Algorithms for Constrained Routing Problems. European Journal of Operational Research, 47, 75-85.
Savelsbergh, M. W. P. (1992). The Vehicle Routing Problem with Time Windows: Minimizing Route Duration. ORSA Journal on Computing, 4, 146-154.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35, 254-265.
Taillard, E., Badeau, P., Gendreau, M., Guertain, F., & Potvin, J. Y. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science, 32(2).
Tang, H., & Miller-Hooks, E. (2005). A TABU Search Heuristic for the Team Orienteering Problem. Computers & Operations Research, 32(6), 1379-1407.
Thangiah, S. R., Nygard, K., & Juell, P. (1991). GIDEON: A Genetic Algorithm System for Vehicle Routing with Time Windows. in Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications, IEEE Press, Miami, FL, 422-425.
Tricoire, F., Romauch, M., Doerner, K., & Hartl, R. (2010). Heuristics for the Multi-period Orienteering Problem with Multiple Time Windows. Computers & Operations Research, 37(2), 351–367.
Tsiligirides, T. (1984). Heuristic Methods Applied to Orienteering. Journal of the Operational Research Society, 35, 797-809.
Vansteenwegen, P., Souffriau, W., & Oudheusden, D. V. The orienteering problem: A survey. European Journal of Operational Research, In Press, Corrected Proof.
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009). Iterated Local Search for the Team Orienteering Problem with Time Windows. Computers & Operations Research, 36(12), 3281-3290.
Willard, J. A. G. (1989). Vehicle Routing Using r-optimal Tabu Search. MSc thesis, Management School Imperial College, London
Yu, B., Yang, Z.-Z., & Yao, B. (2009). An Improved Ant Colony Optimization for Vehicle Routing Problem. European Journal of Operational Research, 196(1), 171-176.