進階搜尋


 
系統識別號 U0026-2408201700253900
論文名稱(中文) 建構考量服務品質與生態效益之多目標撥召問題模型
論文名稱(英文) A Multi-objective Model for Dial-a-Ride Problem with Service Quality and Eco-efficiency
校院名稱 成功大學
系所名稱(中) 交通管理科學系
系所名稱(英) Department of Transportation & Communication Management Science
學年度 105
學期 2
出版年 106
研究生(中文) 鄭冠淳
研究生(英文) Guan-Chun Zheng
學號 R56041114
學位類別 碩士
語文別 英文
論文頁數 149頁
口試委員 指導教授-胡大瀛
口試委員-魏健宏
口試委員-董啟崇
口試委員-許聿廷
中文關鍵字 撥召運輸問題  服務品質  生態效益  速率選擇  多目標方法 
英文關鍵字 Dial-a-Ride Problem (DARP)  Service quality  Eco-efficiency  Speed level  Multi-Objective Optimization (MOO) method 
學科別分類
中文摘要 現今對於DRAP的研究,大多只考慮最小化旅程成本,然而以DARP模型最常見的應用復康巴士為例,這種運輸型態本質在於服務老人、身體殘障等弱勢族群,且國內外大多經營此種運輸者皆為非營利組織。故本研究認為不應單只從經營者觀點去考量成本,擬加入消費者觀點及環保觀點,依序分別於目標式加入等待時間及燃料消耗成本,以提高服務品質、節省燃料消耗及汙染,建構一個多目標的DARP模型。
DARP是自著名的Vehicle Routing Problem(VRP)問題的演化而來,而不論是VRP或是DARP,自建立以來模型皆假設一單位距離為一固定時間,亦即沒有速率的概念,所有路段皆假設為維持在某固定速率下等速行駛。然而現實中並非如此,本研究試著提升模式模擬的精確度,加入速率選擇概念,讓每條路段上能有高、中、低三種速率等級可選擇。藉此,在駕駛成本面向,使路徑能有更多可行組合;在服務品質面向,在遇到較緊迫時窗路段能提高速率盡量降低等待時間;在環保節能面向,於時窗較寬鬆之路段能降低速率減少燃料消耗。
旅行時間、等待時間、燃料消耗是三個相互衝突的目標式,而速率在其中就扮演著像齒輪般的角色,使目標式之間可以有所連動、互相牽制並相互妥協,為減少等待時間會使速率提高,而燃料消耗會抑制速率,再綜合藉由總最小距離維持路徑選擇及車輛使用效率。本研究使用幾種常見之多目標方法搭配最新演算工具Gurobi Optimizer求出設定權重下的柏拉圖最佳解,並使用不同的多目標方法來求解、分析,繪製柏拉圖區間以及權重設定建議區間以作為後續研究參考討論。
英文摘要 The objective function of standard Dial-a-Ride Problem (DARP) is to minimize total travel cost. However, most of DARP applications are designed for disabled and elderly people to provide more convenient and friendly services. The main difference between DARP and other vehicle routing problems is due to the human perspective which should be accounted for. Thus, the profit or operational cost should not be the only consideration. In addition to travel cost, the objective functions considered in this study include service quality and eco-efficiency.
In order to make three conflicting objectives interacting with each other, the speed level constraints were added to the model. We defined a set of speed levels, and these constraints ensure that only one speed is selected for each arc. From the perspective of travel cost, there are more feasible path sets by selecting different speed levels. From the perspective of service quality, the model can reduce more waiting time by increasing the speed on the arcs with a tight time window. From the perspective of eco-efficiency, the model can reduce fuel consumption by reducing speed.
The proposed model are constructed, and solved by the software Gurobi Optimizer. Four instances based on real geographic network are generated to evaluate the effectiveness of the model. We present results on the overall performance of the multi-objective model and the Pareto fronts with WMN and ECM. The results indicate that the multi-objective model can avoid these disadvantages of single objective model, and improve the total performance.
論文目次 ABSTRACT I
摘要 II
TABLE OF CONTENTS III
LIST OF TABLES VII
LIST OF FIGURES IX
CHAPTER 1 INTORDUCTION 1
1.1 Research Background 1
1.2 Research Motivation 2
1.3 Research Objectives 4
1.4 Research Flowchart 5
1.5 Overview 7
CHAPTER 2 LITERATURE REVIEW 9
2.1 Dial-a-Ride Problems (DARP) 9
2.1.1 Demand Responsive Transit System (DRTS) 9
2.1.2 Vehicle Routing Problem (VRP) 14
2.1.3 Recent Studies of Dial-a-Ride Problem (DARP) 17
2.1.4 Formulation of Standard DARP Model 22
2.1.5 Desired Pickup Time (DPT) and Desired Delivery Time (DDT) 25
2.2 Eco-efficiency 27
2.2.1 Regression-Based Models 28
2.2.2 Power-Based Models 31
2.2.3 Pollution-Routing Problem 35
2.2.4 Summary 41
2.3 Service Quality 43
2.3.1 Service Quality for Dial-a-Ride Problems 43
2.3.2 Summary 47
2.4 Multi-Objective Optimization (MOO) Methods 48
2.4.1 Classification of Multi-Objective Optimization (MOO) Methods 49
2.4.2 The Weighting Method (WM) 51
2.4.3 The Weighting Method with Normalization (WMN) 52
2.4.4 The ε-Constraint Method (ECM) 53
CHAPTER 3 RESEARCH METHODOLOGY 57
3.1 Problem Statement and Research Assumptions 57
3.2 Research Framework 59
3.3 The Definitions of Notations 62
3.4 Single Objective Models 64
3.4.1 Travel Time Minimization (Model A) 64
3.4.2 Waiting Time Minimization (Model B) 66
3.4.3 Fuel Consumption Minimization (Model C) 67
3.5 Multi-objective DARP Models 68
3.5.1 Multi-objective Model applying WMN (Model ABC-W) 68
3.5.2 Multi-objective Model applying ECM (Model ABC-E) 69
3.6 Mixed-Integer Programming (MIP) 71
3.7 Summary 72
CHAPTER 4 NUMERICAL EXPERIMENTS FOR THE SINGLE OBJECTIVE MODEL 73
4.1 Experimental Design and Setup 73
4.1.1 Experimental Network 73
4.1.2 Experiment Design 74
4.1.3 Experimental Setup 75
4.1.4 Experimental Process 77
4.2 Introduction of Test Instances 79
4.2.1 Small Instance with 10 Requests (S-1) 79
4.2.2 Small Instance with 10 Requests (S-2) 80
4.2.3 Medium Instance with 15 Requests (M) 81
4.2.4 Large Instance with 20 Requests (L) 82
4.3 Results of Single Objective Models 83
4.3.1 Results of Travel Time Minimization (Model A) 89
4.3.2 Results of Waiting Time Minimization (Model B) 90
4.3.3 Results of Fuel Consumption Minimization (Model C) 91
4.4 Summary 92
CHAPTER 5 NUMERICAL EXPERIMENTS FOR THE MULTI-OBJECTIVE MODEL 93
5.1 Results of Multi-objective Models Applying WMN 93
5.1.1 The Utopia and Nadir point 94
5.1.2 Equal Weights 95
5.1.3 Different Combinations of Weights 100
5.1.4 The Solutions and Plot for WMN 102
5.2 Results of Multi-objective Models Applying ECM 107
5.2.1 The Payoff Table and Epsilon Value 107
5.2.2 The Solutions and Plot for ECM 110
5.3 Result Analysis of Multi-objective Models 117
5.3.1 Effective Interval of Weighting Coefficients 118
5.3.2 S-1 Instance vs. S-2 Instance 122
5.3.3 WMN vs. ECM (Weakly Pareto Optimal) 125
5.3.4 WMN vs. ECM (Pareto Optimal) 126
5.3.5 Hypervolume Indicator 128
5.4 Summary 131
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 134
6.1 Conclusions 134
6.2 Suggestions 136
References 137
Appendix 143
參考文獻 1.Akcelik, R., & Besley, M. (2003). Operating cost, fuel consumption, and emission models in aaSIDRA and aaMOTION. In 25th Conference of Australian Institutes of Transport Research (CAITR 2003) (pp. 1-15).
2.Barth, M., Younglove, T., & Scora, G. (2005). Development of a heavy-duty diesel modal emissions and fuel consumption model. California Partners for Advanced Transit and Highways (PATH).
3.Barth, M., & Boriboonsomsin, K. (2009). Energy and emissions impacts of a freeway-based dynamic eco-driving system. Transportation Research Part D: Transport and Environment, 14(6), 400-410.
4.Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
5.Braekers, K., Caris, A., & Janssens, G. K. (2014). Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B: Methodological, 67, 166-186.
6.Braekers, K., & Kovacs, A. A. (2016). A multi-period dial-a-ride problem with driver consistency. Transportation Research Part B: Methodological, 94, 355-377. ISO 690
7.Chankong, V., & Haimes, Y. Y. (1983). Multiobjective decision making: theory and methodology. Elsevier.
8.Cohon, J. L. (2010). Multiobjective programming and planning. Academic, New York.
9.Cordeau, J. F., & Laporte, G. (2003). The dial-a-ride problem (DARP): Variants, modeling issues and algorithms. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2), 89-101.
10.Cordeau, J. F., & Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1), 29-46.
11.Coslovich, L., Pesenti, R., & Ukovich, W. (2006). A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem. European Journal of Operational Research, 175(3), 1605-1615.
12.Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
13.Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223(2), 346-359.
14.Demir, E., Bektaş, T., & Laporte, G. (2014). A review of recent research on green road freight transportation. European Journal of Operational Research, 237(3), 775-793.
15.Demir, E., Bektaş, T., & Laporte, G. (2014). The bi-objective pollution-routing problem. European Journal of Operational Research, 232(3), 464-478.
16.Denson, C. R. (2000). Public sector transportation for people with disabilities: A satisfaction survey. Journal of Rehabilitation, 66(3), 29.
17.Diwekar, U. (2008). Introduction to applied optimization (Vol. 22). Springer Science & Business Media.
18.Ehrgott, M., & Ryan, D. M. (2002). Constructing robust crew schedules with bicriteria optimization. Journal of Multicriteria Decision Analysis, 11(3), 139.
19.Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4), 1472-1483.
20.Engels, D., Hemelrijck, K. V., & Ayland, N. (2000). A basic system architecture and technical solutions for DRT. System for Advanced Management of Public Transport.
21.Falcocchio, J. (1979). A Methodology for Evaluating the Effectiveness of Transportation Improvements for the Elderly and Handicapped (No. TR-78/503 Final Rpt.).
22.Franceschetti, A., Honhon, D., Van Woensel, T., Bektaş, T., & Laporte, G. (2013). The time-dependent pollution-routing problem. Transportation Research Part B: Methodological, 56, 265-293.
23.Gass, S., & Saaty, T. (1955). The computational algorithm for the parametric objective function. Naval research logistics quarterly, 2(1‐2), 39-45.
24.Grodzevich, O., & Romanko, O. (2006). Normalization and other topics in multi-objective optimization. In Proceedings of the Fields MITACS Industrial Problems Workshop, Toronto, Canada.
25.Haimes, Y. Y., Ladson, L. S., & Wismer, D. A. (1971). Bicriterion formulation of problems of integrated system identification and system optimization. IEEE Transactions on Systems Man and Cybernetics, (3), 296.
26. Hickman, J., Hassel, D., Joumard, R., Samaras, Z., & Sorenson, S. (1999). MEET-Methodology for calculating transport emissions and energy consumption. European Commission, DG VII. Technical report.
27.Jaw, J. J., Odoni, A. R., Psaraftis, H. N., & Wilson, N. H. (1986). A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B: Methodological, 20(3), 243-257.
28.Jørgensen, R. M., & Madsen, O. B. (2004). Dial-a-ride (Doctoral dissertation, Technical University of Denmark Tekniske Universitet, Department of TransportInstitut for Transport).
29.Knörr, W., Seum, S., Schmied, M., Kutzner, F., & Anthes, R. (2011). Ecological transport information tool for worldwide transports. Methodology and data update. Heidelberg: IFEU Heidelberg, Oko-Institut.
30.Knutsson, S. (1999). Valuing rider quality attributes in the Swedish special transport services. Kungliska Tekniska Högskolan.
31.Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2014). The fleet size and mix pollution-routing problem. Transportation Research Part B: Methodological, 70, 239-254.
32.Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.
33.Laumanns, M., Thiele, L., & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research, 169(3), 932-942.
34.Liu, M., Luo, Z., & Lim, A. (2015). A branch-and-cut algorithm for a realistic dial-a-ride problem. Transportation Research Part B: Methodological, 81, 267-288.
35.Lois, A., & Ziliaskopoulos, A. (2017). Online algorithm for dynamic dial a ride problem and its metrics. Transportation Research Procedia, 24, 377-384.
36.Mavrotas, G. (2009). Effective implementation of the ε-constraint method in multi-objective mathematical programming problems. Applied mathematics and computation, 213(2), 455-465.
37.Miettinen, K. (1999). Nonlinear multiobjective optimization. Springer Science & Business Media.
38.Pagano, A. M., & McKnight, C. E. (1983). Economies of scale in the taxicab industry: some empirical evidence from the unite states. Journal of Transport Economics and Policy, 299-313.
39.Paquette, J., Cordeau, J. F., & Laporte, G. (2009). Quality of service in dial-a-ride operations. Computers & Industrial Engineering, 56(4), 1721-1734.
40.Paquette, J., Bellavance, F., Cordeau, J. F., & Laporte, G. (2012). Measuring quality of service in dial-a-ride operations: the case of a Canadian city. Transportation, 39(3), 539-564.
41.Paquette, J., Cordeau, J. F., Laporte, G., & Pascoal, M. M. (2013). Combining multicriteria analysis and tabu search for dial-a-ride problems. Transportation Research Part B: Methodological, 52, 1-16.
42.Parragh, S. N. (2011). Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem. Transportation Research Part C: Emerging Technologies, 19(5), 912-930.
43.Rangaiah, G. P. (2009). Multi-objective optimization: techniques and applications in chemical engineering (Vol. 1). World scientific.
44.Ropke, S., Cordeau, J. F., & Laporte, G. (2007). Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows. Networks, 49(4), 258-272.
45.Wilson, N.H.M., Sussman, J., Wong, H., & Higonnet, B. (1971). Scheduling Algorithms for dial-a-ride systems. Technical Report USL TR-70-13, Urban Systems Laboratory, Massachusetts Institute of Technology, Cambridge, MA.
46.Xiang, Z., Chu, C., & Chen, H. (2008). The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments. European Journal of Operational Research, 185(2), 534-551.
47.Zitzler, E., & Thiele, L. (1998, September). Multiobjective optimization using evolutionary algorithms—a comparative case study. In international conference on parallel problem solving from nature (pp. 292-301). Springer, Berlin, Heidelberg.
48.Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., & Da Fonseca, V. G. (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on evolutionary computation, 7(2), 117-132.
49.Actions on the integration of Rural Transport Services (ARTS) http://www.transport-research.info/project/actions-integration-rural-transport-services
50.Dial-a-Ride https://tfl.gov.uk/modes/dial-a-ride/
51.Gurobi Optimizer http://www.gurobi.com/
52.The Regional Transportation District (RTD) http://www.rtd-denver.com/
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2017-08-30起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2017-08-30起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw