The vehicle platooning problem: Computational complexity and heuristics
The vehicle platooning problem: Computational complexity and heuristics
复制标题
DOI：
10.1016/j.trc.2015.08.019
复制
发表时间：
2015-11-01
影响因子：
8.3
通讯作者：
Larson, Jeffrey
中科院分区：
文献类型：
--
作者：
Larsson, Erik;Sennton, Gustav;Larson, Jeffrey
我们创建了一个用于对在道路网络中行驶的卡车进行建模的数学框架，并定义了一个称为编队行驶问题的路径规划问题。我们证明了即使用于表示道路网络的图是平面的，这个问题也是NP难的。我们针对不考虑截止时间的编队行驶问题实例（我们称之为无限制编队行驶问题）提出了整数线性规划公式。这些公式使我们能够为大规模的实际例子计算编队行驶问题的燃料最优解。所解决的问题比文献中先前精确解决的问题大几个数量级。我们提出了几种启发式方法，并将它们的性能与德国高速公路网络上的最优解进行比较。所提出的启发式方法在大多数所考虑的问题实例中都能找到最优或接近最优的解，特别是当应用最终的局部搜索时。假设编队行驶可使燃料减少10%，我们发现道路网络中仅有10辆卡车编队行驶时可节省1 - 2%的燃料；节省的百分比随着卡车数量的增加而增加。如果所有卡车从同一点出发，仅200辆卡车就能获得高达9%的节省。（C）2015爱思唯尔有限公司。保留所有权利。
We create a mathematical framework for modeling trucks traveling in road networks, and we define a routing problem called the platooning problem. We prove that this problem is NP-hard, even when the graph used to represent the road network is planar. We present integer linear programming formulations for instances of the platooning problem where deadlines are discarded, which we call the unlimited platooning problem. These allow us to calculate fuel-optimal solutions to the platooning problem for large-scale, real-world examples. The problems solved are orders of magnitude larger than problems previously solved exactly in the literature. We present several heuristics and compare their performance with the optimal solutions on the German Autobahn road network. The proposed heuristics find optimal or near-optimal solutions in most of the problem instances considered, especially when a final local search is applied. Assuming a fuel reduction factor of 10% from platooning, we find fuel savings from platooning of 1-2% for as few as 10 trucks in the road network; the percentage of savings increases with the number of trucks. If all trucks start at the same point, savings of up to 9% are obtained for only 200 trucks. (C) 2015 Elsevier Ltd. All rights reserved.