1. NCHU Institution Repository
  2. 理學院
  3. 資訊網路與多媒體研究所
Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19826
標題: 利用梯度逼近技巧解決最短車輛路徑之問題
A Gradient-Based Technique for Near-Shortest Paths in Vehicle Routing Problem
作者: 張志嘉
Chang, Chih-Chia
關鍵字: Gradient;梯度;Vehicle Routing;Shortest Path;Optimization;Grid Computing;車輛繞徑;最短路徑;最佳化;網格計算
出版社: 資訊網路多媒體研究所
引用: 1. G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Management Science, Vol. 6, No. 1, pp. 80-91, 1959. 2. P. Tsirimpas, A. Tatarakis, I. Minis and E. G. Kyriakidis, “Single vehicle routing with a predefined customer sequence and multiple depot returns,” European Journal of Operations Research, Vol. 187, Iss. 2, pp. 483-495, 2008. 3. A. Tatarakis and I.Minis, “Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns,” European Journal of Operations Research, Vol. 197, Iss. 2, pp. 557-571, 2009. 4. G. Cornuejols and G. L. Nemhauser, “Tight bounds for Christofides’ traveling salesman heuristic,” Mathematical Programming, Vol. 14, No. 1, pp. 116-121, 2009. 5. M. Gendreau, G. Laporte and A. Hertz, “An approximation algorithm for the traveling salesman problem with Backhauls,” Operations Research, Vol. 45, No. 4, pp. 639-641, 1997. 6. M. Reimann, K. Doerner and R. F. Hartl, “D-ants: Savings based ants divide and conquer the vehicle routing problem,” Computers & Operations Research, Vol. 31, No. 4, pp. 563-591, 2003. 7. B. L. Golden and E. A. Wasil, “Computerized vehicle routing in the soft drink industry,” Operations Research, Vol. 35, Iss. 1, pp. 6-17, 1987 8. L. Bodin and B. Golden, “Classification in vehicle routing and scheduling,” Networks, Vol. 11, Iss. 2, pp. 97-108, 1981. 9. M. Desrochers, J. Desrosiers and M. Solomon, “A new optimization algorithm for the vehicle routing problem with time windows,” Operations Research Society of America, Vol. 40, No. 2, pp. 342-354, 1992. 10. A. S. Kenyon and D. P. Morton, “Stochastic vehicle routing with random travel times,” Transportation Science, Vol. 37, No. 1, pp. 69-82, 2003. 11. G. M. Giaglis, I. Minis, A. Tatarakis and V. Zeimpekis, “Minimizing logistics risk through real-time vehicle routing and mobile technologies,” International Journal of Physical Distribution & Logistics Management, Vol. 34, Iss. 9, pp.749-764, 2004. 12. J. K. Lenstra and A. H. G. Rinnooy Kan, “Complexity of vehicle routing and scheduling problems,” Networks, Vol. 11, Iss. 2, pp.221-227, 1981. 13. B. E. Gillett and L. R. Miller, “A heuristic algorithm for the vehicle-dispatch problem, Operations Research,” Operations Research, Vol. 22, No. 2, pp. 340-349, 1974. 14. S. P. Gayialis and I. P. Tatsiopoulos, “Design of an IT-driven decision support system for vehicle routing and scheduling,” European Journal of Operational Research, Vol. 152, Iss. 2, pp. 382-398, 2004. 15. M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997. 16. B. M. Baker, M. A. Ayechew, “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, Vol. 30, Iss. 5, pp. 787-800, 2003. 17. J.-Y. Wang and K.-F. Jea, “A near-optimal database allocation for reducing the average waiting time in the grid computing environment,” Information Sciences, Vol. 197, Iss. 21, pp. 3772-3790, 2009. 18. I. F. A. Vis, “Survey of research in the design and control of automated guided vehicle systems,” European Journal of Operational Research, Vol. 170, Iss. 3, pp. 677-709, 2006. 19. Y. A. Bozer and M. M. Srinivasan, “Tandem AGV systems: A partitioning algorithm and performance comparison with conventional AGV system,” European Journal of Operational Research, Vol. 63, Iss. 2, pp. 173-191, 1992. 20. P. Toth and D. Vigo, The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, 2002. 21. J. A. Tompkins and J. A. White, Facility Planning, Wiley, New York, 1984. 22. M. M. Flood, “The traveling salesman problem,” Operations Research, Vol. 4, No. 1, pp. 61-75, 1955. 23. B. F. Field and J. G. Kasper, Automated Guided Vehicle, US Patent 4790402, 1988. 24. 林依潔, Integration of Fuzzy Theory and Ant Algorithm for Vehicle Rouing Problem with Time Window, 碩士論文，國立台北科技大學, 2003. 25. 游展宗, Minimizing the AGV Cycle Time by the Job Sequence Generated by a Genetic Algorithm, 碩士論文，國立交通大學, 2008. 26. 陳昱皓, Solving a Two-stage Problem with Scheduling and Delivery in Supply Chain by Tabu Search Algorithm, 碩士論文，國立交通大學, 2003.
摘要: 
針對單車輛配送多重種類貨物的車輛繞徑問題，本論文利用梯度逼近的最佳化技巧，快速求得車輛繞徑的近似最佳路線。本研究的動機是來自經常使用於大型批量生產工廠內的物料搬運系統或大型的物流中心之車輛指派規劃，必需在短時間內求得最短的車輛行徑路線。我們首先將車輛繞徑問題從整數空間映射到實數空間，得到轉換後的新問題，接下來利用梯度逼近技巧在實數空間中求得新問題的近似最佳解答，最後再將此近似最佳解答轉換回原先整數空間問題的解答，得到原問題的近似最佳解答。利用此技巧，車輛路線的指派中心可以在短時間內獲得較佳的繞徑路線，降低車輛繞徑成本。
URI: http://hdl.handle.net/11455/19826
其他識別: U0005-3101201111522500
Appears in Collections:資訊網路與多媒體研究所

Show full item record
 
TAIR Related Article

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.