Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm
Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm
复制标题
DOI：
10.1016/j.trd.2017.04.016
复制
发表时间：
2017-07-01
影响因子：
7.6
通讯作者：
Soysal, Mehmet
中科院分区：
文献类型：
--
作者：
Cimen, Mustafa;Soysal, Mehmet
本文研究了一类具有随机车速和环境因素的时间依赖型容量限制车辆路径问题。这个问题被表述为一个马尔可夫决策过程。与传统方法不同的是，该模型在估算燃油消耗量和排放量时，考虑了车速的时间依赖性和随机性。时间依赖的能力约束车辆路径问题是已知的NP-难，即使是确定性的设置。不确定性的问题增加了复杂性，这使得经典的优化方法不可行。因此，我们提出了一个近似动态规划为基础的启发式作为决策辅助工具的问题。建议的马尔可夫决策模型和近似动态规划的启发式是灵活的，可以通过改变目标函数从成本最小化到排放量最小化，以获得更环保的解决方案。通过对几个实例的计算分析，显示了拟议的决策支持工具的附加值。计算分析表明，将车速随机性纳入决策支持模型有可能提高性能的旅行时间，排放量和旅行成本方面的路线。此外，所提出的启发式算法在相对较短的计算时间内提供了有希望的结果。(C)2017爱思唯尔有限公司版权所有
This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be NP-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, we propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times. (C) 2017 Elsevier Ltd. All rights reserved.