Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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) Published
Resource type
Text
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: 000365372900016Scopus ID: 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-11-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 41 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf