Sähköautojen optimaalinen reititys

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.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