Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Robust Vehicle Routing in an Urban Setting
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2016 (Swedish)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Robust fordonsruttning i en urban miljö (Swedish)
Abstract [en]

In this thesis, the vehicle routing problem with stochastic, and time dependent, travel times is studied. The stochastic travel times are estimated from historical drive data. The variation of the drive times, as well as that of the variance, during the day was modeled.  

The purpose of the thesis was to propose a method of handling the congestion related traffic impediments in an urban setting. Since the majority of times of delivery in the empirical test cases studied correlate with the time period of high traffic load, an efficient and robust handling of such traffic scenarios is of high importance. 

It is shown that the stochastic models will shift the estimated arrivals to customers from the more volatile early and late extremes to more central regions of the time window.

Previously delivered routes were evaluated both with the standard algorithm and the proposed stochastic algorithm. The difference between the actual drive times and the calculated drive times were analyzed by studying the correlation of the drive times between each customer in the route. It was shown that the routes of the proposed stochastic method increased this correlation. The drive times between nodes where also perturbed with a Gamma distributed noise. The results from the stochastic algorithm showed higher resilience to this disturbance than did the deterministic models.

Abstract [sv]

I detta examensarbete har fordonsruttningsproblemet, VRP, med stokastiska och tidsberonds körtider behandlöats. De stokastiska körtiderna har estimerats från tidigare insamlad hasighetsdata. Modeller för körtidernas och variansernas förändring under dagen har tagits fram.  

Syftet med examensarbetet var att föreslå en metod för hur påverkan på körtider av förutsägbar trafikträngsel i en urban trafikmiljö kan hanteras. Eftersom huvuddelen av alla leveranser sammanfaller med de tider på dygnet då trafikbelastning är som högst, ar är en effektiv och robust metod för att hantera sådana störningar av stor vikt.

Det visas att den stokastiska modellen kommer att förflyttar ankomster från början och slutet av tidsfönstret till den mer okänsliga mittregionen.

Tidigare, utförda leveranser studerades både med den ursprungliga deterministiska modellen och här framtagna stokastiska modellen. Skillnaden mellan de två analyserades genom att studera korrelationen mellan körtiderna som de beräknats av de två modellerna och de upmätta tiderna som de loggats av leveransfordonen. Det visas att korrelationen mellan körtiderna mellan de stokastiska körtiderna och de verkliga körtiderna är högre än korrelationen mellan de deterministiska körtiderna och de verkliga.

Rutterna som föreslagits av den stokastiska modellen var också mer tlig mot störningar.

Place, publisher, year, edition, pages
2016.
Series
TRITA-MAT-E, 2016:14
Keyword [en]
Vehicle routing problem, Stochastic travel times, Time dependent rive times, Time Windows.
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-186248OAI: oai:DiVA.org:kth-186248DiVA: diva2:926544
External cooperation
Budbee AB
Subject / course
Systems Engineering
Educational program
Master of Science - Aerospace Engineering
Supervisors
Examiners
Available from: 2016-05-09 Created: 2016-05-08 Last updated: 2016-05-09Bibliographically approved

Open Access in DiVA

fulltext(13982 kB)162 downloads
File information
File name FULLTEXT01.pdfFile size 13982 kBChecksum SHA-512
56ade9b1d2c660ffc928a2f86ac18237c8e89c8d61126e9d384fe8fc6fc93cd3f0e7964fd29e97c8fe6592e0a76ae3889bfc856890ec6f5080672101fc4d8abf
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 162 downloads
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

urn-nbn

Altmetric score

urn-nbn
Total: 168 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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