本研究中提出了一個著重城市物流的二階層動態衛星路徑規劃問題（2E-LRPDS）。此問題之主要創新在於以卡車作為動態衛星，將固定衛星從典型的二階層路徑規劃問題（2E-LRP）中取代。在這項研究中，我們利用禁忌搜索演算法結合K-means來解決2E-LRPDS問題，並使用Prodhon設計之2E-LRP基準問題集測試此模型。其結果顯示，在大型實例中，本研究所提出的模型優於原始的2E-LRP模型，且在問題越複雜的情況下，路徑成本節省越多。另外，本研究透過田口實驗獲得最佳參數設置，其配置之最佳參數能夠降低總成本的平均值和變異數。

In this paper, we proposed a new two-echelon location routing problem with dynamic satellites (2E-LRPDS) problem which focus on city logistics. The main innovation of this work is replacing the fix satellites from typical two-echelon location routing problem (2E-LRP) and utilize the truck as dynamic satellites. In this research, a combined Tabu Search with K-means was utilized to solve 2E-LRPDS problem. The proposed model is tested on the 2E-LRP Prodhon benchmark instances. The result shows that the proposed model outperforms the original 2E-LRP models in large instances. The more complicated the problems is, the higher the cost-savings the proposed model can produce. A Taguchi experiments were simulated to obtain the best setting of parameters. As the results, the best-configured parameters reduce both the average and the variance of the total costs.

Alinaghian, M., Kaviani, Z., & Khaledan, S. (2015). A novel heuristic algorithm based on clark and wright algorithm for green vehicle routing problem. International Journal of Supply and Operations Management, 2(2), 784.
Altınel, İ. K., & Öncan, T. (2005). A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Journal of the Operational Research Society, 56(8), 954-961.
Amarouche, Y., Guibadj, R. N., & Moukrim, A. (2018). A neighborhood search and set cover hybrid heuristic for the two-echelon vehicle routing problem. Paper presented at the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018).
Andrews, N. O., & Fox, E. A. (2007). Recent developments in document clustering. Retrieved from
Baker, B. M., & Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
Balinski, M. L., & Quandt, R. E. (1964). On an integer program for a delivery problem. Operations Research, 12(2), 300-304.
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069-1072.
Belgin, O., Karaoglan, I., & Altiparmak, F. (2018). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115, 1-16.
Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I., & Laporte, G. (2007). Static pickup and delivery problems: a classification scheme and survey. Top, 15(1), 1-31.
Bertsimas, D. J. (1992). A Vehicle Routing Problem with Stochastic Demand. Operations Research, 40(3), 574-585.
Boccia, M., Crainic, T. G., Sforza, A., & Sterle, C. (2010). A metaheuristic for a two echelon location-routing problem. Paper presented at the International Symposium on Experimental Algorithms.
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved Ant System algorithm for theVehicle Routing Problem. Annals of operations research, 89(0), 319-328. doi:10.1023/a:1018940026670
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309-318.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581.
Connor, A., & Shea, K. (2016). A comparison of semi-deterministic and stochastic search techniques.
Contardo, C., Cordeau, J.-F., & Gendron, B. (2013). An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS Journal on Computing, 26(1), 88-102.
Contardo, C., Hemmelmayr, V., & Crainic, T. G. (2012). Lower and upper bounds for the two-echelon capacitated location-routing problem. Computers & Operations Research, 39(12), 3185-3199.
Crainic, T. G., Mancini, S., Perboli, G., & Tadei, R. (2008). Clustering-based heuristics for the two-echelon vehicle routing problem (Vol. 46): CIRRELT Montréal.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80-91. doi:10.1287/mnsc.6.1.80
Del Pia, A., & Filippi, C. (2006). A variable neighborhood descent algorithm for a real waste collection problem with mobile depots. International Transactions in Operational Research, 13(2), 125-141.
Dell'Amico, M., & Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of operations research, 41(3), 231-252.
Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342-354.
Desrosiers, J., Dumas, Y., & Soumis, F. (1986). A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows. American Journal of Mathematical and Management Sciences, 6(3-4), 301-325.
Eilon, S., Watson-Gandy, C. D. T., Christofides, N., & de Neufville, R. (1974). Distribution management-mathematical modelling and practical analysis. IEEE Transactions on Systems, Man, and Cybernetics(6), 589-589.
Fisher, M. L. (1994). Optimal solution of vehicle routing problems using minimum k-trees. Operations Research, 42(4), 626-642.
Gaskell, T. (1967). Bases for vehicle fleet scheduling. Journal of the Operational Research Society, 18(3), 281-295.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.
Ghaffari-Nasab, N., Ahari, S. G., & Ghazanfari, M. (2013). A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands. Scientia Iranica, 20(3), 919-930.
Glover, F. (1989). Tabu Search—Part I. ORSA Journal on Computing, 1(3), 190-206. doi:10.1287/ijoc.1.3.190
Gonzalez-Feliu, J., Perboli, G., Tadei, R., & Vigo, D. (2008). The two-echelon capacitated vehicle routing problem.
Hauder, V. A., Karder, J., Beham, A., Wagner, S., & Affenzeller, M. (2018). A General Solution Approach for the Location Routing Problem, Cham.
He, P., & Li, J. (2019). The two-echelon multi-trip vehicle routing problem with dynamic satellites for crop harvesting and transportation. Applied soft computing, 77, 387-398.
Hemmelmayr, V. C., Cordeau, J.-F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
Hertz, A., & de Werra, D. (1987). Using tabu search techniques for graph coloring. Computing, 39(4), 345-351.
Jacobsen, S. K., & Madsen, O. B. (1980). A comparative study of heuristics for a two-level routing-location problem. European journal of operational research, 5(6), 378-387.
Jain, A. K. (2010). Data clustering: 50 years beyond K-means. Pattern recognition letters, 31(8), 651-666.
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(4‐5), 285-300. doi:10.1111/j.1475-3995.2000.tb00200.x
Laporte, G., & Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European journal of operational research, 6(2), 224-226.
Laporte, G., & Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. Operations-Research-Spektrum, 5(2), 77-85. doi:10.1007/bf01720015
Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem North-Holland Mathematics Studies (Vol. 132, pp. 147-184): Elsevier.
Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93-110.
Lin, J.-R., & Lei, H.-C. (2009). Distribution systems design with two-level routing considerations. Annals of operations research, 172(1), 329.
Lin, Y.-K., Yeh, C.-T., & Huang, P.-S. (2013). A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem (Vol. 13).
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Paper presented at the Proceedings of the fifth Berkeley symposium on mathematical statistics and probability.
Manzour-al-Ajdad, S., Torabi, S. A., & Salhi, S. (2012). A hierarchical algorithm for the planar single-facility location routing problem. Computers & Operations Research, 39(2), 461-470.
Maranzana, F. (1964). On the location of supply points to minimize transport costs. Journal of the Operational Research Society, 15(3), 261-270.
Mehrjerdi, Y. Z. (2012). Vehicle routing problem: meta-heuristic approaches. International Journal of Applied Operational Research, 2(3), 55-68.
Nguyen, V.-P., Prins, C., & Prodhon, C. (2012a). A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem. Engineering Applications of Artificial Intelligence, 25(1), 56-71.
Nguyen, V.-P., Prins, C., & Prodhon, C. (2012b). Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking. European journal of operational research, 216(1), 113-126.
Normasari, N. M. E., Yu, V. F., & Bachtiyar, C. (2019). A Simulated Annealing Heuristic for the Capacitated Green Vehicle Routing Problem. Mathematical Problems in Engineering, 2019.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41(4), 421-451.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(1), 21-51.
Polmar, N. (2006). Aircraft Carriers: A History of Carrier Aviation and Its Influence on World Events, Volume I: 1909-1945 (Vol. 1): Potomac Books, Inc.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002.
Prins, C., Prodhon, C., & Calvo, R. W. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3), 221-238.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R. (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science, 41(4), 470-483.
Prodhon, C. (2010). Instances for LRP-2E.
Prodhon, C., & Prins, C. (2014). A survey of recent research on location-routing problems. European journal of operational research, 238(1), 1-17.
Psaraftis, H. N. (1980). A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 14(2), 130-154.
Rath, S., & Gutjahr, W. J. (2014). A math-heuristic for the warehouse location–routing problem in disaster relief. Computers & Operations Research, 42, 25-39.
Schwengerer, M., Pirkwieser, S., & Raidl, G. R. (2012). A variable neighborhood search approach for the two-echelon location-routing problem. Paper presented at the European Conference on Evolutionary Computation in Combinatorial Optimization.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265.
Soysal, M., Bloemhof-Ruwaard, J. M., & Bektaş, T. (2015). The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, 366-378.
Steinhaus, H. (1956). Sur la division des corp materiels en parties. Bull. Acad. Polon. Sci, 1(804), 801.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J.-Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2), 170-186.
Toth, P., & Vigo, D. (2002). The vehicle routing problem: SIAM.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European journal of operational research, 116(1), 87-99.
Vincent, F. Y., & Lin, S.-W. (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied soft computing, 24, 284-290.
Xu, J., Chiu, S. Y., & Glover, F. (1996). Probabilistic tabu search for telecommunications network design. Combinatorial Optimization: Theory and Practice, 1(1), 69-94.
Yang, C. L., Sutrisno, H., Chan, A. S., & Wibowo, B. S. (2018). The two-echelon vehicle routing problem with dynamic satellites for city logistics. Paper presented at the Proceedings of International Conference on Computers and Industrial Engineering, CIE.