本研究探討在一個物流中心，具有多台配送車輛，但顧客需求為隨機之車輛配送規劃問題，系統中每一車輛之容量為有限，車輛由物流中心出發至多個地理位置不同且需求量未知的顧客，車輛依循規劃路線進行配送，路徑規劃之原則除了最小化配送成本外，必須儘可能的滿足顧客需求。由於顧客需求為隨機變數，配送時顧客需求可能無法及時滿足，稱之為路徑失敗，並造成額外之懲罰成本，例如：配送路線改變所必須重新規劃所產生之建置成本及因車輛行駛路徑改變所增加之配送成本。
　　本研究之目的在將配送問題以區域分割規劃取代傳統的直接路徑安排，求得最佳的區域分割後，再考量每一區域之路徑規劃。在滿足一給定路徑失敗的機率下，使得總期望配送相關成本，包含期望配送成本以及期望懲罰成本為最小。本研究首先建構0、1整數規劃數學模式，由於模式具高度複雜性，遠較傳統車輛配送問題困難，故進而建構兩階段之數學隨機指派模式與區域期望成本模式。但隨機區域的分割方式具高度困難，無法快速求解其數學模式，故以隨機指派模式為基礎，發展啟發式演算法，決定車輛指派之配送區域，而後再考量多個區域劃分下的總期望車輛配送成本。
　　以往傳統均以路徑安排為主要考量，本研究提出區域分割概念，以區域為主要之決策考量，同時考量總期望配送成本與其額外配送成本。由於目標函數的衡量基準與過去學者所研究的不同，因此在比較上必須重新設計，並針對隨機需求下車輛配送規劃問題與期望需求率之動態排程下車輛配送問題進行求解，比較兩者期望相關成本之差異，並以演算實驗來驗證理論模式之正確性，及求解方法之品質與效率。本研究不論在總期望配送成本或是運算時間上皆較動態排程下之結果為佳，且當路徑失敗機率增加時，總期望配送成本呈現增加之趨勢，而運算時間亦呈現增加之趨勢，而當區域劃分數目增加時，總期望配送成本會呈現增加之趨勢，而運算時間則呈現遞減。

　　We consider the multi-vehicle routing problem, in which demands of customers are stochastic. Due to this randomness, a vehicle may fail to satisfy the demand of some customers when accumulated demands of customers in a designated route exceed the capacity of the vehicle. Cost to reschedule alternative route or dispatch additional vehicle to meet customer’s demand incurred when the route failure occurs.
　　In this thesis, the stochastic vehicle routing problem is formulated as a 0-1 integer programming model with probabilistic constraint. Due to the complexity of mathematical model, a streamlined two-stage formulation is then proposed to address this difficult problem. At the first stage, each customer is assigned to a vehicle by the reformulated stochastic linear assignment model, subject to the route failure constraint. The expected operating, including vehicle routing and route failure, is then computed for each vehicle at the second stage.
　　A heuristic solution procedure is developed to solve this stochastic vehicle routing problem. A simplified assignment model, based on expected demand of customers, is solved to determine the routing zone of each vehicle. The optimum route for each vehicle to serve the customers is then determined by solving traveling salesman problem; and the expected total routing cost is finally computed. Numerical experiments, with problem sizes up to 35 customers and 8 vehicles, have been performed. Our computational tests have shown that the expected operating cost of the routes developed by the new approach is significantly lower than that of the classical dynamic approach. The new approach also outperforms the existing approaches in terms of computational times or resources.

Albareda-Sambola, M., Vlerk, M. H. V. D., and Fernndex, E. (2006), “Exact solution to a class of stochastic generalized assignment problems,” European Journal of Operational Research 173, 465-487.

Alfa, A.S., Heragu, S.S., and Chen, M. (1991), “A 3-opt based simulated annealing algorithm for vehicle routing problems,” Computers & Industrial Engineering 21, 635-639.

Balinski, M.L., and Quandt, R.E. (1964), “On an integer program for a delivery problem,” Operations Research 12, 300-304.

Barbarosoglu, G., and Ozgur, D. (1999), “A tabu search algorithm for the vehicle routing problem,” Computer & Operations Research 26, 255-270.

Bektas, T. (2006), “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega 34, 209-219.

Bellmore, M., and Nemhauser, G.L. (1968), “The Traveling Salesman Problem: A Survey,” Operations Research 16, 538-558.

Bertsimas, D.J. (1992), “A vehicle routing problem with stochastic demand,” Operations Research 40, 574-585.

Brando, J. (2004), “A tabu search algorithm for the open vehicle routing problem,” European Journal of Operational Research 157, 552-564.

Carter, A.E., and Ragsdale, C.T. (2005), “A new approach to solving the multiple traveling salesperson problem using genetic algorithms,” European Journal of Operational Research 175, 246-257.

Chatterjee, S., Carrera, C., and Lynch, L.A. (1996), “Genetic algorithms and traveling salesman problems,” European Journal of Operational Research 93, 490-510.

Clarke, G., and Wright, J.W. (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research 12, 568-581.

Dantzig, G.B., Fulkerson, D.R., and Fohson, S.M. (1954), “Solution of a large-scale traveling-salesman problem,” Operations Research 2, 393-410.

Dror, M., Laporte, G., and Trudeau, P. (1989), “Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks,” Transportation Science 23, 166-176.

Fisher, M.L., and Jaikumar, R. (1981), “A Generalized Assignment Heuristic for Vehicle Routing,” Networks 11, 109-124.

Flod, M.M. (1956), “The Traveling-Salesman Problem,” Operations Research 4, 61-75.

Garey, M.R., and Fohson, D.S. (1979), “Computers and Intractability: A guide to theory of NP-Completeness,” Freeman, San Francisco.

Gavish, B., and Srikanth, K. (1986), “An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems,” Operations Research 34, 698-717.

Gendreau, M., Laporte, G., and Sguin, R. (1996), “Stochastic vehicle routing,” European Journal of Operational Research 88, 3-12.

Gendreau, M., Laporte, G., and Sguin, R. (1996), “A tabu search heuristic for the vehicle routing problem with stochastic demands and customers,” Operations Research 44, 469-475.

Gillett, B.E., and Miller, L.R. (1974), “A heuristic algorithm for the vehicle-dispatch problem,” Operations Research 22, 340-349.

Haugland, D., Ho, S.C., and Laporte, G. (2006), “Designing delivery districts for the vehicle routing problem with stochastic demands,” European Journal of Operational Research 180, 997-1010.

Kirkpartrick, S., Gelatt, C.D., and Vecchi, M.P. (1983), “Optimization by simulated annealing,” Science 220, 671-680.

Laporte, G., and Nobert, Y. (1980), “A cutting planes algorithm for the m-salesmen problem,” The Journal of the Operational Research Society 31, 1017-1023.

Laporte, G., Nobert, Y., and Desroches, M. (1985), “Optimal Routing under Capacity and Distance Restrictions,” Operations Research 33, 1050-1073.

Li, F., Golden, B., and Wasil, E. (2005), “Very large-scale vehicle routing: new test problems, algorithms, and results,” Computers & Operations Research 32, 1165-1179.

Malandraki, C., and Dial, R.B. (1996), “A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem,” European Journal of Operational Research 90, 45-55.

Miller, D.L., and Pekny, J.F. (1989), “Results from a parallel branch and bound algorithm for the asymmetric traveling salesman problem,” Operations Research Letters 8, 129-135.

Miller, C.E., Tucker, A.W., and Zemlin, R.A. (1960), “Integer programming formulations and traveling salesman problem,” Journal of the Association for Computing Machinery 7, 326-329.

Norback, J.P., and Love, R.F. (1977), “Geometric Approaches to solving the traveling salesman problem,” Management Science 23, 1208-1223.

Norback, J.P., and Love, R.F. (1979), “Heuristic for the Hamiltonian path problem in Euclidian two space,” Journal of the Operational Research Society 30, 363-368.

Papastavrou, J.D. (1996), “A stochastic dynamic routing policy using branching processes with state dependent immigration,” European Journal of Operational Research 95, 167-177.

Prins, C. (2004), “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computer & Operations Research 31, 1985-2002.

Robust, F., Daganzo, C.F., and Souleyrette II, R.R. (1990), “Implementing vehicle routing models,” Transportation Research B 24, 263-286.

Rosemkrantz, D.J., Strearns, R.E., and Lewis II, P.M. (1977), “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal on Computing 6, 563-581.

Savelsbergh, M.W.P. (1985), “Local search in routing problems with time windows,” Annals of Operations Research 4, 285-305.

Singh, K.N., and Oudheusden, D.L. (1997), “A branch and bound algorithm for the traveling purchaser problem,” European of Operational Research 97, 571-579.

Snyder, L.V., and Daskin, M.S. (2006), “A random-key genetic algorithm for the generalized traveling salesman problem,” European of Operational Research 174, 38-53.

Somhom, S., Modares, A., and Enkawa, T. (1999), “Competition-based neural network for the multiple traveling salesmen problem with minmax objective,” Computers & Operations Research 26, 395-407.

Taillard, . (1993), “Parallel iterative search methods for vehicle routing problems,” Networks 23, 661-673.

Tang, L., Liu, J., Rong, A., and Yang, Z. (2005), “A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex,” European of Operational Research 124, 267-282.

Thillman, F. (1969), “The multiple terminal delivery problem with probabilistic demands,” Transportation science 3, 192-204.

Waters, C.D.J. (1989), “Vehicle-scheduling problems with uncertainty and omitted customers,” Journal of Operational Research Society 40, 1099-1108.

Wren, A., and Holliday, A. (1972), “Computer scheduling of vehicles from one or more to a number of delivery points,” Operational Research Quarterly 23, 333-344.

Yee, J.R., and Golden, B.L. (1980), “A note on determining operating strategies for probabilistic vehicle routing,” Naval Research Logistics Quarterly 27, 159-163.

Zhand, W., and Korf, R.E. (1996), “A study of complexity transitions on the asymmetric traveling salesman problem,” Artificial Intelligence 81, 223-239.