本研究提出了具多轉運站與整合型正逆物流之異質性車輛途程問題(The Heterogeneous Fleet Vehicle Routing Problem with Multiple Cross-docks and Integrated Forward and Reverse Flow; HF-VRPMFRCD)，為具越庫作業之車輛途程問題(Vehicle Routing Problem with Cross-docking; VRPCD)之延伸問題，於配送系統中考量了多個轉運站、異質性車輛與正逆向物流。本研究為所提問題建構了一混合整數線性規劃模型，其目標為最小化總運輸成本，包含收貨、同時收送貨、送貨，與兩轉運過程的旅行距離成本。本研究提出模擬退火法(Simulated Annealing; SA)與混合模擬退火法兩個啟發式演算法求解此問題，此混合模擬退火法是以SA為基本架構，加入變動鄰域搜尋(Variable Neighborhood Search; VNS)做為區域搜尋法，因此稱其為SAVNS演算法。由於HF-VRPMFRCD為一個新的問題，本研究修改具多轉運站之異質性車輛途程問題(Heterogeneous Fleet Vehicle Routing Problem with Multiple Cross-docks)的題庫來建立一個HF-VRPMFRCD題庫，以驗證演算法之效率，測試結果顯示所提之SA可在短時間內求解小型題庫，而SAVNS則在求解大型題庫上具有優勢。

This research proposes and formulates a new variant of the vehicle routing problem with cross-docking (VRPCD) called the heterogeneous fleet vehicle routing problem with multiple cross-docks and integrated forward and reverse flow (HF-VRPMFRCD), which considers the use of multiple cross-docks, a heterogeneous fleet of vehicles and forward and reverse logistics in a distribution system. A mixed integer linear program is developed for the problem. The objective is to minimize the total costs, including the transportation costs of pickup, simultaneous pickup and delivery, delivery, and two transfer processes. Two metaheuristics, simulated annealing (SA) algorithm and hybrid simulated annealing algorithm, are also developed for the problem. The hybrid metaheuristic called SAVNS is based on SA and includes variable neighborhood search as a local search mechanism. Since this problem has not been studied in the literature yet, a HF-VRPMFRCD benchmark dataset adapted from the benchmark instances of the Heterogeneous Fleet Vehicle Routing Problem with Multiple Cross-docks is generated in the study to test the performance of the proposed algorithm. Results of computational study show high computational efficiency of SA in solving small instances and advantages of SAVNS in solving large instances.

Agustina, D., Lee, C., & Piplani, R. (2010). A review: mathematical modles for cross docking planning. International Journal of Engineering Business Management, 2(2), 47-54.
Ahkamiraad, A., & Wang, Y. (2018). Capacitated and multiple cross-docked vehicle routing problem with pickup, delivery, and time windows. Computers & Industrial Engineering, 119, 76-84.
Ahmadizar, F., Zeynivand, M., & Arkat, J. (2015). Two-level vehicle routing with cross-docking in a three-echelon supply chain: A genetic algorithm approach. Applied Mathematical Modelling, 39(22), 7065-7081.
Amini, A., & Tavakkoli-Moghaddam, R. (2016). A bi-objective truck scheduling problem in a cross-docking center with probability of breakdown for trucks. Computers & Industrial Engineering, 96, 180-191.
Baldacci, R., Battarra, M., & Vigo, D. (2008). Routing a heterogeneous fleet of vehicles. In B. Golden, S. Raghavan, & E. Wasil (Eds.), The vehicle routing problem: latest advances and new challenges (pp. 3-27). New York, USA: Springer.
Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), 347-380.
Brandão, J. (2011). A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem. Computers & Operations Research, 38(1), 140-151.
Catoni, O. (1998). Solving scheduling problems by simulated annealing. SIAM Journal on Control Optimization, 36(5), 1539-1575.
Chen, M.C., Hsiao, Y.H., Reddy, R.H., & Tiwari, M.K. (2016). The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks. Transportation Research Part E: Logistics Transportation Review, 91, 208-226.
De Brito, M.P., & Dekker, R. (2004). A framework for reverse logistics. In R. Dekker, M. Fleischmann, K. Inderfurth, & L. N. V. Wassenhove (Eds.), Reverse Logistics (pp. 3-27). New York, USA: Springer.
Dhahri, A., Mjirda, A., Zidi, K., & Ghedira, K. (2016). A VNS-based heuristic for solving the vehicle routing problem with time windows and vehicle preventive maintenance constraints. Procedia Computer Science, 80, 1212-1222.
Dondo, R., & Cerdá, J. (2015). The heterogeneous vehicle routing and truck scheduling problem in a multi-door cross-dock system. Computers & Chemical Engineering, 76, 42-62.
Golden, B., Assad, A., Levy, L., & Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1), 49-66.
Grellier, E., Dejax, P., Jussien, N., & Lu, Z. A multiperiodic vehicle routing problem in the context of reverse logistics: A modeling framework. Paper presented at the The International Conference on Information System, Logistics and Supply Chain, Lyon, France, May, 2006.
Guastaroba, G., Speranza, M.G., & Vigo, D. (2016). Intermediate facilities in freight transportation planning: A survey. Transportation Science, 50(3), 763-789.
Gunawan, A., Widjaja, A.T., Vansteenwegen, P., & Yu, V.F. Vehicle routing problem with reverse cross-docking: An adaptive large neighborhood search algorithm. Paper presented at the International Conference on Computational Logistics, Enschede, The Netherlands, September, 2020.
Hermel, D., Hasheminia, H., Adler, N., & Fry, M.J. (2016). A solution framework for the multi-mode resource-constrained cross-dock scheduling problem. Omega, 59, 157-170.
Jiang, J., Ng, K.M., Poh, K.L., & Teo, K.M. (2014). Vehicle routing problem with a heterogeneous fleet and time windows. Expert Systems with Applications, 41(8), 3748-3760.
Kassem, S., & Chen, M. (2013). Solving reverse logistics vehicle routing problems with time windows. The International Journal of Advanced Manufacturing Technology, 68(1-4), 57-68.
Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Lee, Y.H., Jung, J.W., & Lee, K.M. (2006). Vehicle routing scheduling for cross-docking in the supply chain. Computers & Industrial Engineering, 51(2), 247-256.
Li, F., Golden, B., & Wasil, E. (2007). A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 34(9), 2734-2742.
Liao, C.J., Lin, Y., & Shih, S.C. (2010). Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications, 37(10), 6868-6873.
Maknoon, M., & Laporte, G. (2017). Vehicle routing with cross-dock selection. Computers & Operations Research, 77, 254-266.
Maknoon, M., Soumis, F., & Baptiste, P. (2016). Optimizing transshipment workloads in less-than-truckload cross-docks. International Journal of Production Economics, 179, 90-100.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), 1087-1092.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097-1100.
Mohtashami, A. (2015). A novel dynamic genetic algorithm-based method for vehicle scheduling in cross docking systems with frequent unloading operation. Computers & Industrial Engineering, 90, 221-240.
Moutaoukil, A., Neubert, G., & Derrouiche, R. A comparison of homogeneous and heterogeneous vehicle fleet size in green vehicle routing problem. Paper presented at the IFIP International Conference on Advances in Production Management Systems, Ajaccio, France, September, 2014.
Muelas, S., LaTorre, A., & Pena, J.M. (2015). A distributed VNS algorithm for optimizing dial-a-ride problems in large-scale scenarios. Transportation Research Part C: Emerging Technologies, 54, 110-130.
Musa, R., Arnaout, J.P., & Jung, H. (2010). Ant colony optimization algorithm to solve for the transportation problem of cross-docking network. Computers & Industrial Engineering, 59(1), 85-92.
Nikolopoulou, A.I., Repoussis, P.P., Tarantilis, C.D., & Zachariadis, E.E. (2019). Adaptive memory programming for the many-to-many vehicle routing problem with cross-docking. Operational Research, 19(1), 1-38.
Prins, C. (2009). Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, 22(6), 916-928.
Rao, R.J. (2016). A simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 7(1), 19-34.
Redi, A., Jewpanya, P., Kurniawan, A.C., Persada, S.F., Nadlifatin, R., & Dewi, O.A.C. (2020). A simulated annealing algorithm for solving two-echelon vehicle routing problem with locker facilities. Algorithms, 13(9), 218.
Rezaei, S., & Kheirkhah, A. (2017). Applying forward and reverse cross-docking in a multi-product integrated supply chain network. Production Engineering, 11(4), 495-509.
Santos, F.A., Mateus, G.R., & Da Cunha, A.S. (2013). The pickup and delivery problem with cross-docking. Computers & Operations Research, 40(4), 1085-1093.
Savelsbergh, M.W., & Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29(1), 17-29.
Selim, S.Z., & Alsultan, K. (1991). A simulated annealing algorithm for the clustering problem. Pattern Recognition, 24(10), 1003-1008.
Sevkli, M., & Aydin, M.E. A variable neighbourhood search algorithm for job shop scheduling problems. Paper presented at the European Conference on Evolutionary Computation in Combinatorial Optimization, Budapest, Hungary, April, 2006.
Subramanian, A., Penna, P.H.V., Uchoa, E., & Ochi, L.S. (2012). A hybrid algorithm for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 221(2), 285-295.
Taillard, É.D. (1999). A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Operations Research-Recherche Opérationnelle, 33(1), 1-14.
Van Belle, J., Valckenaers, P., & Cattrysse, D. (2012). Cross-docking: State of the art. Omega, 40(6), 827-846.
Wang, C., Zhao, F., Mu, D., & Sutherland, J.W. Simulated annealing for a vehicle routing problem with simultaneous pickup-delivery and time windows. Paper presented at the IFIP International Conference on Advances in Production Management Systems, Pennsylvania, USA, September, 2013.
Wang, Z., Geng, X., & Shao, Z. (2009). An effective simulated annealing algorithm for solving the traveling salesman problem. Journal of Computational Theoretical Nanoscience, 6(7), 1680-1686.
Yan, H., & Tang, S. (2009). Pre-distribution and post-distribution cross-docking operations. Transportation Research Part E: Logistics Transportation Review, 45(6), 843-859.
Yu, V.F., Jewpanya, P., & Redi, A.P. (2014). A simulated annealing heuristic for the vehicle routing problem with cross-docking. In P. Golinska (Ed.), Logistics Operations, Supply Chain Management and Sustainability (pp. 575-584). Switzerland: Springer.
Yu, V.F., Jewpanya, P., & Redi, A.P. (2016). Open vehicle routing problem with cross-docking. Computers & Industrial Engineering, 94, 6-17.
Yu, V.F., Jewpanya, P., Redi, A.P., & Tsao, Y.C. (2021). Adaptive neighborhood simulated annealing for the heterogeneous fleet vehicle routing problem with multiple cross-docks. Computers & Operations Research, 129, 105205.
Yu, W., & Egbelu, P.J. (2008). Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. European Journal of Operational Research, 184(1), 377-396.
Zhang, M., Pratap, S., Zhao, Z., Prajapati, D., & Huang, G.Q. (2020). Forward and reverse logistics vehicle routing problems with time horizons in B2C e-commerce logistics. International Journal of Production Research, 1-20.