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
A branch-and-cut method for the Vehicle Relocation Problem in the One-Way Car-Sharing
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The purpose of this thesis is to develop an algorithm which solves the Vehicle Relocation Problem in the One-Way Car-Sharing (VRLPOWCS) as fast as possible. The problem describes the task of relocating the cars to areas with the largest demand. The chauffeurs who relocate the cars are transported by shuttle buses. Each car is assigned an individual relocation utility. The objective is to find shuttle tours that maximise in a given time the relocation utility while balancing the distribution of the cars. The VRLPOWCS is formulated as a mixed integer linear program. Since this problem is NP-complete we choose the branch-and-cut method to solve it. Using additional cutting planes – which exploit the structure of the VRLPOWCS – we enhance this method. Tests on real data show that this extended algorithm can solve the VRLPOWCS faster.

Abstract [sv]

Syftet med detta examensarbete är att utveckla en algoritm som löser fördelningsproblemet av car-sharing bilar (VRLPOWCS) så snabbt som möjligt. Problemet beskriver uppgiften att flytta bilarna till områden där efterfrågan är störst. Bilarna flyttas av chaufförer som är transporterade med bussar. Varje bil ges ett flyttningsvärde. Målet är att hitta resor för bussarna så att inom ett visst tidsintervall det totala flyttningsvärdet är maximerat med hänsyn till en given fördelning. VRLPOWCS formuleras som ett linjärt heltalsprogrammeringsproblem. Eftersom problemet är NP-fullständigt, använder vi branch-and-cut metoden för att lösa det. Metoden utvidgar vi med cutting planes vilka utnyttjar VRLPOWCS strukturen. Tester med olika riktiga data visar att den utvidga algoritmen kan lösa VRLPOWCS snabbare.

Abstract [de]

Das Ziel dieser Arbeit ist die Entwicklung eines Algorithmus, der das Umparkproblem im Free-Floating Carsharing (VRLPOWCS) schnellstmöglich löst. Beim Umparkproblem werden Carsharing Fahrzeuge in Gebiete mit der höchsten Nachfrage umverteilt. Dabei werden die Autos von Fahrern umgeparkt, welche von Kleinbussen transportiert werden. Jedem Auto wird ein individueller Nutzenwert zugewiesen. Das Ziel des Umparkproblems ist das Finden von Bustouren, die in gegebener Zeit den Umparknutzen unter Beachtung einer gewissen Verteilung der Fahrzeuge in den Zielräumen maximieren. Das VRLPOWCS wird als ganzahlig-lineares Optimierungsproblem formuliert. Zur Lösung des VRLPOWCS wird ein Schnittebenenverfahren verwendet, da das Problem NP-vollständig ist. Das Verfahren wird mit Schnitten verbessert, die die Struktur des VRLPOWCS ausnutzen. Testläufe mit echten Daten zeigen, dass der erweiterte Algorithmus das VRLPOWCS schneller lösen kann.

Place, publisher, year, edition, pages
2015.
Series
TRITA-MAT-E, 2015:15
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-166720OAI: oai:DiVA.org:kth-166720DiVA: diva2:812003
External cooperation
TUM Technische Universität München
Subject / course
Optimization and Systems Theory
Educational program
Master of Science in Engineering -Engineering Physics
Supervisors
Examiners
Available from: 2015-05-14 Created: 2015-05-14 Last updated: 2015-05-14Bibliographically approved

Open Access in DiVA

fulltext(1890 kB)280 downloads
File information
File name FULLTEXT01.pdfFile size 1890 kBChecksum SHA-512
7652386a9ae9c580dea38178522647988c5d2038d1b91497d8d07be141131c91c78112b6d59a956e57d208203f2e555884e51e388ba4b3a6edd647228d4c65f9
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 280 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: 1238 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