臺灣博碩士論文加值系統

本研究以模擬退火法求解同時收送貨之區位途程問題，在供應鏈管理中，如何將使用過的商品回收並再利用是相當重要的議題，因此，近年來產業和研究者都非常重視同時收送貨之區位途程問題。同時收送貨之區位途程問題考量配送新商品及零件給顧客、收取需要回收及維修的商品與選擇設施的位址，在這樣的配送網路裡，必須同時滿足每個顧客的收貨和送貨兩種需求。我們提出模擬退火法以求解此問題，並以四個小型及中型的標竿題組作測試，實驗結果顯示，我們所提出的模擬退火法在解的品質與計算效率上都優於現有的演算法。此外，我們在此研究中產生四個大型的題組，並以所提出的模擬退火法求解，也得到不錯的結果。

This study proposes a simulated annealing (SA) heuristic for the location routing problem with simultaneous pickup and delivery (LRPSPD). How to recycle and reuse used products has become an important issue in supply chain management, and thus the LRPSPD has received much attention from the industry and researchers recently. The LRPSPD considers the distribution of parts and new products, the collection of recycled products and products to be repaired, and the locations of facilities. In such a distribution network, each customer has both pickup and delivery demands that need to be satisfied simultaneously. We propose an SA heuristic for the LRPSPD and test it on four sets of small- and medium-size LRPSPD benchmark instances. The results indicate that the proposed SA heuristic outperforms existing approaches in both computational time and solution quality. In addition, another four sets of large LRPSPD instances are generated and solved by the proposed SA heuristic with satisfactory results.

ABSTRACT .................................................................................................................. I
ACKNOWLEDGEMENT ........................................................................................... II
TABLE OF CONTENTS ........................................................................................... III
LIST OF FIGURES ......................................................................................................V
LIST OF TABLES...................................................................................................... VI
Chapter 1 INTRODUCTION ....................................................................................... 1
1.1. Research Background and Motivation..................................................................... 1
1.2. Purpose of Research................................................................................................. 2
1.3. Research Framework ............................................................................................... 3
Chapter 2 LITERATURE REVIEW ............................................................................. 4
2.1. Vehicle Routing Problem with Simultaneous Pickup and Delivery ......................... 5
2.2. Location Routing Problem ....................................................................................... 6
2.3. Location Routing Problem with Simultaneous Pickup and Delivery ................ 7
2.4. Simulated Annealing .............................................................................................. 7
Chapter 3 PROBLEM DEFINITION ........................................................................ 8
Chapter 4 SOLUTION METHODOLOGY ............................................................ 12
4.1. Solution Representation ...................................................................................... 12
4.2. Initial Solution ...................................................................................................... 16
4.3. Neighborhood Search .......................................................................................... 17
4.4. The Simulated Annealing Procedure ................................................................. 20
Chapter 5 COMPUTATIONAL STUDY ................................................................ 22
5.1. Test Instances ....................................................................................................... 22
5.2. Separation Approaches ........................................................................................ 25
5.3. Parameter Setting ................................................................................................ 27
5.4. Comparative Results ............................................................................................ 28
Chapter 6 CONCLUSION AND FURTHER RESEARCH ................................... 37
6.1. Conclusion ............................................................................................................ 37
6.2. Further Research ................................................................................................. 37

Aksen, D., & Altinkemer, K. (2008). A location-routing problem for the conversion to the “click-and-mortar” retailing: The static case. European Journal of Operational Research, 186(2), 554-575.
Andel, T. (1997). Reverse logistics: a second chance to profit: whether through refurbishment or recycling, companies are finding profit in returned products. Transportation & Distribution, 38(7), 61-64.
Angelelli, E., & Mansini, R. (2002). The vehicle routing problem with time windows and simultaneous pick-up and delivery. In A. Klose, M. G. Speranza & L. N. Van Wassenhove (Eds.), Quantitative Approaches to Distribution Logistics and Supply Chain Management. (pp. 249-267): Springer.
Barreto, S. S. (2004). Analise e Modelizacao de Problemas de localizacao-distribuicao [Analysis and Modelling of Location-routing Problems]. Ph.D. Thesis, University of Aveiro, Aveiro, Portugal.
Catay, B. (2010). A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Expert Systems with Applications, 37(10), 6809-6817.
Christofides, N. (1979). The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth & C. Sandi (Eds.), Combinatorial Optimization. (pp. 315-338). Chichester: Wiley.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operation Research, 12(4), 568-581.
Derbel, H., Jarboui, B., Hanafi, S., & Chabchoub, H. (2012). Genetic algorithm with iterated local search for solving a location-routing problem. Expert Syst. Appl., 39(3), 2865-2871.
Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick up. OR Spectrum, 23(1), 79-96.
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.
Gajpal, Y., & Abad, P. (2009). An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research, 36(12), 3215-3223.
Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53.
Jacobsen, S. K., & Madsen, O. B. G. (1980). A comparative study of heuristics for a two-level routing-location problem. European Journal of Operational Research, 5(6), 378-387.
Jeong, C.-S., & Kim, M.-H. (1991). Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections. Parallel Computing, 12(2-3), 221-228.
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 Jr., C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680.
Laporte, G., Nobert, Y., & Arpin, D. (1986). An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research, 6(9), 293-310.
Lin, C. K. Y., Chow, C. K., & Chen, A. (2002). A location-routing-loading problem for bill delivery services. Computers & Industrial Engineering, 43(1-2), 5-25.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling salesman problem. Operation Research, 21, 498-516.
Liu, S. C., & Lee, S. B. (2003). A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration. The International Journal of Advanced Manufacturing Technology, 22(11-12), 941-950.
Madsen, O. B. G. (1983). Methods for solving combined two level location-routing problems of realistic dimensions. European Journal of Operational Research, 12(3), 295-301.
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.
Min, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), 377-386.
Murty, K. G., & Djang, P. A. (1999). The U.S. army national guard's mobile training simulators location and routing problem. Operation Research, 47(2), 175-182.
Nguyen, V.-P., Prins, C., & Prodhon, C. (2012). 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.
Osman, I., & Potts, C. (2003). Simulated Annealing for the Permutation Flowshop Problem. Omega, 17(6), 551-557.
Osman, I. H., & Wassan, N. A. (2002). A reactive tabu search meta-heuristic for the vehicle routing problem with back‐hauls. Journal of Scheduling, 5(4), 263-285.
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., & Wolfler Calvo, R. (2004). Nouveaux algorithmes pour le probleme de localisation et routage sous contraintes de capacite. Proceedings of the MOSIM' 04 (pp. 1115-1122). 2, Lavoisier, Ecole des Mines de Nantes, France.
Salhi, S., & Nagy, G. (1999). A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling. The Journal of the Operational Research Society, 50(10), 1034-1042.
Seckiner, S. U., & Kurt, M. (2007). A simulated annealing approach to the solution of job rotation scheduling problems. Applied Mathematics and Computation, 188(1), 31-45.
Sofianopoulou, S. (1992). Simulated annealing applied to the process allocation problem. European Journal of Operational Research, 60(3), 327-334.
Subramanian, A., Uchoa, E., Pessoa, A. A., & Ochi, L. S. (2011). Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39(5), 338-341.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116, 87-99.
Wassan, N. A., Wassan, A. H., & Nagy, G. (2007). A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries. Journal of Combinatorial Optimization, 15(4), 368-386.
Watson-Gandy, C., & Dohrn, P. (1973). Depot location with van salesman - a practical approach. Omega, 1(3), 321-329.
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., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.