臺灣博碩士論文加值系統

This research presents an extension of the Vehicle vehicle Routing routing Problem problem with Time time Wwindows (VRPTW), namely,called the path covering problem with time windows (PCPTW). In order to be more applicable in a real-world setting, this research presents a problem that always has been faced by a many company companies which that does not have their own a vehicle at allfleet, or do not have enough vehicles its feel is inappropriate or inadequate to satisfy the demand. and have to be delivered in relatively short times to a set of customers. PCPTW is NP-hard since its variant of the well-known VRPTW is NP-hardvehicle routing problem with time windows. Thus, this research formulated a mathematical models for PCPTW and , performed a numerical study usinged CPLEX to solve small and largePCPTW benchmark instances. In addition, this study and developed a simulated annealing with restart strategy (SA_RS) algorithm to solving large PCPTW instances, which that are generated from Solomon’s VRPTW benchmark instances. At the end, this research cComputational result shows that the proposed SA_RS performed performs well on solving PCPTW.

This research presents an extension of the Vehicle vehicle Routing routing Problem problem with Time time Wwindows (VRPTW), namely,called the path covering problem with time windows (PCPTW). In order to be more applicable in a real-world setting, this research presents a problem that always has been faced by a many company companies which that does not have their own a vehicle at allfleet, or do not have enough vehicles its feel is inappropriate or inadequate to satisfy the demand. and have to be delivered in relatively short times to a set of customers. PCPTW is NP-hard since its variant of the well-known VRPTW is NP-hardvehicle routing problem with time windows. Thus, this research formulated a mathematical models for PCPTW and , performed a numerical study usinged CPLEX to solve small and largePCPTW benchmark instances. In addition, this study and developed a simulated annealing with restart strategy (SA_RS) algorithm to solving large PCPTW instances, which that are generated from Solomon’s VRPTW benchmark instances. At the end, this research cComputational result shows that the proposed SA_RS performed performs well on solving PCPTW.

ABSTRACT iv
TABLE OF CONTENTS vi
LIST OF FIGURES vii
LIST OF TABLES viii
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Research Statement 3
1.3 Objectives 3
1.4 Scope and Limitations 3
1.5 Organization 4
CHAPTER 2 LITERATURE REVIEW 5
2.1 Vehicle Routing Problem 5
2.2 Simulated Annealing 8
CHAPTER 3 MODEL DEVELOPMENT 11
3.1 Problem Definition 11
3.2 Mathematical Model 12
CHAPTER 4 SOLUTION METHODOLOGY 15
4.1 Simulated Annealing Algorithm 15
4.2 Solution Representation 18
4.3 Initial Solution 18
4.4 Neighborhood Moves 18
4.5 Parameters used in SA 20
CHAPTER 5 COMPUTATIONAL RESULT 21
5.1 Parameter Setting 21
5.2 Algorithm Testing 25
5.3 Computational Result for PCPTW 30
CHAPTER 6 CONCLUSION AND RECOMMENDATION 45
6.1 Conclusion 45
6.2 Research Contributions 46
6.3 Recommendation for Future Research 46
REFERENCE 48

Abramson, D. (1991). Constructing School Timetables Using Simulated Annealing: Sequential and Parallel Algorithms. Management Science, 37(1), 98-113.
Akpinar, S. (2016). Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem. Expert Systems with Applications, 61, 28-38.
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), 635-639.
Alvarenga, G. B., & Mateus, G. R. (2004, 5-8 Dec. 2004). A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows. Proceedings of the Hybrid Intelligent Systems, 2004. HIS '04. Fourth International Conference on (pp. 428-433).
Alvarez, A., & Munari, P. (2017). An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Computers & Operations Research, 83, 1-12.
Beamon, B. M. (1998). Supply chain design and analysis:: Models and methods. International Journal of Production Economics, 55(3), 281-294.
Brandão, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552-564.
Chwif, L., Barretto, M. R. P., & Moscato, L. A. (1998). A solution to the facility layout problem using simulated annealing. Computers in Industry, 36(1–2), 125-132.
Cordeau, J.-F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Chapter 6 Vehicle Routing Handbook in OR & MS. (Vol. 14): Elsevier B.V.
Coy, S. P., Golden, B. L., Runger, G. C., & Wasil, E. A. (2000). Using Experimental Design to Find Effective Parameter Setting for Heuristic. 7.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80-91.
Desroisers, J., Madsen, O. B. G., Solomon, M. M., & Soumis, F. (1999). 2-Path Cuts for the Vehicle Routing Problem with the Time Windows. 33(1).
Fahimnia, B., Sarkis, J., & Davarzani, H. (2015). Green supply chain management: A review and bibliometric analysis. International Journal of Production Economics, 162, 101-114.
Fu, Z., Eglese, R., & Li, L. Y. O. (2005). A New Tabu Search Heuristic for the Open Vehicle Routing Problem. The Journal of the Operational Research Society, 56(3), 267-274.
Halim, C. (2015). Minimum Cost Vertex-Disjoint Path Cover Problem. Taipei: National Taiwan University of Science and Technology.
Jayaraman, V., & Ross, A. (2003). A simulated annealing methodology to distribution network design and management. European Journal of Operational Research, 144(3), 629-645.
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.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.
Lenstra, J. K., & Kan, A. H. G. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
Letchford, A. N., Lysgaard, J., & Eglese, R. W. (2007). A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem. The Journal of the Operational Research Society, 58(12), 1642-1651.
Li, F., Golden, B., & Wasil, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & Operations Research, 34(10), 2918-2930.
Lin, S.-W., Chou, S.-Y., & Chen, S.-C. (2007). Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine schedulingwith a common due date. [journal article]. Journal of Heuristics, 13(2), 151-165.
Lin, S.-W., Ying, K.-C., Lu, C.-C., & Gupta, J. N. D. (2011a). Applying multi-start simulated annealing to schedule a flowline manufacturing cell with sequence dependent family setup times. International Journal of Production Economics, 130(2), 246-254.
Lin, S.-W., & Yu, V. F. (2015). A simulated annealing heuristic for the multiconstraint team orienteering problem with multiple time windows. Applied Soft Computing, 37, 632-642.
Lin, S.-W., Yu, V. F., & Lu, C.-C. (2011b). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252.
Lin, S.-W. T., K. -C.; Lee, Z. -J.; Hsi, F. -H. (2006). Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problem. (IEEE international conference on Systems, Man, and Cybernetics), 639 -644.
Magdalena, I. C. (2016). Particle Swarm Optimization for the Minimum Cost Vertex-Disjoint Path Cover Problem. Taipei: National Taiwan University of Science and Technology.
McKendall Jr, A. R., Shang, J., & Kuppusamy, S. (2006). Simulated annealing heuristics for the dynamic facility layout problem. Computers & Operations Research, 33(8), 2431-2444.
Meixell, M. J. (2005). The impact of setup costs, commonality, and capacity on schedule stability: An exploratory study. International Journal of Production Economics, 95(1), 95-107.
Meixell, M. J., & Gargeya, V. B. (2005). Global supply chain design: A literature review and critique. Transportation Research Part E, 531-550.
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.
Munari, P., & Gondzio, J. (2013). Using the primal-dual interior point algorithm within the branch-price-and-cut method. Computers & Operations Research, 40(8), 2026-2036.
Pureza, V., Morabito, R., & Reimann, M. (2012). Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. European Journal of Operational Research, 218(3), 636-647.
Repoussis, P. P., Tarantilis, C. D., & Ioannou, G. (2009). An Evolutionary Algorithm for the Open Vehicle Routing Problem with Time Windows. In F. B. Pereira & J. Tavares (Eds.), Bio-inspired Algorithms for the Vehicle Routing Problem. (pp. 55-75). Berlin, Heidelberg: Springer Berlin Heidelberg.
Sariklis, D., & Powell, S. (2000). A Heuristic Method for the Open Vehicle Routing Problem. The Journal of the Operational Research Society, 51(5), 564-573.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265.
Syslo, M., Deo, N., & Kowalik, J. S. (1983a). Discrete Optimization Algorithms with Pascal Programs: Prentice Hall Professional Technical Reference.
Syslo, M. M., Deo, N., & Kowalik, J. S. (1983b). Discrete optimization algorithm: with pascal programs: Courier Dover Publications.
Tarantilis, C. D., Diakoulaki, D., & Kiranoudis, C. T. (2004). Combination of geographical information system and efficiennt routing algorithms for real life distribution operations. 152.
Tarantilis, C. D., & Kiranoudis, C. T. (2002). A list-based threshold accepting method for job shop scheduling problems. International Journal of Production Economics, 77(2), 159-171.
Toth, P., & Vigo, D. (2002). The vehicle routing problem.
Tseng, Y.-y., Yue, W. L., & Taylor, M. A. (2005). The role of transportation in logistics chain. 5.
Van Breedam, A. (1995). Improvement heuristics for the Vehicle Routing Problem based on simulated annealing. European Journal of Operational Research, 86(3), 480-490.
Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research, 39(7), 1419-1431.
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., Redi, A. A. N. P., Hidayat, Y. A., & Wibowo, O. J. (2017a). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132.
Yu, V. F., Redi, A. A. N. P., Yang, C.-L., Ruskartina, E., & Santosa, B. (2017b). Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem. Applied Soft Computing, 52, 657-672.
Zare-Reisabadi​​, E., & Hamid Mirmohammadi, S. (2015). Site dependent vehicle routing problem with soft time window: Modeling and solution approach. Computers & Industrial Engineering, 90, 177-185.