基於演化計算演算法解決車輛共乘問題之研究

A Study of Evolutionary Computation Algorithms for Carpooling Problem

詹富閔(FU-MIN ZHAN)

指導教授 ： 謝富雄

朝陽科技大學/資訊學院/資訊工程系/碩士(2018年)

摘要

共乘是一種有效的運輸模式，可以顯著降低運輸成本。由於在解決共乘決策問題的過程中要滿足複雜的限制條件，使得乘客與駕駛員匹配的問題成為一個極有挑戰性的難題。本文的目標是提出一種模型與解決方案，該方法使用現有的地理資訊以及從司機與乘客所收集的資訊來計算與匹配共乘的司機/乘客。在本文中，我們制定了共乘問題的數學模式並提出了基於萬用啟發式的演算法。差分進化(DE)是被廣泛用於科學和工程領域的保留原樣進化演算法。DE 簡單的演化機制賦予它解決優化問題的強大能力。為了達成本論文的目標，我們首先將共乘優化問題描述為整數規劃問題。然後我們為它發展DE 演算法變形的解決方法。我們還進行了實驗來說明和比較所提出的DE 演算法的有效性。

關鍵字

共乘 ； 差分進化演算法 ； 啟發式

並列摘要

Carpooling is an effective transport model that can significantly reduce transportation costs. The problem to match passengers with drivers is a difficult problem due to complex constraints to be satisfied in the solution processes. The goals of this Thesis are to propose a model and a solution methodology that is seamlessly integrated with existing geographic information system to determine drivers/passengers for ride sharing. In this Thesis, we formulate a car pooling problem and propose a solution algorithm for it based on a meta-heuristic approach. Differential evolution (DE) is a competitive evolutionary algorithm widely utilized in the science and engineering fields. The simple and straightforward evolving mechanisms of DE endow it with the powerful capability to solve optimization problems. To achieve the goal, we first formulate the carpooling optimization problem as an integer programming problem. We then develop variants of DE algorithm for it. We also conduct experiments to illustrate and compare effectiveness of the proposed DE algorithms.

並列關鍵字

car pooling ； differential evolution ； meta-heuristic

參考文獻

參考文獻

[1] Mehdi Nourinejad and Matthew J. Roorda, “Agent based model for dynamic ridesharing,” Transportation Research Part C: Emerging Technologies, Volume 64, March 2016, Pages 117-132.

[2] Masabumi Furuhata, Maged Dessouky, Fernando Ordóñez, Marc-Etienne Brunet, Xiaoqing Wang and Sven Koenig, “Ridesharing: The state-of-the-art and future directions,” Transportation Research Part B : Methodological, Volume 57,1 November 2013, Pages 28–46.

[3] Niels Agatz, Alan Erera, Martin Savelsbergh and Xing Wang, “Optimization for dynamic ride-sharing: A review,” European Journal of Operational Research, Volume 223, Issue 2, December 2012, Pages 295–303.

[4] Maurizio Bruglieri, Diego Ciccarelli, Alberto Colornia and Alessandro Luè, “PoliUniPool: a carpooling system for universities,” Procedia Social and Behavioral Sciences, Volume 20, 2011, Pages 558–567.