The growing interest in electric transport solutions, mainly due to technological advances and environmental benefits, introduces new challenges. These include the need to adapt traditional route planning tools to accommodate the unique characteristics of electric vehicles. In the problem studied here, a fleet of electric trucks is tasked with delivering service to various customers, each with specific time windows for delivery. This problem is known as the Electric Vehicle Routing Problem with Time Windows (EVRPTW) and can be solved to optimality using a branch-and-price algorithm. A key component of this method is column generation, which involves the iterative construction of efficient single-vehicle routes in a pricing problem known as the Elementary Shortest Path Problem with Resource Constraints (ESPPRC).

For column generation to converge, it is sufficient to find an improving, but not necessarily optimal, new route when solving the pricing problem. Therefore, in this thesis, we explore the possibility of improving the performance of the branch-and-price algorithm by solving the pricing problem heuristically. Primarily, we explore three different heuristics employed in previous research, where modifications of these methods are made to account for the specific structure of the problem studied. The performance of the heuristics is evaluated using benchmark instances for the EVRPTW. The results show that significant acceleration is achieved by solving the pricing problem heuristically and that combining the different heuristics generally yields additional performance gains.

Teknikutveckling och miljömässiga fördelar ligger bakom ett växande intresse av elektriska lösningar inom transportindustrin. Detta medför bland annat ett behov av att anpassa traditionella ruttplaneringsverktyg för att ta elfordonens unika egenskaper i beaktning. Problemet som studeras här är inom forskningen känt som ett Electric Vehicle Routing Problem with Time Windows (EVRPTW) och innefattar en ellastbilsflotta som står inför uppgiften att leverera varor till ett antal kunder, där varje kund har ett specifikt tidsfönster för leveransen. För att lösa problemet till optimalitet används en branch-and-price-algoritm, vars grundbult utgörs av kolumngenerering bestående av iterativ framtagning av effektiva enfordonsrutter i ett subproblem känt som ett Elementary Shortest Path Problem with Resource Constraints (ESPPRC).

För att nå konvergens i kolumngenereringsprocessen räcker det att hitta en förbättrande, men inte nödvändigtvis optimal, ny väg när man löser subproblemet. Mot bakgrund av denna observation utforskas i det här examensarbetet möjligheten att förbättra branch-and-price-algoritmens prestanda genom att lösa subproblemet heuristiskt. Främst utforskas tre i tidigare forskning föreslagna heuristiker, där modifikationer av dessa metoder görs med hänsyn till den föreliggande problemspecifika strukturen. Prestandan för heuristikerna utvärderas genom testning på benchmark-instanser. Resultaten visar på att det finns stora vinster att hämta genom att lösa subproblemet heuristiskt, och att prestandan förbättras ytterligare när heuristikerna kombineras.