電動車路徑規劃問題

The Electric Vehicle Touring Problem

呂尚鴻

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2013年)

摘要

暖化問題日益嚴重使電動車產業快速發展。電動車的普及化能減緩溫室效應並更有效率地利用能源。本研究主要探討電動車路徑規劃問題，考量電動車需要充電的議題，針對電動車規劃出對其而言最佳的行駛路徑。目標為對一台給定電池電力容量上限的電動車，找出其在道路網路中從一點到另一點的最短時間路徑，稱為電動車最短路徑問題(the EV shortest path problem)，或找出其訪問數個指定地點所需要的最短時間路徑，稱為電動車巡迴路徑問題 (the EV touring problem)。而這些路徑都必須涵蓋電動車因電力需求而前往電池交換站更換電池的路徑與時間。本研究對電動車最短路徑問題和固定巡迴電動車巡迴路徑問題(the fixed tour EV touring problem)－電動車需依固定順序訪問所有指定地點－分別提出多項式時間的演算法。根據這些結果，我們進一步對電動車巡迴路徑問題(其為更複雜化的旅行者銷售問題)，提出可理論證明的常數倍數近似演算法。

關鍵字

近似演算法 ； 電動車 ； 最短路徑 ； 旅行者銷售問題 ； 車輛途程

並列摘要

The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we investigate some optimal EV route planning problems that take into consideration of possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest path problem and a fixed tour EV touring problem, where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem, which is a generalization of the traveling salesman problem.

並列關鍵字

approximation algorithms ； electric vehicle ； shortest paths ； traveling salesman problem ； vehicle routing

參考文獻

2. Bansal, N., A. Blum, S. Chawla, and A. Meyerson. “Approximation algorithms for deadline-TSP and vehicle routing with time-windows.” Proceedings of the 36th ACM Symposium on Theory of Computing (STOC’04), 166-174 (2004).

5. Campbell, A.M., M. Gendreau, and B.W. Thomas. “The orienteering problem with stochastic travel and service times.” Annals of Operations Research, 186(1), 61-81(2011).

6. Chang, M.-S. “Efficient algorithms for the domination problems on interval and circular-arc graphs.” SIAM J. Computing, 27(6), 1671-1694 (1998).

7. Christofides, N. “Worst-case analysis of a new heuristic for the traveling salesman problem.” Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University (1976).

9. Dijkstra, E.W. “A note on two problems in connexion with graphs.” Numerische Mathematik, 1(1)269-271 (1959).