臺灣博碩士論文加值系統

宅配業之快速發展，造成商品取貨及送貨的服務更為流暢。然而在這競爭激烈的宅配市場中，如何有效的規劃車輛的使用及人力的分配，提高服務水準，而能增加營業額，降低成本，以維持本身競爭優勢，成為業者必須面臨的課題。本研究以宅配業車輛途程規劃為研究主題，以整數規劃建立途程規劃模式，利用模擬退火演算法進行求解，除考量實務上途程規劃的原則外，並同時考慮到總途程成本最小、軟式時間窗之懲罰成本最小及員工工作時數的平準等三個目標。研究結果顯示最終班表均能符合車容量與工作時數12小時限制的硬性限制條件，並儘可能滿足軟性限制。此外，敏感度分析對多種配送狀況探討，並對實務應用及後續研究作建議。

The vehicle routine has been one of the key factors that affect the operational efficiency of door-to-door delivery service companies. A well-planned routine may result not only lower costs, in terms of shorter travel distance of vehicles, less overtime pay for drivers. It also results in higher customer satisfaction due to higher percentage of on-time services. This thesis proposes a multiple-objective integer model to solve vehicle routine problems. To minimize the travel distance of vehicles, to maximize the percentage of on-time services, and to level the working hours of drivers are three objectives of the proposed model. Practical constraints, such as the working hours of drivers should be limited within 12 hours, vehicles are not allowed to be overloaded, are considered. Relaxation technique is used to alleviate the burden of random search of the simulated annealing algorithm that is used to solve the integer model. The computational results show that the simulated annealing algorithm properly solves the relaxed model. The vehicle routine obtained by the model does not violate any of the hard constraints. Only a couple of vehicles can not satisfy few soft constraints. A sensitivity analysis is also conducted based upon various situations, such city vs urban customers, different time windows, and etc. Recommendations for both practical applications and academic research are made.

目 錄
摘 要 I
Abstract II
誌 謝 III
目 錄 IV
圖表索引 VII
1. 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 6
1.3 研究假設 7
1.4 論文架構 8
2. 文獻探討 10
2.1 車輛途程問題介紹 10
2.1.1 車輛途程問題之沿革 10
2.1.2 車輛途程問題之基本模式 13
2.1.3 途程問題之整理 18
2.2 時窗限制下車輛途程問題 21
2.3 含取貨條件下車輛途程問題 26
2.4 模擬退火法 34
2.4.1 Metropolis演算法 36
2.4.2 模擬退火法 38
2.5 小結 42
3. 研究方法 43
3.1 車輛途程問題之目標 43
3.2 符號定義 44
3.3 數學規劃模式之建構 46
3.4 鬆弛模式 51
3.5 模擬退火演算過程 54
4. 實證分析 59
4.1範例描述 59
4.2 模擬結果 62
4.3 配送狀況分析 68
4.3.1 配送地點集中或分散 68
4.3.2 貨品指定送達時段 73
4.3.3 配送需求量狀況分析 76
5. 結論與建議 83
5.1 結論 83
5.2 未來研究方向與建議 86
參考文獻 88
附錄 97
作 者 簡 介 116

參考文獻
中文部分
王治元，「智慧型基因演算法於多目標排程之發展與應用—以PCB鑽孔作業為例」，碩士論文，元智大學工業工程與管理系碩士班（2004）。
王保元，「物流中心冷凍食品配送模式之研究」，碩士論文，朝陽大學工業工程與管理系碩士班（1999）。
王耿彬，「應用遺傳演算法於低溫物流中心之車輛配送排程規劃」，碩士論文，朝陽科技大學工業工程與管理系碩士班（2001）。
王裕元，「應用多目標決策模式建立護理人員排班方式之研究」，碩士論文，國立屏東科技大學工業管理系碩士班（2003）。
呂昆達，「反應需求式宅配車輛排程與派遣系統之建立」，碩士論文，國立交通大學交通運輸系碩士班（2004）。
林宗毅、余辰祐、黃科智，「途程規劃之探討—以宅急便為例」，實務專題報告，國立屏東科技大學工業管理系（2006）。
物流資訊網，http://link.disc.com.tw/Common/main.asp。
邱柏憲，「多元服務物流轉運中心模糊車輛派遣之研究」，碩士論文，國立雲林科技大學工業管理系碩士班（2001）。
林耿暘，「深層海水物流運輸模式分析─以水產養殖運輸為例」，碩士論文，國立屏東科技大學工業管理系碩士班（2005）。
徐俊誠，「車輛途程含取貨問題解法之研究」，碩士論文，大葉大學工業管理系碩士班（1999）。
翁基華，「在工作負荷與總距離考慮下之配送車輛途程方法研究」，碩士論文，國立中興大學農產運銷系碩士班（1997）。
逢甲大學物流系統規劃實驗室，http://140.134.72.87/main/mbie/logistics.htm（2004）。
陳百傑，「以啟發性演算法求解時窗限制車輛途程問題」，碩士論文，中原大學工業工程系碩士班（2001）。
陳契伸，「硬性/軟性時窗限制之車輛途程問題研究」，碩士論文，中原大學工業工程研究系碩士班（2001）。
莊英群，「應用禁忌搜尋法於混合送收貨之車輛途程問題」，碩士論文，逢甲大學工業工程系碩士班（2003）。
陳振，「風起雲湧-台灣宅配戰國元年」，物流技術與戰略，第16期，62-69（2000）。
張容瑄，「模擬退火法在校車路線問題上的應用」，碩士論文，國立中正大學數學系碩士班（2002）。
許晉嘉，「宅配業貨物配送路線規劃問題之研究」，碩士論文，國立成功大學交通管理科學系碩士班（2003）。
游文松，「公路客運人員與車輛排班之研究」，碩士論文，中華大學科技管理系碩士班（2004）。
番成正，「優勢水流對坡地安定影響之研究 - 以草嶺為例」，碩士論文，國立成功大學資源工程系碩士班（2003）。
黃冠雄，「時效導向的娃娃車接送之車輛途程問題-以禁忌搜尋法求解」，碩士論文，國立中正大學數學系碩士班（2002）。
彭冠儒，「考量同時送貨及收貨之車輛途程問題」，碩士論文，逢甲大學 工業工程系碩士班（2002）。
曾惠鈺，「及時行車資訊下物流配送作業規劃之研究」，碩士論文，淡江大學運輸管理系碩士班（2003）。
廖忠雄，「物流中心運輸服務途程規劃」，碩士論文，國立台灣大學工業工程系碩士班（1994）。
廖國維，「應用多目標規劃建構護理人員非週期性最佳班表之研究」，碩士論文，國立屏東科技大學工業管理系碩士班（2005）。
熊碩成，「以實驗設計改善時窗限制下物流中心車輛途程問題之研究」，碩士論文，國防管理學院資訊系碩士班（2001）。
蔡志強，「以蟻群系統建立物流宅配最佳化配送路徑規劃」，碩士論文，國立屏東科技大學工業管理系碩士班（2004）。
蔡宗明，「滿足多目標之護理人員最佳化班表之探討」，碩士論文，國立屏東科技大學工業管理系碩士班（2004）。
歐陽恬恬，「宅配經營特性分析與郵局面對宅配之挑戰與因應」，碩士論文，國立臺灣大學土木工程學系碩士班（1999）。

英文部分
Alfa, S., S. Heragu and M. Chen, “A 3-opt Based Simulated AnnealingAlgorithm for Vehicle Routing Problem,” Computers & Industrial Engineering, 21, 635-639 (1991).
Baker, E. and J. R. Schaffer., “Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints,” American Journal of Mathematical and Management Sciences, 6, 261-300 (1986).
Bartholdi, J. J. and L. K. Platzman, “Heuristics based on spacefilling curved for combinatorial problems in Euclidean space,” Management Science, 34, 291-305 (1988).
Beasley, J., “Route-First Cluster-Second Methods for Vehicle Routing,”Omega, 11, 403-408 (1983).
Bodin, L. D. and B. L. Golden, A. A. Assad and M. Ball, “Routing and scheduling of vehicles and crews, the state of the art,” Computers and Operations Research, 10(2), 63-212 (1983).
Bodin, L., “Twenty Years of Routing and Scheduling,” Operations Research, 38(4), 571-579 (1990).
Casco, D. O., B. L. Golden and E. A. Wasil, “Vehicle routing with backhauls: Models, algorithms, and case studies,” In: Golden, B.L., Assad, A.A. (Eds.), Vehicle Routing: Methods and Studies. Elsevier, Amsterdam, 127-147 (1988).
Chen, J. F., “Approaches for the vehicle routing problem with simultaneous deliveries and pickups,” Journal of the Chinese Industrial Engineers, 23(2), 141-150 (2006).
Christofides, N., A. Mingozzi and P. Toth, “The vehicle routing problem,” Combinatorial Optimization, Wiley, Chichester, 325-338 (1979).
Christofides, N., “Vehicle routing, In: Lawler, E. L., J. K. Lenstra, A. H. G. Rinnooy Kan, and Shmoys, D. B. (eds),” The traveling Salesman Problem, 431-448 (1985).
Clarke, G. and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, 12, 568-581 (1964).
Dantzig, G. B. and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, 6, 80-91 (1959).
Desrochers, M., J. Desrosiers and M. Solomon, “A new optimization algorithm for the vehicle routing problem with time windows,” Operations Research, 40, 342-354 (1992).
Du, T. C., E. Y. Li and D. Chou, “Dynamic vehicle routing for online B2C Delivery,” Omega, 33, 33-45 (2005).
Duhamel, C., J. Y. Potvinn and J. M. Rousseau, “A Tabu search heuristic for the vehicle routing problem with backhauls and time windows,” Transportation Science, 31, 49-59 (1997).
Fisher, M. L. and R. Jaikumar, “A generalized assignment heuristic for vehicle routing problems,” Network, 11, 109-124 (1981).
Gendreau, M., A. Hertz and G. Laporte, “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, 40, 1276-1290 (1994).
Gillett, B. E. and L. R. Miller, “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, 22, 340-349 (1974).
Golden, B., E. Baker, J. Alfaro and J. Schaffer, “The vehicle routing problem with backhauling: two approaches,” Proceedings of the Twenty-First Annual Meeting of S.E.TIME, Myrtle Beach, 2, 90-92 (1985).
Hwang, H. S., “An improved model for vehicle routing problem with time constraint based on genetic algorithm,” Computer & Industrial Engineering, 42, 361-369 (2002).
Ioannou, G., M. Kritikos and G. Prastacos, ”A problem generator-solver heuristic for vehicle routing with soft time windows,” omega, 31, 41-53 (2003).
Johnson, D. S., C. R. Aragon, L. A. McGeoch and S. Catherine, “Optimization by simulated annealing: Anexperimental evaluation; Part 1, ” Graph partitioning, 37(6), 865-892 (1989).
Kirkparick, S., Jr. C. D. Gelett and M. P. Vecchi, “Optimization by Simulated Annealing, ” Science, 220(4598), 671-680 (1983).
Kontoravdis, G. and J. Bard, “A GRASP for the vehicle routing problem with time windows,” ORSA Journal on Computing, 7(1), 10-23 (1995).
Krolak, W. F. and J. Nelson, “A Man-Machine Approach Toward Solving The Generalized Truck Dispatching Problem,” Transportation Science, 6, 149-170 (1972).
Lenstra, J. and K. Rinnooy, “Complexity of vehicle routing and scheduling problem”, Network, 11(2), 221-227 (1981).
Lin, S., “Computer solutions of the traveling salesman problem,” Bell System Tech. J, 44, 2245-2269 (1965).
Louis, S. J., X. Yin and Z. Y. Yuan, “Multiple Vehicle Routing with Time Windows Using Genetic Algorithms, ” IEEE Proceedings of the 1999 Congress on Evolutionary Computation, 3, 1804-1808 (1999).
Metropolis, N., A. Rosenbluth and M. N. Rosenbluth, A. Teller and E. Teller, “ Journal of Chemical Physics,” 21, 1087-1092 (1953).
Min, H., “The multiple vehicle routing problem with simultaneous delivery and pick-up points,” Transportaion research.Part A, 377-386 (1989).
Mole R. H. and S. R. Jameson, “A sequential route-bulding algorithm employing a generalised savings criterion,” Operational Research Quarterly, 27, 503 (1976).
Nagy, G. and S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” European Journal of Operational Research, 162, 126-141 (2005)
Rochat, Y. and E. D. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, 1, 147-167 (1995).
Salhi, S. and G. Nagy, “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling,” Journal of the Operational Research Society, 50, 1034-1042 (1999).
Solomon, M., “Algorithms for the Vehicle Routing and Scheduling with Time Window Constraints,” Operations Research, 15, 254-265 (1987).
Tang, F. A. and R. D. Galvão, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,” computer & operations research, 33, 595-619 (2006).
Thompson, P. M. and H. Psaraftis, “Cyclic Transfer Algorithms for Multi- Vehicle Routing and Scheduling Problems,” Operations Research, 41, 935-946 (1993).
Zhong, Y. and M. H. Cole, ”A vehicle routing problem with backhauls and time windows: a guided local search solution,” Transportation Research, 41, 131-144 (2005).
Zhu, K. Q., ”A New Genetic Algorithm for VRPTW,” Proceedings of the 4th International Conference on Genetic Algorithm, Las Vegas, U.S.A. (2000).