多車種車輛路線問題啟發式解法之研究

Abstract

許多行業中，物流配送活動在其管理決策上扮演著一個相當重要的角色， 同時，如何將配送作業電腦化也是商業自動化相當重要的一環，然而配送 作業的重點在於如何有效的使用車輛以及決定其經濟行駛路線，尤其是正 面臨國際能源日漸短缺的今天，更見其重要性。目前世界上有關車輛路線 問題研究雖然不少，但大都假設只擁有一種車種，然而在現實社會中，物 流配送中心所使用的車輛卻不只一種，因此如何求解多車種車輛路線問 題(FSMVRP, Fleet Size and Mixed Vehicle Routing problem) 是一個 很重要的研究課題。目前世界上FSMVRP 的演算法以Bruce Golden 等人所 發展的(MGT+OrOPT)5 演算法與的演算法表現最佳。本研究合併此二演算 法，以C 語言在MS-Windows 上發展出求解FSMVRP 的兩種創新的啟發式解 法MGORSR3 與MGSROR3 。兩種啟發式解法均為三階段求解法。第一階段均 以MGT , 即多巨網切割法求解初始解。第二及第三階段則分別採不同之先 後次序執行改良後的 Or-OPT 交換法與修正的SR(Salhi and Rand) 擾動 法。以文獻上所使用的20 題測試例題測試此兩種演算法，發現MGORSR3演 算法與MGSROR3 演算法分別得到3 題和4 題現有最佳解，其中包括3 題新 發現的現有最佳解，且與文獻的現有最佳解的平均誤差分別僅為1.04% 與0.73%。 Two new combined heuristic methods for Fleet Size and Mixed Vehicle Routing Problem(FSMVRP) are present- ed in this thesis. Both heuristic methods are 3-stage heuristic methods. In the first stage, an initial sol- ution is generated by MGT, Multiple Giant Tour, metho- ds. The second and third stage are solution improveme- nt procedures. We revised both Or-OPT exchange heuris- tic and Salhi and Rand's(SR) perturbation procedure, and implemented them in different sequential order. Although both of the heuristics of MGORSR3 and MGSROR3 has the same first solution generated by the MGT heur- istic, MGORSR3 executes the revised Or-OPT heuristic before the modified SR( Salhi and Rand) perturbation method while MGSROR3 implements the two solution impr- ovement procedures in the reversed order. These two heuristic methods are coded in Borland C++, and are implemented on a MS-Windows in 486 PC. The set of 20 test problems reported by Bruce Golden et. al. was adopted to evaluate the performance of all the heuristic methods. As compared with the other heu- ristic methods, MGSROR3 on the average generates slig- htly more accurate results for the set of 20 test pro- blems. In particular, the heuristic methods which is presented in this thesis have yielded three new best available solution. The overall results seem to indic- ate that MGSROR3 provides a good solution tool for FSMVRP.