區位途程問題包含設施區位選擇問題與車輛途程兩個交互影響的決策。傳統上，利用先分群再排程方法求解區位途程問題時按以下三個步驟進行：形成集群、路線排程、選擇路線出發位置，過去研究多分別處理形成集群和路線排程。本研究提出一新方法，在形成集群階段篩選出候選需求點，這些候選需求點究竟應該安排在哪一個集群則由路線排程階段決定，若改變其所屬集群可以降低總行駛距離，則重新調整候選需求點之所屬集群。
為評估此新方法對於不同形成集群方法的影響程度，因此本研究在集群形成階段採用兩種最常使用的分群法：簡單法及K平均數集群法。經由測試標準範例後，發現簡單法結合本研究之改善方法的表現優於K平均數集群法結合本改善方法。透過歸納，當需求點所處位置與其他相鄰分群所屬需求點較近時，本研究所提出之改善方法可以減少總路線距離，進而降低成本。

The Location-Routing Problem includes the decisions of the Facility-Location Problem and the Vehicle-Routing Problem. Traditionally, the procedure of the cluster-first, route-second approach to solve the capacitated Location-Routing Problem is as follows: cluster construction, cluster route scheduling, and route assignment. In this study, candidate customers are selected in the cluster construction stage, and if the total distance can be reduced by switching from its original cluster to the neighboring cluster, we re-adjust them during the cluster route scheduling stage. In order to compare the influence of this improvement method, this study tests two commonly used clustering methods during the cluster construction stage: the Simple Clustering Method and the K-means Clustering Method. Our experimental results show that the performance of the Simple Clustering Method is superior to the K-means Clustering Method when the two clustering methods are combined with the improvement method this study proposes. We conclude that when a customer is closer to an adjacent point belongings to another cluster, using the improvement method proposed in this study, we can reduce travel distance and cost.

1. Balakrishnan, A., Ward, J. E., & Wong, R. T. (1987). Integrated facility location and vehicle routing models: Recent work and future prospects. American Journal of Mathematical and Management Sciences, 7, 35-61.
2. Barreto, S. r., Ferreira, C., Paixa˜o, J., & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3), 968-977.
3. Barreto, S. S., Ferreira, C. M., & Paixa˜o, J. M. (2003). Using clustering analysis in a capacitated location-routing problem. Paper presented at the Communication presented at XIV Meeting of the European Working Group on Locational Analysis, Corfu, Greece.
4. Beasley, J. (1983). Route-first cluster-second methods for vehicle routing. Omega, 11(4), 403-408.
5. Bodin, L. D., Goldern, B. L., Assad, A. A., & Ball, M. O. (1983). Routing and shceduling of vehicles and crews. The State of the Art. Computers and Operations Research, 10, 63-211.
6. Boudahri, F., Aggoune-Mtalaa, W., Bennekrouf, M., & Sari, Z. (2013). Application of a clustering based location-routing model to a real agri-food supply chain redesign. In N. T. Nguyen, B. Trawinski, R. Katarzyniak, & G.-S. Jo (Eds.), Advanced methods for computational collective intelligence, 323-331.
7. Church, R. L., & Revelle, C. (1974). The Maximal Covering Location Problem. Papers of the Regional Science Association, 32, 101-118.
8. Daskin, M., & Mark, S. (1995). Network and Discrete Location: JOHN WILEY & SONs, Inc.
9. Geetha, S., Poonthalir, G., & Vanathi, P. T. (2009). Improved K-Means Algorithm for Capacitated Clustering Problem. International INFOCOMP Journal of Computer Science, 8(4).
10. Güler, B., & Şevkli, A. Z. (2015). Oscillated Variable Neighborhood Search for Open Vehicle Routing Problem. Paper presented at the Neural Information Processing.
11. Hiquebran, D. T., Alfa, A. S., Shapiro, J. A., & Gittoes, D. H. (2007). Cluster-first route-second algorithm applied to the vehicle routing problem. Engineering Optimization, 22(2).
12. Jain, A. K., & Dubes, R. C. (1988). Algorithms for Clustering Data. New Jersey: Prentice Hall.
13. Lai, D. S. W., Demirag, O. C., & Leung, J. M. Y. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E, 86, 32-52.
14. Laporte, G., Gendreau, M., Potvin, J.-Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7, 285-300.
15. Larson, R. C., & Odoni, A. R. (1981). Urban Operation Research. Prentice-Hall.
16. Mehrjerdi, Y. Z., & Nadizadeh, A. (2013). Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. European Journal of Operational Research, 229.
17. Mole, R., Johnson, D., & Wells, K. (1983). Combinatorial analysis for route first-cluster second vehicle routing. Omega, 11(5), 507-512.
18. Nadizadeh, A., Sadegheih, A., & Zadeh, A. S. (2017). A hybrid heuristic algorithm to solve capacitated location-routing problem with fuzzy demands. International Journal of Industrial Mathematics, 9(1), 1-20.
19. Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
20. Oudouar, F., & Fellahi, A. E. (2017). Solving the location-routing problems using clustering method. Paper presented at the Proceedings of the 2nd international Conference on Big Data, Cloud and Applications, Tetouan, Morocco.
21. Owen, S. H., & Daskin, M. S. (1998). Strategic facility location: A review. European Journal of Operational Research, 111, 423-447.
22. Perl, J., & Daskin, M. S. (1985). A warehouse location-routing problem. Transportation Research Part B-Methodological, 19(5), 381-396.
23. Polimeni, A., & Vitetta, A. (2014). Vehicle routing in urban areas: an optimal approach with cost function calibration. Transportmetrica B: Transport Dynamics, 2(1), 1-19.
24. Prins, C., Prodhon, C., & Wolfler-Calvo, R. (2006). Solving the Capacitated Location-Routing Problem by a GRASP complemented by a Learning Process and a Path Relinking. A Quarterly Journal of Operations Research, 4(3), 221-238.
25. Rand, G. K. (1976). Methodological choices in depot location studies. Operational Research Quarterly, 27, 241-249.
26. Russell, R. S., & Taylor, B. W. (2011). Operation management/ Roberta S. Russell, Bernard W. Taylor ||| (7th ed.): Chichester, John Wiley.
27. Salhi, S., & Nagy, G. (1999). Consistency and robustness in location routing. Studies in Locational Analysis, 13, 3-19.
28. Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39, 150-156.
29. Savaser, S. (2017). Periodic location routing problem: An application of mobile health services in rural areas. (Master), Bilkent University.
30. Shin, K., & Han, S. (2011). A centroid-based heuristic algorithm for the capacitated vehicle routing problem. Computing and Informatics, 30, 721-732.
31. Toregas, C. (1971). The Location of Emergency Service Facilities. Operational Research, 19(6), 1363-1373.
32. Tuzun, D., & L., B. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 166, 87-99.
33. Villegas, J. G., Prins, C., Prodhon, C., Medaglia, A. L., & Velasco, N. (2011). A GRASP with evolutionary path relinking for the truck and trailer routing problem. Computer and Opearation Research, 38(9), 1319-1334.
34. Wangab, X., & Li, X. (2017). Carbon reduction in the location routing problem with heterogeneous fleet, simultaneous pickup-delivery and time windows. Procedia Computer Science, 112, 1131-1140.
35. Yu, V. F., Redi, A. A. N. P., Hidayat, Y. A., & Wibowo, O. J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132.
36. Zarandi, M. H. F., Hemmati, A., Davari, S., & Turksen, I. B. (2013). Capacitated location-routing problem with time windows under uncertainty. Knowledge-Based Systems, 37, 480-489.