Optimal routing of electric vehicles

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Bartolini, Enrico
dc.contributor.author Andelmin, Juho
dc.date.accessioned 2014-08-29T06:55:14Z
dc.date.available 2014-08-29T06:55:14Z
dc.date.issued 2014-08-19
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/13893
dc.description.abstract In this thesis, a vehicle routing problem (VRP) variant tailored for plug-in battery electric vehicles (BEVs) is studied. The studied problem involves a fleet of identical BEVs located at a central depot, a set of customers that must be serviced within given time windows, and a set of charging stations where the vehicles can recharge their batteries. The objective is to design a set of vehicle routes, each starting and ending at the depot, so that each customer is serviced exactly once and the total energy cost of the vehicle routes is minimized. Since BEVs have limited battery capacity and low recharging rate, charging station visits and recharging times must be explicitly considered in the route planning, wherefore most VRP variants are not sufficient in modeling the studied problem. Optimal routing of electric vehicles is not much studied in the optimization literature. The two most relevant models are the Green Vehicle Routing Problem (G-VRP) by Erdogan & Miller-Hooks (2012) and the Electric VRP with Time Windows (E-VRPTW) by Schneider et al. (2013). The model considered in this thesis generalizes the E-VRPTW by also allowing the possibility of recharging a variable amount of energy at charging stations (variable recharging scheme) rather than performing a full recharge at every visit (fixed recharging scheme). This thesis introduces energy paths (e-paths) and proposes a new formulation of the studied problem based on non-dominated e-paths between every customer pair. The new formulation reduces the number of decision variables in the model and eliminates the need of imposing an artificial upper bound on the number of stops to a charging station, as is commonly done in previous models to keep their size acceptable. Some new preprocessing steps and valid inequalities are also presented to strengthen the LP-relaxation of the proposed formulation. Computational tests indicate that the new formulation provides considerable improvements over the standard formulation. Moreover, it is shown that significant reductions in the routing cost can be obtained in real-world routing problems by adopting the variable recharging scheme over the fixed one. en
dc.description.abstract Tässä työssä tutkitaan ajoneuvon reititysongelman (Vehicle Routing Problem, VRP) variaatiota, joka on räätälöity ladattavia sähköautoja varten. Tutkittu ongelma käsittää laivueen identtisiä sähköautoja, jotka sijaitsevat keskusvarikolla; joukon asiakkaita, joiden luona tulee vierailla annettujen aikaikkunoiden määräämissä rajoissa; sekä joukon latausasemia, joissa autot voivat käydä lataamassa akkunsa. Ongelman tavoitteena on suunnitella joukko ajoreittejä, alkaen varikolta ja päättyen varikolle, siten, että jokainen asiakas on palveltu tasan kerran ja ajoreittien yhteenlaskettu energiakustannus on pienin mahdollinen. Koska sähköautojen toimintasäde on lyhyt ja akun lataaminen kestää suhteellisen kauan, tulee sekä latausasemakäynnit että lataukseen kuluva aika ottaa erityisesti huomioon reitin suunnittelussa, minkä vuoksi useimmat ajoneuvon reititysongelman variaatiot eivät ole riittäviä mallintamaan tutkittua ongelmaa. Sähköautojen optimaalista reititystä ei ole tutkittu paljon alan kirjallisuudessa. Kaksi keskeisintä mallia ovat Green VRP (G-VRP) (Erdogan & Miller-Hooks, 2012) ja Electric VRP with Time Windows (E-VRPTW) (Schneider et al., 2013). Tässä työssä tutkittu malli on yleistys E-VRPTW -mallista, joka mahdollistaa lisäksi mielivaltaisen energiamäärän lataamisen latausasemilla toisin kuin alkuperäisessä mallissa, jossa sähköautojen akut ladataan täyteen jokaisella käynnillä. Tässä työssä esitetään energiapolku (e-path) ja kehitetään uusi formulaatio tutkitulle ongelmalle perustuen ei-dominoituihin energiapolkuihin asiakasparien välillä. Uusi formulaatio vähentää päätösmuuttujien lukumäärää mallissa ja poistaa tarpeen asettaa mielivaltaisen ylärajan latausasemakäyntien lukumäärälle, kuten on tavallisesti tehty aikaisemmissa malleissa pitääkseen niiden koot kohtuullisina. Työssä esitetään myös uusia esikäsittelyjä sekä valideja epäyhtälöitä. Laskennalliset testit osoittavat, että työssä kehitetty uusi formulaatio on huomattavasti tehokkaampi kuin alkuperäinen vastaava. Lisäksi mallintamalla ladattu energiamäärä muuttujana, toisin kuin suorittamalla täysi lataus jokaisella latausasemakäynnillä, voidaan kuljetuskustannuksia vähentää merkittävästi. fi
dc.format.extent 89 + 8
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Optimal routing of electric vehicles en
dc.title Sähköautojen optimaalinen reititys fi
dc.type G2 Pro gradu, diplomityö en
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword vehicle routing problem en
dc.subject.keyword VRP en
dc.subject.keyword electric vehicle routing en
dc.subject.keyword electric vehicle en
dc.subject.keyword plug-in battery electric vehicle en
dc.subject.keyword BEV en
dc.subject.keyword e-path en
dc.subject.keyword electric vehicle routing problem with time windows en
dc.subject.keyword E-VRPTW en
dc.subject.keyword ajoneuvon reititysongelma fi
dc.subject.keyword ajoneuvon reititystehtävä fi
dc.subject.keyword kauppamatkustajan ongelma fi
dc.subject.keyword sähköauton reititysongelma fi
dc.subject.keyword sähköauto fi
dc.subject.keyword energiapolku fi
dc.identifier.urn URN:NBN:fi:aalto-201408292544
dc.programme.major Systeemi- ja operaatiotutkimus fi
dc.programme.mcode F3008 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Bartolini, Enrico
dc.programme Teknillisen fysiikan ja matematiikan koulutusohjelma fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account