| 摘要(英) |
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.
|
| 參考文獻 |
[ 1 ] 林志鴻與陳春益，2002，「新車裝載問題之研究」，運輸計畫季刊，第31卷，第4期，頁765-794。
[ 2 ] 林志鴻，2005，「考量板架具相同裝載限制之新車配送路線規劃問題」，運輸學刊，第17卷，第4期，頁393-422。
[ 3 ] Agbegha, G.Y., Ballou, R.H., Mathur, K., 1998, “Optimizing auto-carrier loading. Transportation Science,” Vol. 32, No. 2, pp.174-188.
[ 4 ] Avriel, M., Penn, M., Shpirer, N., 2000, “Container ship stowage problem: complexity and connection to the coloring of circle graphs. Discrete Applied Mathematics,” Vol. 103, pp. 271-279.
[ 5 ] Chang, T.S., Liao, Y.F., 2008, “Path finding with storage consideration in a mixed pickup-delivery and specified-node network,” Transportation Research Part E. Vol. 44, pp. 970-985.
[ 6 ] Gendreau, M., Iori, M., Laporte, G., Martello, S., 2006, “A tabu search algorithm for a routing and container loading problem,” Transportation Science. Vol. 40, No. 3, pp. 342-350.
[ 7 ] Iori, M., Salazar Gonzalez, J.J., Vigo, D., 2007, “An exact approach for the Vehicle Routing Problem with two dimensional loading constraints,” Transportation Science. Vol. 41, No.2, pp. 253-264.
[ 8 ] MacQueen, J., 1967, “Some methods for classification and analysis of multivariate observations,” Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Vol. I, Statistics. Edited by Le Cam, L.M. and Neyman, J., University of California Press.
[ 9 ] Tadei, R., Perboli, G., Della Croce, F., 2002, “A heuristic algorithm for the auto-carrier transportation problem,” Transportation Science. Vol. 36, No. 1, pp. 55-62.
[ 10 ] Zachariadis, E.E., Tarantilis, C.D., Kiranoudis, C.T., 2009, “A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research,” Vol. 195, No. 3, pp. 729-743.
|
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit