本研究討論了以時變路網(Time Dependent road network )為背景發展出的團體排程問題。在過去的多人銷售員(MTSP) 問題研究史上，雖發展出了廣泛領域的應用,但由於多只考慮了行程距離的最小化,反而局限了延伸的發展性，因此在本論文中將時間也加入考量,考慮了隨時間而變化的路況，以及拜訪點的時間窗條件限制，發展出了更多貼近現實生活的應用。
在本研究中,我們將說明基於時變路網發展的團體排程問題的詳細定義。並且設計了三個演算法來解決此問題。分別為以 EnumerationAlgorithm (EA),以窮舉所有分配組合與拜訪排序找出最佳解,以及基於 EA 提出過濾機制減少計算組合數的Pruning Algorithm (PA),最後，為了能應用在 member 和 poi 數量遽增情形,提出 Greedy Algorithm (GA) 方法。我們以不同面向的實驗觀察不同變量對演算法的影響,並驗證以上三個演算法的有效性。

The research discussed the scheduling problem developed with the background of Time Dependent Road Network (Time Dependent Road Network). Most of them only consider the minimization of the itinerary, and the nutrition increases with the expansion. Therefore, the development time is also considered in this paper. The road conditions that change over time and the time window conditions of the visit point are considered, and the development is healthier. More close to real-life applications.
In this study, we will explain the definition of personal scheduling problems based on the development of time-varying road networks. And three algorithms are designed to solve this problem. Respectively, the enumeration algorithm (EA) is used to find the best solution by exhausting all the allocation combinations and the order of appearance, and the method of calculating the number of combinations based on the filtering mechanism proposed by EA (PA), and finally, in order to be applied to members and poi In the case of a sudden increase in the number, the Greedy Algorithm (GA) is proposed. An experiment observes the influence of different variables on the algorithm, and verifies the effectiveness of the above three algorithms.

[1] K. Sylejmani, J. Dorn, and N. Musliu, “Planning the trip itinerary for tourist groups,” Information Technology and Tourism, vol. 17, no. 3, pp. 275–314, Sep. 2017, doi: 10.1007/s40558-017-0080-9.
[2] T. Hashem, T. Hashem, M. E. Ali, and L. Kulik, “Group trip planning queries in spatial databases,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, vol. 8098 LNCS, pp. 259–276. doi: 10.1007/978-3-642-40235-7_15.
[3] A. Husban, “An exact solution method for the MTSP,” Journal of the Operational Research Society, vol. 40, no. 5, pp. 461–469, 1989, doi: 10.1057/jors.1989.73.
[4] Merrill M. Flood, “The Traveling-Salesman Problem,” vol. 4, no. 1, pp. 61–75, 1956.
[5] L. Li, J. Kim, J. Xu, and X. Zhou, “Time-Dependent Route Scheduling on Road Networks.”
[6] Y. Wang, G. Li, and N. Tang, “Querying Shortest Paths on Time Dependent Road Networks,” vol. 12, no. 11, pp. 1249–1261, 2019, doi: 10.14778/3342263.3342265.
[7] P. Bouman, N. Agatz, and M. Schmidt, “Dynamic programming approaches for the traveling salesman problem with drone,” Networks, vol. 72, no. 4, pp. 528–542, 2018, doi: 10.1002/net.21864.
[8] T. Zhou, “TSP problem solution based on improved genetic algorithm,” in Proceedings - 4th International Conference on Natural Computation, ICNC 2008, 2008, vol. 1, pp. 686–690. doi: 10.1109/ICNC.2008.486.
[9] H. Allaoua, “Combination of Genetic Algorithm with Dynamic Programming for Solving TSP,” 2017.
[10] P. Kitjacharoenchai, M. Ventresca, M. Moshref-Javadi, S. Lee, J. M. A. Tanchoco, and P. A. Brunese, “Multiple traveling salesman problem with drones: Mathematical model and heuristic approach,” Computers and Industrial Engineering, vol. 129, pp. 14–30, Mar. 2019, doi: 10.1016/j.cie.2019.01.020.
[11] X. Xu, H. Yuan, M. Liptrott, and M. Trovati, “Two phase heuristic algorithm for the multiple-travelling salesman problem,” Soft Computing, vol. 22, no. 19, pp. 6567–6581, 2018, doi: 10.1007/s00500-017-2705-5.
[12] A. E. Carter and C. T. Ragsdale, “A new approach to solving the multiple traveling salesperson problem using genetic algorithms,” European Journal of Operational Research, vol. 175, no. 1, pp. 246–257, 2006, doi: 10.1016/j.ejor.2005.04.027.
[13] A. A. R. Hosseinabadi, M. Kardgar, M. Shojafar, S. Shamshirband, and A. Abraham, “GELS-GA: Hybrid metaheuristic algorithm for solving Multiple Travelling Salesman Problem,” International Conference on Intelligent Systems Design and Applications, ISDA, vol. 2015-Janua, pp. 76–81, 2015, doi: 10.1109/ISDA.2014.7066271.
[14] S. Yuan, B. Skinner, S. Huang, and D. Liu, “A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms,” European Journal of Operational Research, vol. 228, no. 1, pp. 72–82, 2013, doi: 10.1016/j.ejor.2013.01.043.
[15] P. V. Reddy, A. C. S. Kumar, M. S. Bhat, R. Dhanalakshmi, and P. Parthiban, “Balanced centroids (BC) k-means clustering algorithm to transform MTSP to TSP,” International Journal of Logistics Economics and Globalisation, vol. 2, no. 3, p. 187, 2010, doi: 10.1504/ijleg.2010.036299.
[16] H. L. Xu and C. M. Zhang, “The research about balanced route MTSP based on hybrid algorithm,” in Proceedings of the 2009 International Conference on Communication Software and Networks, ICCSN 2009, 2009, pp. 533–536. doi: 10.1109/ICCSN.2009.115.
[17] K. Sundar and S. Rathinam, “An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem,” in 2015 International Conference on Unmanned Aircraft Systems, ICUAS 2015, Jul. 2015, pp. 366–371. doi: 10.1109/ICUAS.2015.7152311.
[18] W. C. Ng, K. L. Mak, and Y. X. Zhang, “Scheduling trucks in container terminals using a genetic algorithm,” Engineering Optimization, vol. 39, no. 1, pp. 33–47, Jan. 2007, doi: 10.1080/03052150600917128.
[19] J. Li, X. Dai, H. Liu, and M. Zhou, “A decomposition approach to colored traveling salesman problems,” in IEEE International Conference on Automation Science and Engineering, Oct. 2015, vol. 2015-October, pp. 51–56. doi: 10.1109/CoASE.2015.7294040.
[20] J. Li, Q. Sun, M. C. Zhou, X. Yu, and X. Dai, “Colored traveling salesman problem and solution,” in IFAC Proceedings Volumes (IFAC-PapersOnline), Jan. 2014, vol. 19, no. 3, pp. 9575–9580. doi: 10.3182/20140824-6-za-1003.01403.
[21] S. Geetha, P. T. Vanathi, and G. Poonthalir, “Metaheuristic approach for the multi-depot vehicle routing problem,” Applied Artificial Intelligence, vol. 26, no. 9, pp. 878–901, 2012, doi: 10.1080/08839514.2012.727344.
[22] R. Zhang, W. Y. Yun, and H. Kopfer, “Heuristic-based truck scheduling for inland container transportation,” OR Spectrum, vol. 32, no. 3, pp. 787–808, 2010, doi: 10.1007/s00291-010-0193-4.
[23] H. Jula, M. Dessouky, P. Ioannou, and A. Chassiakos, “Container movement by trucks in metropolitan networks: Modeling and optimization,” Transportation Research Part E: Logistics and Transportation Review, vol. 41, no. 3, pp. 235–259, 2005, doi: 10.1016/j.tre.2004.03.003.
[24] V. J. Wei, R. C. W. Wong, and C. Long, “Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Jun. 2020, pp. 1841–1856. doi: 10.1145/3318464.3389718.
[25] S. Sariel-Talay, T. R. Balch, and N. Erdogan, “Multiple traveling robot problem: A solution based on dynamic task selection and robust execution,” IEEE/ASME Transactions on Mechatronics, vol. 14, no. 2, pp. 198–206, 2009, doi: 10.1109/TMECH.2009.2014157.
[26] Y. Rayhan, T. Hashem, R. Jahan, and M. A. Cheema, “Efficient scheduling of generalized group trips in road networks,” ACM Transactions on Spatial Algorithms and Systems, vol. 5, no. 2, 2019, doi: 10.1145/3325915.
[27] A. Orda and R. Rom, “Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length.”
[28] A. Tabassum, S. Barua, T. Hashem, and T. Chowdhury, “Dynamic group trip planning queries in spatial databases,” in ACM International Conference Proceeding Series, Jun. 2017, vol. Part F128636, pp. 1–6. doi: 10.1145/3085504.3085584.
[29] C. Sommer, “Shortest-path queries in static networks,” ACM Computing Surveys, vol. 46, no. 4, pp. 1–31, 2014, doi: 10.1145/2530531.
[30] B. Ding, J. X. Yu, and L. Qin, “Finding time-dependent shortest paths over large graphs,” Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings, pp. 205–216, 2008, doi: 10.1145/1353343.1353371.
[31] L. Li, K. Zheng, S. Wang, W. Hua, and X. Zhou, “Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory,” VLDB Journal, vol. 27, no. 3, pp. 321–345, Jun. 2018, doi: 10.1007/s00778-018-0499-4.
[32] L. Li, W. Hua, X. Du, and X. Zhou, “Minimal On-Road Time Route Scheduling on Time-Dependent Graphs,” 2150.
[33] K. G. Zografos and K. N. Androutsopoulos, “Algorithms for itinerary planning in multimodal transportation networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 9, no. 1, pp. 175–184, 2008, doi: 10.1109/TITS.2008.915650.
[34] A. Idri, M. Oukarfi, A. Boulmakoul, K. Zeitouni, and A. Masri, “A new time-dependent shortest path algorithm for multimodal transportation network,” in Procedia Computer Science, 2017, vol. 109, pp. 692–697. doi: 10.1016/j.procs.2017.05.379.
[35] A. Idri, M. Oukarfi, A. Boulmakoul, K. Zeitouni, and A. Masri, “A distributed approach for shortest path algorithm in dynamic multimodal transportation networks,” Transportation Research Procedia, vol. 27, pp. 294–300, 2017, doi: 10.1016/j.trpro.2017.12.094.
[36] J. J. Miranda-Bront, I. Méndez-Díaz, and P. Zabala, “An integer programming approach for the time-dependent TSP,” Electronic Notes in Discrete Mathematics, vol. 36, no. C, pp. 351–358, Aug. 2010, doi: 10.1016/j.endm.2010.05.045.
[37] L. Federici, A. Zavoli, and G. Colasurdo, “A Time-Dependent TSP Formulation for the Design of an Active Debris Removal Mission using Simulated Annealing,” Sep. 2019, [Online]. Available: http://arxiv.org/abs/1909.10427