臺灣博碩士論文加值系統

車輛途程含回程取貨問題是車輛途程問題的延伸，其定義為車輛完成送貨作業之後，在回程時可以進行取貨的作業。但在很多實際的情形下，需求點通常會有同時取貨送貨的需求，所以寬放需求點可能同時需要送貨及取貨的情況；另外當需求點的需求量大於車容量時，就必須要考慮分批送貨。因此本研究的基本假設是建立在需求點可能同時需要送貨及取貨的情況，且允許分批送貨和取貨，加上不違背車容量限制和時窗限制，來求解最小總路徑成本的規劃。
本研究的目的為建構一個符合本研究的數學模式，並且利用禁忌搜尋法進行求解，探討平均需求量與車容量的比值和需求量的變異數，決定是否採用分批策略；另外針對違反時窗懲罰成本進行敏感度分析。實驗結果顯示，當平均需求量為車容量的一半以上但不超過四分之三，且需求量變異數較小時，採用分批策略可以獲得較佳的結果；當違反時窗懲罰成本增大時，採用分批策略對於節省路徑成本的效果越明顯。

Vehicle Routing Problem with Backhauls is an extensive problem of the Vehicle Routing Problem. For the most of past research, the carrier can pick up goods on the way back after a delivery trip is finished is assumed. However, in many real cases, those two demands, pick-up and delivery, might be occurred on the same demand point, simultaneously. Meanwhile, if the needs of demand points are greater than the volume of vehicles, split delivery is considered. The addressed problem is solved in two ways. First, a mathematical programming model is constructed for solving the problem optimally. Following, a tabu search based heuristic is presented to obtain a near optimal solution. In the experiment analysis stage, a variety of delivery environments based on the ratio of average demand and vehicle volume, and variation of demands are analyzed. The experimental results have shown that split delivery turns out to be more successful when the average demand is half to 3/4 greater than the vehicle volume and the variable of demand is smaller. The greater the punishment cost of time window violation increases, the more successful the split delivery is concluded as well.

摘要 ii
Abstract iii
目錄 v
圖目錄 vii
表目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍 4
1.4 研究流程 5
第二章 文獻探討 8
2.1 車輛途程問題 8
2.1.1 參數與變數之定義 9
2.1.2 車輛途程問題之數學模式 10
2.1.3 車輛途程問題之相關啟發式解法 11
2.2 車輛途程問題含時窗限制 12
2.2.1 參數與變數之定義 13
2.2.2 車輛途程問題含硬時窗限制之數學模式 13
2.2.3 車輛途程問題含軟時窗限制之數學模式 14
2.2.4 車輛途程問題含時窗限制之相關啟發式解法 15
2.3 車輛途程問題含回程取貨 15
2.3.1 參數與變數之定義 16
2.3.2 車輛途程問題含回程取貨之數學模式 16
2.3.3 車輛途程問題含回程取貨之相關啟發式解法 18
2.4 車輛途程問題含混合送貨和取貨 18
2.4.1 參數與變數之定義 19
2.4.2 車輛途程問題含混合送貨、取貨之數學模式 19
2.4.3 車輛途程問題含混合送貨和取貨之相關啟發式解法 20
2.5 車輛途程問題含分批送貨 21
2.5.1 參數與變數之定義 22
2.5.2 車輛途程問題含分批送貨之數學模式 22
2.5.3 車輛途程問題分批送貨之相關啟發式解法 23
2.6 車輛途程問題彙整 26
2.7 小結 26
第三章 數學模式建立 28
3.1 問題描述 28
3.2 變數定義 29
3.3 數學規劃模式 30
3.4 本研究數學模式驗證 32
3.4.1 需求量大於車容量時的模式驗證 32
3.4.2 需求量小於車容量時的模式驗證 33
第四章 考慮混合分批送貨和取貨車輛途程問題之啟發式方法 35
4.1初始途程建構階段 35
4.2 禁忌搜尋法 38
4.3 鄰近解改善階段 41
4.3.1 途程間改變分批點交換 41
4.3.2 途程間2-opt*交換 42
4.3.3 途程間1-0節點交換 43
4.3.4 途程間1-1節點交換 44
4.3.5 途程內2-opt節線交換 45
4.4 演算法例題說明 46
第五章 例題測試與分析 49
5.1 測試例題說明 49
5.2 禁忌搜尋法參數設計 50
5.3 求解品質測試 55
5.4 本研究例題求解 57
5.4.1 送貨需求75%，取貨需求50% 57
5.4.2 送貨需求75%，取貨需求60% 61
5.5 敏感度分析 65
第六章 結論與未來研究方向 73
6.1 結論 73
6.2 未來研究方向 73
參考文獻 74
附錄一 產生Beta分配 78
附錄二 小規模測試例題資料 79
附錄三 MP-ES演算法 84

1.彭冠儒，2002，考量同時送貨及收貨之車輛途程問題，逢甲大學工業工程研究所，碩士論文。
2.陳契伸，2001，硬性軟性時窗限制之車輛途程問題研究，中原大學工業工程研究所，碩士論文。
3.徐俊誠，2000，車輛途程含取貨問題解法之研究，大葉大學工業工程研究所，碩士論文。
4.敖君瑋，1999，禁制搜尋法於軟性時窗限制之車輛途程問題研究，元智大學工業工程研究所，碩士論文。
5.郭維凌，1999，負載變動與需求分割條件下車輛途程問題之研究，中華大學工業工程管理研究所，碩士論文。
6.經濟部商業司，2000，物流經營管理實務，修訂版，經濟部，台北市。
7.Archetti, C., Savelsbergh, M.W.P., Speranza, M.G., 2008, “To split or not to split: That is the question”, Transportation Research Part E, vol. 44, pp. 114-123.
8.Alfred, F., Montane, T., Galvao R.D., 2006, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers & Operations Research, vol. 33, pp. 595-619.
9.Archetti, C., Savelsbergh, M.W.P., Speranza, M.G., 2006, “Worst-case analysis for split delivery vehicle routing problems”, Transportation Science, vol. 40, pp. 226–234.
10.Archetti, C., Hertz, A., Speranza, M.G., 2006, “A tabu search algorithm for the split delivery vehicle routing problem”, Transportation Science, vol. 40, pp. 64–73.
11.Clarke, G., Wright, J., 1964, “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, vol. 12, pp. 568-581.
12.Duhamel, C., Potvin, J., Rousseau, J., 1997, “A tabu search heuristic for the vehicle routing problem with backhauls and time windows”, Transportation Science, vol. 31, no.1, pp. 49-59.
13.Dethloff, J., 2001, “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum, vol. 23, pp.79–96.
14.Dror, M., Trudeau, P., 1990, “Split delivery routing”, Naval Research Logistics, vol. 37, pp. 383-402.
15.Dror, M., Trudeau, P., 1989, “Savings by split delivery routing”, Transportation Science, vol. 23, pp. 141–145.
16.David M., Olli B., Wout D., 2007,“A multi-parametric evolution strategies algorithm for vehicle routing problems”, Expert Systems with Applications 32 pp.508–517.
17.Fisher, M.L., Jaikumar, R., 1981, “A generalized assignment heuristic for vehicle routing”, Networks, vol. 11, pp. 109-124.
18.Fisher, M., Vehicle routing, in: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L., (Editors), 1995, “Handbooks in Operations Research and Management Science”, vol. 8: Network Routing, North-Holland, Amsterdam, pp.1-33.
19.Fisher, M.L., Jornsten, O., Madsen O.B., 1997, “Vehicle Routing with Time Windows : Two Optimization Algorithms”, Operations Research, vol. 45, pp. 488-492.
20.Frizzell, P.W., Giffin, J.W., 1995, “The split delivery vehicle scheduling problem with time windows and grid network distances”, Computers & Operations Research, vol. 22, pp. 655–667.
21.Goetschalckx, M., Jacobs-Blecha, C., 1989, “The vehicle routing problem with backhauls”, European Journal of Operational Research, vol. 42, pp. 39-51.
22.Golden, B., Baker, E., Alfaro, J., Schaffer, J., 1985, “The vehicle routing problem with backhauling: two approaches”, Proceedings of the Twenty-First Annual Meeting of S.E.TIMS, Myrtle Beach, Sc, 90-92.
23.Gillet, B., Miller, L., 1974, “A heuristic algorithm for the vehicle dispatch problem”, Operations Research, vol. 22, pp. 340- 349.
24.Ho, S.C., Haugland, D., 2004, “A tabu search heuristic for the vehicle routing problem with time windows and split deliveries”, Computers & Operations Research, vol. 31, pp. 1947–1964.
25.Konskosidis, A., Powell, W.B., Solomon, M.M., 1992. “An optimization-based heuristic for vehicle routing and scheduling with soft time window constrains”, Transportation Science, vol. 26, pp. 69-85.
26.Lin, S., and Kernighan, B., 1973, “An effective heuristic algorithm for the traveling salesman problem”, Operation Research, vol. 21, pp. 498-516.
27.Min, H., 1989, “The multiple vehicle routing problem with simultaneous delivery and pickup points”, Transportation Research A, vol. 23, pp. 377–386.
28.Osman, I.H., 1993, “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem”, Annals of Operational Research, vol. 41, pp. 421-451.
29.Potvin, J.Y., Kervahut, T., Garcia, B.L., Rousseau, J.M., 1996, “The Vehicle Routing Problem with Time Windows Part I: Tabu Search”, Informs Journal on Computing 8:2, pp. 158-164.
30.Salhi, S., Nagy, G., 1999, “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling”, Journal of the Operational Research Society, vol. 50, pp. 1034–42.
31.Solomon, M., 1987, “Algorithm for the vehicle routing and scheduling problem with time window constrain”, Operations Research, vol. 35, pp. 254-265.
32.Taillard, E., Badeau, P., Gendreau, M.M., Guertin, F., Potvin, J, 1997, “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation Science, vol. 31, pp. 170-186.
33.Toth, P., Vigo, D., 1997, “An exact algorithm for the vehicle routing problem with backhauls”, Transportation science, vol. 31, no.4, pp. 372-385.
34.Van Breedam A., 1995, “Improvement heuristics for the vehicle routing problem based on simulated annealing”, European Journal of Operational Research, vol. 86, pp. 480-490.