标题: | 应用基因演算法以解决最小碳足迹之依时可选择路径之多车种车辆途程问题 A Genetic Algorithm for Minimizing Carbon Footprint for the Time-Dependent Heterogeneous Fleet Vehicle Routing Problem with Alternative Paths |
作者: | 曹佑菘 林春成 Lin, Chun-Cheng 工业工程与管理系所 |
关键字: | 碳足迹;车辆途程问题;多车种;多路径;基因演算法;Carbon Footprint;Vehicle Routing Problem;Heterogeneous Fleet;Alternative Paths;Genetic Algorithm |
公开日期: | 2012 |
摘要: | 本研究提出考虑最小碳足迹之车辆途程问题规划中同时考量车种选择和路径选择的问题,并称此问题为 “最小碳足迹之依时性可选择道路之多车种车辆途程问题”(Minimizing Carbon Footprint for the Time-Dependent Heterogeneous Fleet Vehicle Routing Problem with Alternative Paths, CTHVRPP),当中在目标式方面,为了因应目前日益严重的全球暖化与温室气体问题,因此不以过去常用的距离或时间为目标式,而改以最小碳足迹为目标。在比较了相关的依时性车辆途程问题之文献及总结 CTHVRPP 的问题特性后,我们提出此问题的一个整数规划的模型。如同过去车辆途程问题,CTHVRPP 亦为NP-Hard,因此我们进一步地发展出一套不同于以往的基因演算法的解决方法。藉由一套适当的编码与解码系统,本研究提出了序列型染色体与平行型染色体的编码方式,其中序列型染色体较利于演算法中交配、突变等动作进行,而平行型染色体则是将序列型染色体进行解码的动作,如此一来可简化单一染色体进行交配与突变时复杂的动作。另外由于碳足迹的大小取决于车辆行驶时消耗的能源多寡而定,因本研究改良 Bektaş 等人 (2011) 所提出之能源消耗模型,使其能够为本研究之多路径多车种问题所使用。在实验例题方面,我们以 Taillard (1999) 之测试例题为基础,额外编制影响碳足迹之成本变数,包含了不同路径下之车辆行驶速度、不同时区下之车辆行驶速度与不同车辆种类之空车重量与最大载重等变因,使其测试例题为本篇论文能够使用。最后将具多重路径供选择之例题与无多重路径供选择之例题测试结果进行不同成本如碳足迹、时间或距离最小化之目标式之结果进行分析,与无多重路径供选择之例题测试结果进行比较。结果表明路径选择这个实验因子对实验结果是有显着影响的,并且有路径选择之碳足迹实验结果优于无路径选择之碳足迹实验结果。在本篇论文中,提出基因演算法运算出优化的车辆排程,根据实验结果表明,所提出的车辆排程结果在以最小碳足迹为目标的情况下具有较佳的实验结果。 This study proposes a vehicle routing problem for minimizing carbon footprint by selecting the appropriate vehicles and routes. It is referred to as the “Minimizing Carbon Footprint for the Time-Dependent Heterogeneous Fleet Vehicle Routing Problem with Alternative Paths, CTHVRPP.” The objective of this problem is to minimize carbon footprint rather than distance or time. Thus, the resulting solution can help reduce greenhouse gas emissions and global warming. Since the vehicle routing problem is itself an NP-Hard problem, it can be inferred that CTHVRPP is also an NP-Hard problem. So we developed an enhanced genetic algorithm to resolve this problem. In the process of devising an appropriate coding and decoding system, this study developed a sequential chromosome coding method and a parallel chromosome decoding method. The sequential chromosome encoding method is best suited for crossover and mutation encoding operations, while the parallel chromosome decoding method is typically used in decoding sequentially encoded chromosomes. It is known that carbon footprint size is dependent on the vehicle energy consumption, thus this study improved the energy consumption model Bektaş et al. (2011) proposed, making this study possible. In our test scenario, we applied a test benchmark developed by Taillard (1999), which required the identification of cost variables that affect carbon footprint, including: vehicle speed, vehicle traveling on different paths during different time periods of the day, and the speed of each vehicle type when carrying an empty load and maximum load. The test results were then analyzed by applying various objectives such as carbon footprint minimization, time minimization, and distance minimization. These results were compared with results from scenarios without alternative routes available for selection. The results show that the alternative path in this experiment factor is has a significant impact on the experimental results. In this paper, the genetic algorithms optimization of vehicle scheduling, according to the experimental results, the proposed vehicle scheduling results with the experimental results better in minimum carbon footprint as the target case. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT070053349 http://hdl.handle.net/11536/72510 |
显示于类别: | Thesis |