跳到主要內容

臺灣博碩士論文加值系統

(44.220.255.141) 您好!臺灣時間:2024/11/04 02:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王偉亞
研究生(外文):Anak Agung Ngurah Perwira Redi
論文名稱:具有越庫作業之開放式車輛途程問題
論文名稱(外文):Open Vehicle Routing Problem With Cross-Docking
指導教授:喻奉天喻奉天引用關係
指導教授(外文):Vincent F. Yu
口試委員:喻奉天
口試委員(外文):Vincent F. Yu
口試日期:2013-12-23
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:63
中文關鍵詞:Cross-dockingOpen vehicle routing problemSimulated annealing (SA)
外文關鍵詞:Cross-dockingOpen vehicle routing problemSimulated annealing (SA)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:242
  • 評分評分:
  • 下載下載:23
  • 收藏至我的研究室書目清單書目收藏:0
With the growing appreciation of the advantages of cross-docking technique in literature as well as in practice in the field of supply chain management and with the advances of numerous applications in vehicle routing problem across broad range of practical context, present an opportunity to explore the open vehicle routing problem with cross-docking (OVRPCD). In retail for example; capital expenditure necessary in vehicle acquisition and other delivery-related fixed assets can be a burden for the retailer, then outsourcing logistical service can be a cost-effective option. This practical scenario can be applied to have an open flow-network of routes. Contracted transportation service starts from picking up quantity ordered from various suppliers up to delivery of quantity demanded from his stores or customers via his cross-dock facility. Vehicles will route in the network in a one-way fashion. They do not start and end at depots or one fixed point. As a result, no loops are created in the network, hence, open routing. In this way, the retailer saves certain transportation costs of possible wasted trips should he acquire his own fleet of vehicle. It is in this practical case that this specific vehicle routing variant may be applied.
In this paper, a single product and single-dock are considered. In the pick-up operations, capacity-homogeneous vehicles start at differing pick-up points and time. So, the vehicles are scheduled to route in the network synchronously to arrive at the dock at the same time. In the delivery operations, all customers must be served only once and deliveries should be finished at a predetermined duration. Then the problem is modeled to find the number of vehicles to be contracted and their corresponding routes at the least possible transportation cost. A simulated annealing algorithm (SA) is proposed to find the optimal vehicle fleet and their respective routes. The proposed SA algorithm considered neighborhood structures to be used to improve the solution. The study analyzed further by suggesting a Pareto frontier solved from nine possible neighborhood configurations suitable for small, medium, and large problem sizes. The results show, after a large problem was used with different time horizon, that increases in time horizon decreases objective function value. In terms of objective function value, the solution of the proposed SA algorithm for all instances were as efficient as that of the optimal LINGO solutions in problem 1 and 2 and a reasonably comparable result of Problem 3. A 1.5% gap between the two solution methods was observed and the algorithm evidently provided good solutions within reasonable span of time for all instances in three problem sizes.
With the growing appreciation of the advantages of cross-docking technique in literature as well as in practice in the field of supply chain management and with the advances of numerous applications in vehicle routing problem across broad range of practical context, present an opportunity to explore the open vehicle routing problem with cross-docking (OVRPCD). In retail for example; capital expenditure necessary in vehicle acquisition and other delivery-related fixed assets can be a burden for the retailer, then outsourcing logistical service can be a cost-effective option. This practical scenario can be applied to have an open flow-network of routes. Contracted transportation service starts from picking up quantity ordered from various suppliers up to delivery of quantity demanded from his stores or customers via his cross-dock facility. Vehicles will route in the network in a one-way fashion. They do not start and end at depots or one fixed point. As a result, no loops are created in the network, hence, open routing. In this way, the retailer saves certain transportation costs of possible wasted trips should he acquire his own fleet of vehicle. It is in this practical case that this specific vehicle routing variant may be applied.
In this paper, a single product and single-dock are considered. In the pick-up operations, capacity-homogeneous vehicles start at differing pick-up points and time. So, the vehicles are scheduled to route in the network synchronously to arrive at the dock at the same time. In the delivery operations, all customers must be served only once and deliveries should be finished at a predetermined duration. Then the problem is modeled to find the number of vehicles to be contracted and their corresponding routes at the least possible transportation cost. A simulated annealing algorithm (SA) is proposed to find the optimal vehicle fleet and their respective routes. The proposed SA algorithm considered neighborhood structures to be used to improve the solution. The study analyzed further by suggesting a Pareto frontier solved from nine possible neighborhood configurations suitable for small, medium, and large problem sizes. The results show, after a large problem was used with different time horizon, that increases in time horizon decreases objective function value. In terms of objective function value, the solution of the proposed SA algorithm for all instances were as efficient as that of the optimal LINGO solutions in problem 1 and 2 and a reasonably comparable result of Problem 3. A 1.5% gap between the two solution methods was observed and the algorithm evidently provided good solutions within reasonable span of time for all instances in three problem sizes.
ABSTRACT iii
LIST OF FIGURES viii
LIST OF TABLES ix
CHAPTER 1 1
INTRODUCTION 1
1.1. Background 1
1.2. Purposes 6
1.3. Research Scopes and Limitations 6
1.4. Research Framework 7
CHAPTER 2 9
LITERATURE REVIEW 9
2.1. Cross-Docking 9
2.2. Vehicle Routing Problem with Cross-Docking 10
2.3. Open Vehicle Routing Problem 12
2.4. Simulated Annealing for Vehicle Routing Problem 13
CHAPTER 3 15
PROBLEM DEFINITION AND MATHEMATICAL FORMULATION 15
3.1. Problem Definition 15
3.2. Mathematical Formulation 17
CHAPTER 4 22
SOLUTION METHODOLOGY 22
4.1. Simulated Annealing Heuristic for the OVRPCD 22
4.2. Solution Representation 25
4.3. Initial Solution 25
4.4. Simulated Annealing Heuristic Procedure 29
4.4.1. Neighborhood Structure 30
4.4.2. Local Search 32
CHAPTER 5 34
COMPUTATIONAL RESULT 34
5.1. Parameters Selection 34
5.3. Algorithm Verification 38
5.4. OVRPCD Computation Result 43
CHAPTER 6 46
CONCLUSIONS AND FUTURE RESEARCH 46
6.1. Conclusions 46
6.2. Future Research 47
REFERENCES 48
APPENDIX 53
Detail of Route Result for OVRPCD 53
Agustina, D., et al. (2010). A review: mathematical models for cross dock planning. International Journal of Engineering Business Management 2(2010): 47-54.
Ai, T. J. and V. Kachitvichyanukul (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering 56(1): 380-387.
Ai, T. J. and V. Kachitvichyanukul (2009). A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research 36(5): 1693-1702.
Apte, U. M. and S. Viswanathan (2000). Effective cross docking for improving distribution efficiencies. International Journal of Logistics 3(3): 291-302.
Baker, B. M. and M. Ayechew (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research 30(5): 787-800.
Bent, R. and P. Van Hentenryck (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science 38(4): 515-530.
Boysen, N. and M. Fliedner (2010). Cross dock scheduling: Classification, literature review and research agenda. Omega 38(6): 413-422.
Brandao, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research 157(3): 552-564.
Cao, E. and M. Lai (2010). The open vehicle routing problem with fuzzy demands. Expert Systems with Applications 37(3): 2405-2411.
Dondo, R. and J. Cerda (2013). A sweep-heuristic based formulation for the vehicle routing problem with cross-docking. Computers & Chemical Engineering 48: 293-311.
Gendreau, M., et al. (1994). A tabu search heuristic for the vehicle routing problem. Management science 40(10): 1276-1290.
Gendreau, M., et al. (2002). A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science 40(10): 1276-1290.
Gendreau, M., et al. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research 26(12): 1153-1173.
Goksal, F. P., et al. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering 65(1): 39-53.
Hasani-Goodarzi, A. and R. Tavakkoli-Moghaddam (2012). Capacitated Vehicle Routing Problem for Multi-Product Cross- Docking with Split Deliveries and Pickups. Procedia - Social and Behavioral Sciences 62: 1360-1365.
Ho, W., et al. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence 21(4): 548-557.
Hwang, H.-S. (2002). An improved model for vehicle routing problem with time constraint based on genetic algorithm. Computers & Industrial Engineering 42(2): 361-369.
Jayaraman, V. and A. Ross (2003). A simulated annealing methodology to distribution network design and management. European Journal of Operational Research 144(3): 629-645.
Kergosien, Y., et al. (2013). Metaheuristic algorithms for solving two interconnected vehicle routing problems in a hospital complex. Computers & Operations Research 40(10): 2508-2518.
Kirkpatrick, S., et al. (1983). Optimization by simmulated annealing. science 220(4598): 671-680.
Laporte, G., et al. (2000). Classical and modern heuristics for the vehicle routing problem. International transactions in operational research 7(4‐5): 285-300.
Lee, Y. H., et al. (2006). Vehicle routing scheduling for cross-docking in the supply chain. Computers & Industrial Engineering 51(2): 247-256.
Li, F., et al. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & Operations Research 34(10): 2918-2930.
Liao, C.-J., et al. (2010). Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications 37(10): 6868-6873.
Lin, S.-W., et al. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & Operations Research 36(5): 1683-1692.
Liu, R. and Z. Jiang (2012). The close–open mixed vehicle routing problem. European Journal of Operational Research 220(2): 349-360.
Marinakis, Y. and M. Marinaki (2010). A hybrid genetic – Particle Swarm Optimization Algorithm for the vehicle routing problem. Expert Systems with Applications 37(2): 1446-1455.
Metropolis, N., et al. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics 21(6): 1087.
MirHassani, S. A. and N. Abolghasemi (2011). A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications 38(9): 11547-11551.
Mousavi, S. M. and R. Tavakkoli-Moghaddam (2013). A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain. Journal of Manufacturing Systems 32(2): 335-347.
Pisinger, D. and S. Ropke (2007). A general heuristic for vehicle routing problems. Computers & Operations Research 34(8): 2403-2435.
Repoussis, P. P., et al. (2010). A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research 37(3): 443-455.
Repoussis, P. P., et al. (2006). The open vehicle routing problem with time windows. Journal of the Operational Research Society 58(3): 355-367.
Repoussis, P. P., et al. (2009). An evolutionary algorithm for the open vehicle routing problem with time windows. Bio-inspired Algorithms for the Vehicle Routing Problem, Springer: 55-75.
Ross, A. and V. Jayaraman (2008). An evaluation of new heuristics for the location of cross-docks distribution centers in supply chain network design. Computers & Industrial Engineering 55(1): 64-79.
Santos, F. A., et al. (2013). The Pickup and Delivery Problem with Cross-Docking. Computers & Operations Research 40(4): 1085-1093.
Sariklis, D. and S. Powell (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society: 564-573.
Subramanian, A., et al. (2012). A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem. European Journal of Operational Research 221(2): 285-295.
Subramanian, A., et al. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research 40(10): 2519-2531.
Sung, C. and S. Song (2003). Integrated service network design for a cross-docking supply chain network. Journal of the Operational Research Society 54(12): 1283-1295.
Toth, P. and D. Vigo (2002). The vehicle routing problem, Siam.
Vahdani, B., et al. (2009). Scheduling the truck holdover recurrent dock cross-dock problem using robust meta-heuristics. The International Journal of Advanced Manufacturing Technology 46(5-8): 769-783.
Van Belle, J., et al. (2012). Cross-docking: State of the art. Omega 40(6): 827-846.
Wen, M., et al. (2008). Vehicle routing with cross-docking. Journal of the Operational Research Society 60(12): 1708-1718.
Wen, M., et al. (2008). Vehicle Routing with Cross-Docking. Journal of the Operational Research Society 60: 1708-1718.
Yu, S., et al. (2011). A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. Expert Systems with Applications 38(8): 10568-10573.
Yu, V. F., et al. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering 58(2): 288-299.
Zachariadis, E. E. and C. T. Kiranoudis (2010). An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Computers & Operations Research 37(4): 712-723.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文