應用行產生法求解考量交通壅塞時間與 軟時間窗格之車輛途程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：39

、訪客IP：3.133.111.29

姓名

江承璋(Cheng-Chang Chiang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

應用行產生法求解考量交通壅塞時間與軟時間窗格之車輛途程問題
(Using Column Generation to Solve the Vehicle Routing Problem with Soft Time Window and Traffic Congestion Time)

相關論文

★ 應用失效模式效應分析於產品研發時程之改善	★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究	★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例	★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)	★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例	★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例	★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例	★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例	★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

這篇論文主要探討是應用行產生法求解考量交通壅塞時間與軟時間窗格之車輛途程問題，在這問題中當車輛無法在各顧客特定時間窗格內服務顧客即會產生一懲罰成本加入目標式，並在特定的時間區間產生交通壅塞的尖峰時段，以上兩種性質都增加了求解可行解的困難度，在解法上我們利用行產生法的求解模式進行求解並利用動態規劃對子問題進行求解，在線性規劃中"行"用來表示路徑，並建立一子問題用來產生新的路徑進一步求出可行路徑及最佳解再利用狀態空間鬆弛法來求解，最後我們利用Solomom的例題進行測試。

摘要(英)

This paper discusses a column generation for the Vehicle Routing Problem subject to soft time window restriction. In this problem, earliness or lateness is allowed although a penalty is incurred and added to solution cost whenever a vehicle serves a customer outside of his time window, and generate traffic congestion within a specific time. Both of them increase the complications of the problem and hard to find feasible solution. We present a column generation algorithm which is the exact optimization algorithm for this problem and then the branch and price help us optimization the result.
In the linear programming column represents the route, and construct subproblem to generate new route for improve the answer and use state-space relaxation for dynamic programs to solve it and then we calculate different size of hard time windows problem that is from “Solomon benchmark problems”.

關鍵字(中)

★ 車輛途程問題
★ 軟時間窗格
★ 交通壅塞時間
★ 行產生法

關鍵字(英)

★ Vehicle routing problem
★ Soft time window
★ Traffic congestion
★ Column generation

論文目次

中文摘要 i
Abstract ii
Table of Content iii
List of Figures iv
List of Tables v
Chapter 1 Introduction 1
1.1 Background 1
1.2 Research Motivation 2
1.3 Research Objective 2
1.4 Research Framework 3
Chapter 2 Literature Review 4
2.1 VRP 4
2.2 VRP with Time Window 6
2.3 Column Generation 7
2.4 Summary 8
Chapter 3 Model 9
3.1 Notation 9
3.2 Definition the problem 10
3.3 Problem Formulation 11
3.4 A column generation for the problem VRPSTW with congestion time 14
3.4.1 A set covering model 15
3.4.2 The Linear Set Covering Solution 16
3.5 Solving the Subproblem 18
3.5.1 label definition 19
Chapter 4 Experimental results 23
4.1 Instance 23
4.2 Performances of the Developed Solution Approaches Over Some Instances in Benchmark Set 24
4.2.1 Discuss long and Short Time Window with Different Low Speed Impact on Cost 27
4.2.2 Discuss the Congestion Time Impact on Cost 30
4.2.3 Discuss the Departure Time Impact on Cost 32
Chapter 5 Conclusions and Future Research 34
References 35

參考文獻

1.Agarwal, Y., K. Mathur, H. M. Salkin.. A set-partitioning-based exact algorithm for the vehicle routing problem. Networks 19 pp.731–749.1989.
2.Balakrishnan.N. Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows. The Journal of the Operational Research Society, Vol. 44, No. 3 pp. 279-287.1993.
3.Baldacci R, Mingozzi A, Roberti R. An exact method for the vehicle routing problem with time windows. In: 20 th International symposium of mathematical programming, Chicago.2009.
4.Bodin, L., Golden, B., Assad, A., Ball, M. , “Routing and scheduling of vehicles and crews: the state of the art,” Computer & Operations Research, Vol. 10, No. 2, pp. 63-211.1983.
5.Brian Kallehauge ,” Formulations and exact algorithms for the vehicle routing problem with time windows.” Computers & Operations Research 35 (2008) pp.2307 – 2330.2008.
6.Bhusiri, Narath; Qureshi, Ali Gul; Taniguchi, Eiichi. “The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem.” Transportation Research Part E, 62, pp.1–22.2014.
7.Dantzig ,G. and Ramser,J. “The Truck Dispatching Problem,” Management Science, Vol. 6, No. 1, pp. 80-91.1959.
8.Desrochers, M., Desrosiers, J. and Solomon ,M..M.. “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows.” Operations Research 40, pp.342–354.1992.

9.Feillet D, Dejax P, Gendreau M, Gueguen C An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44(3):pp.216– 229.2004
10.Federico Liberatore • Giovanni Righini •Matteo Salani, “A column generation algorithm for the vehicle routing problem with soft time windows.” A Quarterly Journal of Operations Research.9(1):pp.49-82.
11.Ferland, J.A., Fortin, L., Vehicles scheduling with sliding time windows. European Journal of Operational Research 38 (2), pp.213–226.1989.
12.Golden, B.L and Assad, A.A. Vehicle Routing: Methods and Studies. North-Holland: Amsterdam.1988.
13.Guo ,Z. G. and Mak, K. L. “A heuristic algorithm for the stochastic vehicle routing problems with soft time windows,” in Proceedings of the Congress on Evolutionary Computation, vol. 2, 2004, pp. 1449–1456.
14.Hashimoto, H. Ibaraki, T. Imahori, S. Yagiura, M. The vehicle routing problem with flexible time windows and traveling times. Discrete Applied Mathematics 154, pp.2271–2290.2006.
15.Ioachim,I.Gelinas,S.Desrosiers,J. and Soumis,F. A dynamic programming algorithm for the shortest path problem with time windows and linear node costs.Networks, 31:pp.193-204, 1998.
16.Kohl N, Desrosiers J, Madsen OBG, Solomon MM, Soumis F. 2-path cuts for the vehicle routing problem with time windows. Transport Sci 33:pp.101–116.1999.
17.Laporte,G. “The Vehicle Routing Problem: An Overview of Exact and Approximate of Operational Research, Vol. 59, No. 3, pp. 345-358.1992.
18.Laporte,G. “Fifty Years of Vehicle Routing,” Transportation Science, Vol. 43, No. 4, pp. 408-416.2009.

19.Jiuping Xu, Fang Yan, Steven Li . Vehicle routing optimization with soft time windows in a fuzzy random environment, Transportation Research Part E 47 ,pp.1075–1091.2001.
20.Kallehauge B, Larsen J, Madsen OBG, Solomon MM. Vehicle routing problem with time windows. In: Desaulniers G, Desrosiers J, Solomon MM, editors. Column generation, GERAD 25th Anniversary Series. New York: Springer;p p. 67–98.2005.
21.Min, H., A multiple objective vehicle routing problem with soft time windows: the case of a public library distribution system. Socio-Economic Planning Sciences 25 (3), pp.179–188.1991.
22.N. Azi, M. Gendreau and J.-Y. Potvin, “An Exact Algorithm for and Multiple Use of Vehicles,” European Journal of Operational Research, Vol. 202, No. 3, pp. 756-763.2010.
23.Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM[M]。Society for Industrial and Applied Mathematics philadephia.2002
24.Solomon, M M and J Desrosiers , Time Window Constrained Routing and Scheduling Problem, Transportation Science 22, pp.1-13.1988.
25.Solomon, M.M. Vehicle routing and scheduling with time windows constraints: models and algorithms. Operation Research 35:2, pp.254-265, 1987.
26.Sexton, T., Choi, Y., Pickup and delivery of partial loads with soft time windows. American Journal of Mathematical and Management 6, pp.369–398.1986.
27.Suresh Nanda Kumar1, Ramasamy Panneerselvam2,” A Survey on the Vehicle Routing Problem and Its Variants.” Intelligent Information Management, 4, pp.66-74.2012.
28.Taillard E, Badeau P, Gendreau M, Guertin F, Potvin JY,A tabu search heuristic for the vehicle routing problem with soft time windows. Transport Sci 31:pp.170–186,1997.

29.Tagmouti M., Gendreau, M, and Potvin ,J. “Arc routing problems with time-dependent service costs,” Eur. J. Oper. Res., vol. 181, no. 1,pp. 30–39, 2007
30.Qureshi ,A.G. , Taniguchi,E. , Yamada, T. An exact solution approach for vehicle routing and scheduling problems with soft time windows. Transportation Research Part E 45, pp.960–977,2009.
31.Qureshi, A. G., Taniguchi, E., and Yamada, T., (2009). Column Generation -based Hauristics for Vehicle Routing Problem with soft time windows. Jurnal of the Eastern Asia society for Trasportation Studies, Vol.8.

指導教授

葉英傑

審核日期

2014-7-28

推文