臺灣博碩士論文加值系統

本研究介紹了考慮時變需求之區位途程問題(Location Routing Problem with Time-Dependent Demand；LRPTDD)，其藉由考慮了每一個節點在其生產週期內依照固定比率所產生的需求量來延伸區位途程問題(Location Routing Problem；LRP)。本問題的目標是設計出一組車輛的途程來滿足每一個節點所累積的需求量之收貨作業，並最小化其總途程成本、場站開設成本以及車量使用成本。每一次的收貨數量取決於車輛到達該節點的時間，此為本問題之時變性質。本研究提出了一個混整數非線性規劃(Mixed-Integer Non-Linear Programming；MINLP)模型，並且以模擬退火法(Simulated Annealing；SA)來求解問題。實驗結果顯示，本研究所提出之SA演算法，在求解LRP題庫上較其它已知的演算法更具競爭力，最重要的是，在求解LRPTDD的例題時有很好的效率。

This research introduces the location routing problem with time-dependent demand (LRPTDD) which extends the location routing problem by considering the demand flowing at a constant rate over a known production period associated to each customer site. The objective is to design a set of vehicle tours to pick the accumulated demands at the sites while minimizing the sum of routing cost, depot cost, and vehicle utility cost. The pick load depends on the vehicle’s arrival time at the site. This is the “time dependency” nature of our problem. A mixed-integer non-linear programming (MINLP) formulation is presented. This research develops a Simulated Annealing (SA) algorithm for the LRPTDD. The computational study demonstrates the competitiveness of the proposed SA heuristic against other well-known algorithms used for LRP instances and most importantly, its effectiveness for the LRPTDD instances.

CHINESE ABSTRACT I
ENGLISH ABSTRACT II
ACKNOWLEDGMENT III
TABLE OF CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES VII
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Objective 3
1.3 Research contribution 4
1.4 Organization of Thesis 4
CHAPTER 2 LITERATURE REVIEW 5
2.1 Location Routing Problem 5
2.2 LRP solution approaches 5
2.3 Simulated Annealing 7
CHAPTER 3 MODEL DEVELOPMENT 9
3.1 Problem definition 9
3.2 Assumptions 10
3.3 Mathematical Formulation 10
CHAPTER 4 METHODOLOGY 14
4.1 Solution representation 14
4.2 Initial solution 18
4.3 Neighborhood structures 18
4.4 Parameter used 19
4.5 Proposed SA procedure 20
CHAPTER 5 NUMERICAL EXPERIMENT 25
5.1 Performance analysis of proposed SA in LRP benchmark instance 25
5.2 LRPTDD test instance 32
5.3 Parameter setting of proposed SA for LRPTDD 34
5.4 Proposed SA performance on the new LRPTDD instance 36
5.5 Sensitivity analysis 38
5.5.1 Sensitivity analysis for problem parameter 38
5.5.2 Sensitivity analysis for algorithm parameter 42
CHAPTER 6 CONCLUSIONS AND RECOMMENDATION 46
REFFERENCES 47

Afshar-Nadjafi, B., & Afshar-Nadjafi, A. (2016). Multi-depot time dependent vehicle routing problem with heterogeneous fleet and time windows. International Journal of Operational Research, 26(1), 88-103.
Ahmadi-Javid, A., & Seddighi, A. H. (2013). A location-routing problem with disruption risk. Transportation Research Part E: Logistics and Transportation Review, 53, 63-82.
Albareda-Sambola, M., Dı́az, J. A., & Fernández, E. (2005). A compact model and tight bounds for a combined location-routing problem. Computers & Operations Research, 32(3), 407-428.
Alumur, S., & Kara, B. Y. (2007). A new model for the hazardous waste location-routing problem. Computers & Operations Research, 34(5), 1406-1423.
Ambrosino, D., Sciomachen, A., & Scutellà, M. G. (2009). A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem. Computers & Operations Research, 36(2), 442-460.
Baldacci, R., Mingozzi, A., & Wolfler Calvo, R. (2011). An exact method for the capacitated location-routing problem. Operations Research, 59(5), 1284-1296.
Balsevich, F., Berdegué, J. A., Flores, L., Mainville, D., & Reardon, T. (2003). Supermarkets and produce quality and safety standards in Latin America. American journal of agricultural economics, 85(5), 1147-1154.
Barreto, S. (2004). Analysis and modeling of location-routing problems. Portugal: University of Aveiro.
Barreto, S., Ferreira, C., Paixao, J., & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3), 968-977.
Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., & Calvo, R. W. (2011). A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research, 38(6), 931-941.
Berdegué, J. A., Balsevich, F., Flores, L., & Reardon, T. (2005). Central American supermarkets’ private standards of quality and safety in procurement of fresh fruits and vegetables. Food Policy, 30(3), 254-269.
Bouhafs, L., & Koukam, A. (2006). A combination of simulated annealing and ant colony system for the capacitated location-routing problem. Proceedings of the Knowledge-Based Intelligent Information and Engineering Systems (pp. 409-416).
Boventer, E. (1961). The relationship between transportation costs and location rent in transportation problems. Journal of Regional Science, 3(2), 27-40.
Bruns, A., Klose, A., & Stähly, P. (2000). Restructuring of Swiss parcel delivery services. OR Spectrum, 22(2), 285-302.
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.
Caunhye, A. M., Zhang, Y., Li, M., & Nie, X. (2015). A location-routing model for prepositioning and distributing emergency supplies. Transportation Research Part E: Logistics and Transportation Review, 90, 161–176.
Chan, Y., Carter, W. B., & Burnes, M. D. (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Computers & Operations Research, 28(8), 803-826.
Chen, H.-K., Hsueh, C.-F., & Chang, M.-S. (2006). The real-time time-dependent vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 42(5), 383-408.
Chien, T. W. (1993). Heuristic Procedures for Practical‐Sized Uncapacitated Location‐Capacitated Routing Problems. Decision Sciences, 24(5), 995-1021.
Coy, S. P., Golden, B. L., Runger, G. C., & Wasil, E. A. (2001). Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics, 7(1), 77-97.
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E., & Gambardella, L. M. (2008). Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research, 185(3), 1174-1191.
Dong, Z., & Turnquist, M. A. (2015). Combining service frequency and vehicle routing for managing supplier shipments. Transportation Research Part E: Logistics and Transportation Review, 79(0), 231-243.
Drexl, M., & Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. European Journal of Operational Research, 241(2), 283-308.
Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2008). A memetic approach for the capacitated location routing problem. Proceedings of the EU/meeting 2008 workshop on metaheuristics for logistics and vehicle routing. University of Technology of Troyes, France.
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.
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.
Guha, S., & Khuller, S. (1999). Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1), 228-248.
Gunnarsson, H., Rönnqvist, M., & Carlsson, D. (2006). A combined terminal location and ship routing problem. Journal of the Operational Research Society, 57(8), 928-938.
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.
Karaoglan, I., & Altiparmak, F. (2010). A hybrid genetic algorithm for the location-routing problem with simultaneous pickup and delivery. Proceedings of the Computers and Industrial Engineering (CIE), 2010 40th International Conference on (pp. 1-6).
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, 671-680.
Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm. European Journal of Operational Research, 248(1), 33-51.
Kulcar, T. (1996). Optimizing solid waste collection in Brussels. European Journal of Operational Research, 90(1), 71-77.
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., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22(3), 161-172.
Lin, C., Chow, C., & Chen, A. (2002). A location-routing-loading problem for bill delivery services. Computers & Industrial Engineering, 43(1), 5-25.
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., and, Z.-J. L., & Hsi, F.-H. (2006). Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems. IEEE International Conference on Systems, Man, and Cybernetics, Taipei, Taiwan.
Lin, S.-W., Yu, V. F., & Lu, C.-C. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516.
Liu, J., & Kachitvichyanukul, V. (2015). A particle swarm optimisation algorithm for the capacitated location-routing problem. International Journal of Operational Research, 24(2), 184-213.
Madsen, O. B. (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). Equations of state calculations by fast computing machines. Journal of Chemical Physics, 21, 1087-1092.
Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1), 1-15.
Murty, K. G., & Djang, P. A. (1999). The US Army national guard's mobile training simulators location and routing problem. Operations Research, 47(2), 175-182.
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
Nambiar, J. M., Gelders, L. F., & Van Wassenhove, L. N. (1981). A large scale location-allocation problem in the natural rubber industry. European Journal of Operational Research, 6(2), 183-189.
Norouzi, N., Sadegh-Amalnick, M., & Tavakkoli-Moghaddam, R. (2016). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 1-14.
Or, I., & Pierskalla, W. P. (1979). A transportation location-allocation model for regional blood banking. AIIE transactions, 11(2), 86-95.
Prins, C., Prodhon, C., & Calvo, R. W. (2006a). A Memetic Algorithm with Population Management (MA| PM) for the Capacitated Location-Routing Problem. Lecture notes in computer science, 3906, 183-194.
Prins, C., Prodhon, C., & Calvo, R. W. (2006b). 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.
Prins, C., Prodhon, C., & Wolfler-Calvo, R. (2004). Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité. Proceedings of the MOSIM (Vol. 4, pp. 1115-1122).
Prodhon, C., & Prins, C. (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1), 1-17.
Reardon, T., Timmer, C. P., Barrett, C. B., & Berdegué, J. (2003). The rise of supermarkets in Africa, Asia, and Latin America. American journal of agricultural economics, 85(5), 1140-1146.
Rosen, S. L., & Harmonosky, C. M. (2005). An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Computers & Operations Research, 32(2), 343-358.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156.
Semet, F., & Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations research, 41(4), 469-488.
Soler, D., Albiach, J., & MartíNez, E. (2009). A way to optimally solve a time-dependent vehicle routing problem with time windows. Operations Research Letters, 37(1), 37-42.
Srivastava, R. (1993). Alternate solution procedures for the location-routing problem. Omega, 21(4), 497-506.
Teece, D. J. (2010). Business models, business strategy and innovation. Long range planning, 43(2), 172-194.
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.
Wang, H., Du, L., & Ma, S. (2014). Multi-objective open location-routing model with split delivery for optimized relief distribution in post-earthquake. Transportation Research Part E: Logistics and Transportation Review, 69, 160-179.
Wang, X., Sun, X., & Fang, Y. (2005). A two-phase hybrid heuristic search approach to the location-routing problem. Proceedings of the Systems, Man and Cybernetics, 2005 IEEE International Conference on (Vol. 4, pp. 3338-3343).
Wasner, M., & Zäpfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403-419.
Watson-Gandy, C., & Dohrn, P. (1973). Depot location with van salesmen—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.
Xiao, Y., & Konak, A. (2016). The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transportation Research Part E: Logistics and Transportation Review, 88, 146-166.
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.
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.