The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization problem concerned with determining cost-efficient routes for a fleet of vehicles serving a set of customers under operational constraints. In recent years, the electrification of transportation has led to the emergence of the Electric Vehicle Routing Problem (EVRP), where routing decisions must account for battery charging requirements and energy-related constraints. These additional considerations significantly increase the complexity of the problem.

This thesis studies exact solution approaches for the EVRP based on branchandprice algorithms, the state-of-the-art methodology for solving large-scale vehicle routing problems to optimality. Branch-and-price combines branch-and-bound with column generation, where the master problem is solved using linear programming relaxation and new columns (routes) are generated dynamically by solving a pricing problem. For the EVRP, the pricing problem takes the form of an elementary shortest path problem with resource constraints, which is typically solved using labeling algorithms.

The thesis consists of three contributions that address different components of the branch-and-price framework. The first and third contributions focus on efficient pricing to speed up the overall algorithm. In the first contribution, bounding techniques tailored to structural properties of the EVRP are introduced, enabling early elimination of non-promising labels and significantly accelerating the labeling procedure. The third contribution instead considers heuristic pricing. A subgraphbased approach is proposed in which the pricing problem is solved on carefully selected subgraphs constructed using a machine learning procedure. This procedure generates subgraphs likely to contain high-quality routes, thereby reducing computational effort while maintaining solution quality.

The second contribution addresses the master problem and proposes a primal heuristic designed to obtain high-quality integer solutions early in the branch-andprice search. The method constructs routes that are compatible from an integrality perspective, enabling rapid identification of feasible solutions even when proving optimality is computationally demanding.

Overall, the proposed methods improve the computational performance of branch-and-price algorithms for the EVRP and contribute to making exact largescale electric vehicle routing more practically tractable.

Varje dag sker stora mängder godstransporter – från paket du beställt på nätet,till maten i din mataffär och komponenter som levereras till fabriker. För att dessa transporter ska ske effektivt krävs noggrann planering. Att bestämma hur fordon ska köra för att utföra en uppsättning uppdrag på bästa sätt kallas ruttplaneringsproblemet,ett problem som har studerats i över 50 år.

Förenklat handlar ruttplaneringsproblemet om att, givet en fordonsflotta och en mängd leveranser, planera hur fordonen ska köra så att alla uppdrag utförs till så låg kostnad som möjligt. Trots att problemet är lätt att beskriva är det matematiskt mycket svårt att lösa, särskilt eftersom det finns många praktiska begränsningar att ta hänsyn till.

En stark trend inom transportsektorn är övergången till elektrifierade fordon. Denna utveckling är viktig för att minska transporternas klimatpåverkan, men den förändrar också förutsättningarna för hur transporter planeras. Till skillnad från traditionella fordon, där tankning ofta kan ske snabbt och infrastrukturenär väl etablerad, kräver elfordon återkommande och mer tidskrävande stopp för laddning. Detta gör ruttplaneringen mer komplex: man behöver inte bara planera hur fordonen ska köra, utan också när och var laddning ska ske.

I denna avhandling studerar vi ruttplaneringsproblemet för elfordon, med fokus på att utveckla effektivare algoritmer för att lösa problemet. Den metod vi arbetar med kallas kolumngenerering, en teknik som används för att hantera mycket stora optimeringsproblem.

Idén bakom kolumngerering är att istället för att försöka lösa hela problemet på en gång, så delar man upp det i två delar: ett huvudproblem och ett eller flera delproblem. Huvudproblemet väljer vilka rutter som ska användas, medan delproblemen söker efter nya, bättre rutter som kan förbättra lösningen. Genom att växelvis lösa dessa två problemdelar kan man steg för steg närma sig en optimal eller nära optimal lösning.

Avhandlingen består av tre arbeten som tillsammans bidrar med förbättringar i båda dessa delar. I det första och tredje arbetet fokuserar vi på att lösa delproblemen mer effektivt, genom att utveckla metoder som snabbare hittar lovande rutter. I det andra arbetet studerar vi huvudproblemet och utvecklar metoder för att snabbt hitta rutter som fungerar väl tillsammans, vilket gör det möjligt att tidigt få fram lösningar av hög kvalitet.

Sammantaget bidrar resultaten till att göra avancerad ruttplanering för framtida elfordon mer praktiskt användbar. Effektivare planering innebär lägre kostnader,bättre resursutnyttjande och kan på sikt bidra till en mer hållbar transportsektor.