臺灣博碩士論文加值系統

開放式車輛途程問題(Open Vehicle Routing Problem; OVRP)為車輛途程問題(Vehicle Routing Problem; VRP)的衍伸應用，VRP為一封閉路程，車輛完成服務後須回到場站，而OVRP為一開放式迴路，車輛服務後無需回到場站，OVRP實務上的應用如校車接送，火車服務及第三方物流運輸等等。本研究考量OVRP在第三方物流運輸上的應用，加入存貨成本因素，結合存貨途程問題(Inventory Routing Problem; IRP)，定義開放式存貨途程問題(Open Inventory Routing Problem; OIRP)，並建構OIRP數學模型。本研究站在物流業角度，考量如何產生有效路徑，使其在需求不確定下能以最小成本遞送。本研究以禁忌搜尋法(Tabu Search; TS)為基礎，模擬多品項之需求不確定問題，最佳化其配送路徑，使其運輸成本及存貨相關成本最小化。

Open Vehicle Routing Problem (OVRP) is an extensions of the Vehicle Routing Problem (VRP). The original VRP problem concern with a closed loop problem in which all the routes are started and ended in the same depot. On the other hand, OVRP is an open loop problem in which each vehicle starts from a depot but ends at a final served customer. The applications of OVRP include school bus, train service and third party logistics. In this research, we incorporate inventory effect into routing path and determine a new problem called Open Inventory Routing Problem (OIRP). This research presents a mathematical model and algorithm of the OIRP based on Tabu Search (TS) to solve a multi-item with demand uncertainty problem and minimize the total cost of the delivery route. The objective of OIRP is to minimize the sum of the total transportation costs and inventory costs.

CHINESE ABSTRACT I
ENGLISH ABSTRACT II
TABLE OF CONTENTS III
LIST OF FIGURES V
LIST OF TABLES VI
I. INTRODUCTION - 1 -
1.1. RESEARCH BACKGROUND AND MOTIVATION - 1 -
1.2. PURPOSE OF RESEARCH - 2 -
1.3. RESEARCH FRAMEWORK - 2 -
II. LITERATURE REVIEW - 4 -
2.1. VEHICLE ROUTING PROBLEM - 4 -
2.2. OPEN VEHICLE ROUTING PROBLEM - 5 -
2.3. INVENTORY ROUTING PROBLEM - 6 -
2.4. TABU SEARCH - 9 -
III. MODEL FORMULATION - 13 -
3.1. PROBLEM DEFINITION - 13 -
3.2. MATHEMATICAL MODEL - 15 -
IV. SOLUTION PROCEDURE - 19 -
4.1. INITIALIZATION - 19 -
4.2. NEIGHBORHOOD STRUCTURE - 20 -
4.3. TABU SEARCH ALGORITHM - 22 -
4.4. THOROUGH LOCAL SEARCH - 24 -
V. CONSTRUCTION OF TEST INSTANCES - 27 -
5.1. BENCHMARKING - 27 -
5.2. INSTANCES CONSTRUCTION - 28 -
5.3. COMPUTATIONAL RESULTS - 28 -
5.4. SENSITIVITY ANALYSIS - 42 -
VI. CONCLUSION AND FUTURE RESEARCH - 45 -
6.1. CONCLUSION - 45 -
6.2. FUTURE RESEARCH - 46 -
BIBLIOGRAPHIES - 47 -

Bibliographies
Ahmadi Javid, A., &; Azad, N. (2010). Incorporating location, routing and inventory decisions in supply chain network design. Transportation Research Part E: Logistics and Transportation Review, 46(5), 582-597.
Alfredo Tang Montane, F., &; Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers &; Operations Research, 33(3), 595-619.
Andersson, H., Hoff, A., Christiansen, M., Hasle, G., &; Lokketangen, A. (2010). Industrial aspects and literature survey: Combined inventory management and routing. Computers &; Operations Research, 37(9), 1515-1536.
Archetti, C., Bertazzi, L., Hertz, A., &; Speranza, M. G. (2012). A hybrid heuristic for an inventory routing problem. INFORMS Journal on Computing, 24(1), 101-116.
Archetti, C., Bertazzi, L., Laporte, G., &; Speranza, M. G. (2007). A branch-and-cut algorithm for a vendor-managed inventory-routing problem. Transportation Science, 41(3), 382-391.
Baker, B. M., &; Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem. Computers &; Operations Research, 30(5), 787-800.
Bell, J. E., &; McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41-48.
Bertazzi, L., Bosco, A., Guerriero, F., &; Lagana, D. (2011). A stochastic inventory routing problem with stock-out. Transportation Research Part C: Emerging Technologies.
Brandao, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552-564.
Campbell, A. M., &; Savelsbergh, M. W. P. (2004). A decomposition approach for the inventory-routing problem. Transportation Science, 38(4), 488-502.
Chen, A., Yang, G., &; Wu, Z. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University-Science A, 7(4), 607-614.
Coelho, L. C., Cordeau, J. F., &; Laporte, G. (2012). The inventory-routing problem with transshipment. Computers &; Operations Research.
Cordeau, J. F., Desaulniers, G., Desrosiers, J., Solomon, M. M., &; Soumis, F. (2002). VRP with time windows. The vehicle routing problem, 9, 157-193.
Cousineau-Ouimet, K. (2002). A tabu search heuristic for the inventory routing problem. Paper presented at the Proceedings of 37th Annual ORSNZ Conference.
Dantzig, G. B., &; Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Dror, M., Ball, M., &; Golden, B. (1985). A computational comparison of algorithms for the inventory routing problem. Annals of Operations Research, 4(1), 1-23.
Gaur, V., &; Fisher, M. L. (2004). A periodic inventory routing problem at a supermarket chain. Operations research, 52(6), 813-822.
Gendreau, M., Hertz, A., &; Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management science, 40(10), 1276-1290.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers &; Operations Research, 13(5), 533-549.
Hemmelmayr, V. C., Doerner, K. F., &; Hartl, R. F. (2009). A variable neighborhood search heuristic for periodic routing problems. European Journal of Operational Research, 195(3), 791-802.
Hertz, A., &; de Werra, D. (1990). The tabu search metaheuristic: how we used it. Annals of Mathematics and Artificial Intelligence, 1(1), 111-121.
Huang, S. H., &; Lin, P. C. (2010). A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty. Transportation Research Part E: Logistics and Transportation Review, 46(5), 598-611.
Kirkpatrick, S., &; Vecchi, M. (1983). Optimization by simmulated annealing. science, 220(4598), 671-680.
Kleywegt, A. J., Nori, V. S., &; Savelsbergh, M. W. P. (2002). The stochastic inventory routing problem with direct deliveries. Transportation Science, 36(1), 94-118.
Laporte, G., Nobert, Y., &; Desrochers, M. (1985). Optimal routing under capacity and distance restrictions. Operations research, 33(5), 1050-1073.
Moin, N. H., &; Salhi, S. (2006). Inventory routing problems: a logistical overview. Journal of the Operational Research Society, 58(9), 1185-1194.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451.
Rusdiansyah, A., &; Tsao, D. (2005). An integrated model of the periodic delivery problems for vending-machine supply chains. Journal of Food Engineering, 70(3), 421-434.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Solyalı, O., Cordeau, J. F., &; Laporte, G. (2012). Robust inventory routing under demand uncertainty. Transportation Science, 46(3), 327-340.
Taillard, E., Badeau, P., Gendreau, M., Guertin, F., &; Potvin, J. Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2), 170-186.
Toth, P., &; Vigo, D. (1987). The vehicle routing problem (Vol. 9): Society for Industrial Mathematics.
Toth, P., &; Vigo, D. (2002). VRP with backhauls. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 9, 195-221.