Change search
ReferencesLink to record
Permanent link

Direct link
The vehicle platooning problem: Computational complexity and heuristics
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.
2015 (English)In: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 60, 258-277 p.Article in journal (Refereed) PublishedText
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 60, 258-277 p.
Keyword [en]
Vehicle platooning, Computational complexity, Vehicle routing
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-179611DOI: 10.1016/j.trc.2015.08.019ISI: 000365372900016ScopusID: 2-s2.0-84942324774OAI: oai:DiVA.org:kth-179611DiVA: diva2:893058
Funder
Swedish Research CouncilSwedish Foundation for Strategic Research
Note

QC 20160112

Available from: 2016-01-12 Created: 2015-12-17 Last updated: 2016-01-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Sennton, Gustav
By organisation
Automatic Control
In the same journal
Transportation Research Part C: Emerging Technologies
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link