本論文提出了單商品收送貨區位途程問題 (one-commodity pickup and delivery location-routing problem; 1-PDLRP) 與單商品收送貨開放式區位途程問題 (one-commodity pickup and delivery open location-routing problem; 1-PDOLRP)，都是區位途程問題 (location-routing problem; LRP) 的延伸問題。在1-PDLRP中，從場站派發的車輛去收集來自顧客的貨品，並配送給對該貨品有需求的顧客，貨品與顧客並無指定配對，而不足的貨品則由場站供給。問題的目標是極小化場站設置成本、車輛的固定成本及配送貨品所需之旅行成本。此問題在現實中有許多運用，例如銀行在各分行的鈔票配送等。由於有些公司不具有自己的車隊，其物流業務外包給第三方的物流公司，本論文進一步延伸1-PDLRP而提出了1-PDOLRP。本論文建構了1-PDLRP和1-PDOLRP的數學模型，並提出模擬退火法 (simulated annealing; SA)以求解這兩個問題。由於這些新問題沒有標準題庫，為此，本研究自LRP的三個知名題庫建立新的1-PDLRP和1-PDOLRP題庫，再以提出的模擬退火法求解LRP、開放式區位途程問題 (open location-routing problem; OLRP)、1-PDLRP和1-PDOLRP。結果顯示，模擬退火法能提供高品質的解及合理的運算時間。本論文並比較封閉式路線和開放式路線的結果，以探討成本節省狀況。

This thesis introduces the one-commodity pickup and delivery location-routing problem (1-PDLRP) and the one-commodity pickup and delivery open location-routing problem (1-PDOLRP), variants of the location-routing problem (LRP), in which customers are divided into pickup customers and delivery customers. The product collected from pickup customers and the depot can be directly supplied to any delivery customer. The objective of these two problems is to minimize a vehicle traveling cost, depot opening cost, and vehicle fixed cost. The proposed problems have many applications in practice, such as cash transportation between branches of banks. Moreover, in the case that companies outsource their logistics activities to third-party logistics (TPL) companies, 1-PDOLRP can be applied. In this thesis, the mixed integer linear programming models for 1-PDLRP and 1-PDOLRP are formulated, and a heuristic approach based on simulated annealing (SA) is proposed to solve these two problems. The proposed SA is tested on the LRP benchmark instances for LRP and the open location-routing problem (OLRP) as well as on new sets of 1-PDLRP and 1-PDOLRP instances that have been modified from those well-known LRP benchmark instances. The computational results indicate that the proposed SA provides competitive results within a reasonable computational time.

Ahn, J., de Weck, O., Geng, Y., & Klabjan, D. (2012). Column generation based heuristics for a generalized location routing problem with profits arising in space exploration. European journal of operational research, 223(1), 47-59.
Albareda-Sambola, M., Fernández, E., & Laporte, G. (2007). Heuristic and lower bound for a stochastic location-routing problem. European journal of operational research, 179(3), 940-955.
Alfa, A. S., Heragu, S. S., & Chen, M. (1991). A 3-opt based simulated annealing algorithm for vehicle routing problems. Computers & Industrial Engineering, 21(1-4), 635-639.
Barreto, S. d. S. (2004). Análise e Modelização de Problemas de localização-distribuição [analysis and modelling of location-routing problem] campus universit' ario de Santiago. (Ph.D. thesis). Aveiro, Portugal: University of Aveiro; 2004.
Caballero, R., González, M., Guerrero, F. M., Molina, J., & Paralera, C. (2007). Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia. European journal of operational research, 177(3), 1751-1763.
Contardo, C., Cordeau, J.-F., & Gendron, B. (2014). A GRASP+ ILP-based metaheuristic for the capacitated location-routing problem. Journal of Heuristics, 20(1), 1-38.
Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2010). A GRASP× ELS approach for the capacitated location-routing problem. Computers & Operations Research, 37(11), 1912-1923.
Escobar, J. W., Linfati, R., Baldoquin, M. G., & Toth, P. (2014). A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem. Transportation Research Part B: Methodological, 67, 344-356.
Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1), 70-79.
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.
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.
Hernández-Pérez, H., Rodríguez-Martín, I., & Salazar-González, J. J. (2009). A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Operations Research, 36(5), 1639-1645.
Hernández-Pérez, H., & Salazar-González, J.-J. (2003). The one-commodity pickup-and-delivery travelling salesman problem Combinatorial Optimization—Eureka, You Shrink! (pp. 89-104): Springer.
Hernández-Pérez, H., & Salazar-González, J.-J. (2004). Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transportation Science, 38(2), 245-255.
Hernández‐Pérez, H., & Salazar‐González, J. J. (2007). The one‐commodity pickup‐and‐delivery traveling salesman problem: Inequalities and algorithms. Networks, 50(4), 258-272.
Hosny, M., & Mumford, C. (2010). Solving the one-commodity pickup and delivery problem using an adaptive hybrid VNS/SA approach. Parallel problem solving from nature, PPSN XI, 189-198.
Hosny, M. I., & Mumford, C. L. (2010). An adaptive hybrid VNS/SA approach to the one-commodity pickup and delivery problem. Proceedings of the 12th annual conference companion on Genetic and evolutionary computation (pp. 2079-2080). Portland, Oregon, USA.
Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2011). A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. European journal of operational research, 211(2), 318-332.
Karaoglan, I., Altiparmak, F., Kara, I., & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Kuo, Y. (2010). Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59(1), 157-165.
Lin, C., & Kwok, R. (2006). Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data. European journal of operational research, 175(3), 1833-1849.
Lin, S.-W., Ying, K.-C., Lee, Z.-J., & Hsi, F.-H. (2006). Applying simulated annealing approach for capacitated vehicle routing problems. Paper presented at the Systems, Man and Cybernetics, 2006. SMC'06. IEEE International Conference on.
Lin, S.-W., & Yu, V. F. (2012). A simulated annealing heuristic for the team orienteering problem with time windows. European journal of operational research, 217(1), 94-107.
Lopes, R. B., Ferreira, C., & Santos, B. S. (2016). A simple and effective evolutionary algorithm for the capacitated location–routing problem. Computers & Operations Research, 70, 155-162.
Lopes, R. B., Plastria, F., Ferreira, C., & Santos, B. S. (2014). Location-arc routing problem: Heuristic approaches and test instances. Computers & Operations Research, 43, 309-317.
Lu, Q., & Dessouky, M. (2004). An exact algorithm for the multiple vehicle pickup and delivery problem. Transportation Science, 38(4), 503-514.
Martinovic, G., Aleksi, I., & Baumgartner, A. (2009). Single-commodity vehicle routing problem with pickup and delivery service. Mathematical Problems in Engineering, 2008.
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.
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
Nagy, G., & Salhi, S. (1996). Nested heuristic methods for the location-routeing problem. Journal of the Operational Research Society, 47(9), 1166-1174.
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: A Quarterly Journal of Operations Research, 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.
Prins, C., Prodhon, C., & Wolfler-Calvo, R. (2004). Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité. MOSIM' 04, 2. France: Lavoisier, Ecole des Mines de Nantes; 2004; 1115-1122. Proceedings of the MOSIM.
Prodhon, C. (2011). A hybrid evolutionary algorithm for the periodic location-routing problem. European journal of operational research, 210(2), 204-212.
Raviv, T., Tzur, M., & Forma, I. A. (2013). Static repositioning in a bike-sharing system: models and solution approaches. EURO Journal on Transportation and Logistics, 2(3), 187-229.
Shi, X., Zhao, F., & Gong, Y. (2009). Genetic algorithm for the one-commodity pickup-and-delivery vehicle routing problem. Proceedings of the Intelligent Computing and Intelligent Systems, 2009. ICIS 2009. (Vol. 1, pp. 175-179).
Su, C.-T. (1999). Dynamic vehicle control and scheduling of a multi-depot physical distribution system. Integrated manufacturing systems, 10(1), 56-65.
Tavakkoli-Moghaddam, R., Safaei, N., & Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 176(2), 445-454.
Ting, C.-J., & Chen, C.-H. (2013). A multiple ant colony optimization algorithm for the capacitated location routing problem. International Journal of Production Economics, 141(1), 34-44.
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.
Wu, T.-H., Low, C., & Bai, J.-W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.
Yu, V. F., & 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.
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.
Yu, V. F., & Lin, S.-Y. (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196.
Zhao, F., Li, S., Sun, J., & Mei, D. (2009). Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. Computers & Industrial Engineering, 56(4), 1642-1648.