| 摘要: | 本研究探討新車運送裝載與路線規劃問題 (Auto-Carrier Transportation Problem, ACTP)，ACT中問題中包含三個求解難度高的子問題：(1) 新車選擇與分群問題、(2) 新車裝載規劃問題 (Auto-Carrier Loading Problem, ACLP) 與 (3) 拖車途程規劃問題。ACTP相關文獻較少，且過去探討新車運送之相關文獻皆只針對其中一個子問題處理，即使有文獻同時處理同時考慮上述子問題，但仍對該問題有許多簡化以降低求解困難度。Agbegha et al. (1998) 曾探討ACTP問題中的第二個子問題：ACLP問題，該文獻將ACLP問題建構為幾何指派問題，並針對該問題提出一分枝界限求解演算法。但該研究中未考慮進出口車位重覆計算的問題與空車位問題，且其分枝求解概念複雜不易執行。在第三章，本研究重新建構ACLP整數規劃模型並提出ACLP啟發式演算法。ACLP演算法搭配預先設定的新車指派策略與裝載成本下限計算，經9題範例測試，ACLP演算法在其中6題範例求解效果優於Agbegha et al. (1998)，另3題結果與之相同。第四章進一步討論循序性新車裝載規劃問題 (Sequential Auto-Carrier Loading Problem, SACLP)，此問題主要概念為放寬“重裝載新車必須放置回原車位”假設，本研究建構一循序式混合整數規劃模型，其目標式為最小化拖車在路線內各交車中心中產生之重裝載成本。此外本研究亦提出SACLP求解演算法，其主要概念與ACLP演算法相同，但考慮拖車在運送過程中產生之空車位，在拖車卸下需求新車後，允許重裝載新車放置於較佳車位。根據4個例題測試結果，SACLP演算法可進一步改善ACLP的重裝載成本。本研究於第五章整合所有子問題，提出ACTP整數規劃模型，其目標式為最大化新車急迫指標與利潤，並最小化新車重裝載成本與拖車路線旅行成本，本研究發展出兩階段ACTP啟發式演算法求解該問題。在演算法第一階段利用新車指派策略與節點插入法將需運送新車指派到拖車車位中，並建構初始拖車路線，第二階段再採用ACLP演算法改善初始解裝載成本。經測試8題新車運送範例測試發現，兩階段ACTP演算法之運算結果優於ILOG數學最佳化軟體，顯示該演算法具有實務應用價值。This dissertation studies the Auto-Carrier Transportation Problem (ACTP) which consists of three subproblems, i.e., car selection and clustering problem, auto-carrier loading problem (ACLP), and auto-carrier routing problem. Very limited references are available in the literature. Though each subproblem may have been well dealt with in the past, to the best of our knowledge, none of articles in the literature have tackled on all three subproblems as a whole, or at least, with significant simplifications.The second subproblem, i.e., ACLP, has been elaborately tackled by Agbegha et al. (1998) who formulated it as a geometric assignment problem and proposed a solution heuristic involving a branch and bound procedure for solutions. Unfortunately, in their model formulation, the erratic computation of the number of reloads due to the existence of empty slots as well as that associated with the exit slot is not well treated. In addition, their proposed heuristic algorithm is applicable only for a very specific branching rule which is not appreciated in practice. In Chapter 3, we revisited the ACLP by reformulating it as an integer programming model, proposing a novel heuristic algorithm, and finally demonstrating with numerical examples. The results from 9 instances indicate the our approach performs better than Agbegha et al.’s (1998) by obtaining 6 better solutions while getting 3 the same quality solutions.In Chapter 4, we explore the Sequential Auto-Carrier Loading Problem (SACLP) which is essentially an extension of the ACLP by relaxing the assumption of “if at any auto-dealer, a car is unloaded and reloaded again, it is reloaded back to its original slot.” The SACLP is formulated as a series of mixed integer mathematical programming problem in which the objective function is to minimize the number of reloads at each auto-dealer (AD) along the auto-carrier route. A repetitive heuristic algorithm, which is essentially modified from the heuristic algorithm developed in Chapter 3 by taking the generated empty slots at each AD into consideration, is proposed for the SACLP. At each auto-dealer (AD), after its demand has been unloaded, the unloaded cars destined for later ADs are reloaded back to the “better” unassigned slots of the auto-carrier (AC). Computational experiments on four instances indicate that the solutions obtained from the Auto-Carrier Loading Problem (ACLP) can be further improved by the SACLP.In Chapter 5, the Auto-Carrier Transportation Problem (ACTP), in which the objective function maximizes the profit by loading the most critical and valuable cars as well as minimizes the total reloading and routing cost subject to a set of constraints is elaborately studied. The ACTP is formulated as an integer programming model and solved by a proposed two-stage heuristic algorithm. In the first stage, the delivery-ready cars with known destinations are assigned to the available auto-carriers which are also routed based on the insertion method to fulfill the demands of the destinations. In the second stage, the loading assignment made for each auto-carrier (AC) is further improved by the proposed ACLP heuristic algorithm. Computational experiments with eight instances indicate that our two-stage heuristic algorithm outperforms a constraint programming software, called ILOG-OPL, and hence has great potential to be applied in the real situations. |
