Traditionally, route planning in the transportation sector has only focused on minimizing the total distance driven when transporting goods or people. This is often done using software tools since planning the optimal route is a complex task that is hard to solve by hand. While driving the shortest distance possible is an effort towards lowering fuel costs, which is one of the largest operating costs for truck transportation companies, it is not necessarily the most fuel efficient route. Recently, research has emerged regarding fuel minimizing route planning in order to perform transport operations at the lowest fuel cost possible. One factor contributing to fuel consumption is vehicle speed, since high speed means high wind resistance. Fuel can therefore be conserved by driving at lower speeds. Though lower speeds means longer travelling time, meaning that if the route is disrupted, causing a delay, there is an increased risk that all tasks cannot be performed during the started working day. The purpose of this thesis is to determine how to plan fuel efficient routes in a transportation system prone to disruptions. It was conducted at Scania to further understand how their truck customers can increase profitability in their businesses by planning fuel efficient routes. The truck transportation business is under heavy pressure with low margins. It is therefore valuable to plan fuel efficient routes. The outcome of this thesis is two linear programming models for route planning that take truck capacity, customer demand and time windows for delivery into account. The first model can be used during planning to find a fuel efficient route in order to deliver to all customers to the lowest fuel cost possible. The model gives a route with predetermined average speeds between the customers, as well as arrival time at each customer. When appropriate, the truck is proposed to drive at a slightly decreased speed, to lower wind resistance and thereby fuel consumption. By also taking load weight into account, the route can be planned such that a heavy part of the load is delivered early, reducing the weight carried for the rest of the route. The proposed model accomplishes on average 6.3 % lower fuel cost, compared to the most commonly used route planning model, where the shortest total driving distance is sought. If something would happen that disrupts the route, it might be impossible to deliver all customers before the day ends. To handle those situations, a second model is proposed. Once the transport is delayed, the model will revise the initial route and propose a new route based on a cost of delaying a delivery. The goal is then to deliver as much as possible to the lowest possible cost. The new route will still consist of predetermined average speeds and arrival times. The proposed model is a tool for handling the complex task of recalculating routes once a disruption occurs. In summary, the first model provides support to plan a route that potentially lowers the operational costs for truck transportation companies. If the planned route is disrupted, the second model will revise it and give a new route with new speeds and arrival times. If possible, the revised route will still result in making all deliveries, otherwise the model will postpone the smallest deliveries to the next day. Together, the two models serve as a valuable support for truck transport companies that want to increase their profitability by lowering their operational costs. / Traditionellt har ruttplanering inom transportsektorn endast fokuserat på att minimera den totala körsträckan vid transport av gods eller människor. Detta görs ofta med hjälp av mjukvaruverktyg, eftersom optimal ruttplanering är en komplex uppgift som är svår att lösa för hand. Att köra den kortaste totalsträckan är ett sätt att sänka bränslekostnaderna, vilket är en av de största driftskostnaderna för lastbilstransportföretag, men det är inte nödvändigtvis den mest bränsleeffektiva rutten. Den senaste tiden har allt mer forskning bedrivits inom bränsleminimering för att kunna utföra transportuppdrag till lägsta möjliga bränslekostnad. En faktor som bidrar till bränsleförbrukningen är fordonets hastighet, eftersom hög hastighet innebär högt luftmotstånd. Bränsleförbrukningen kan därför minskas genom att köra i lägre hastigheter. Även om lägre hastigheter betyder längre körtid, vilket innebär att om rutten störs och lastbilen blir försenad, finns det en ökad risk att allt inte kan levereras under den påbörjade arbetsdagen. Syftet med detta arbete är att bestämma hur bränsleeffektiva rutter kan planeras i ett transportsystem benäget för störningar. Arbetet genomfördes på Scania för att förstå hur deras lastbilskunder kan öka lönsamheten i sina företag genom att planera bränsleeffektivare rutter. Lastbilstransportbranschen är under hög press med låga marginaler. Det är därför värdefullt för Scanias lastbilskunder att planera bränsleeffektiva rutter. Arbetet resulterade i två ruteplaneringsmodeller som tar hänsyn till lastkapacitet, kundbehov och tidsfönster för leverans. Den första modellen kan användas vid planering för att hitta en bränsleeffektiv rutt så att alla kunder levereras till lägsta möjliga bränslekostnad. Modellen ger en rutt med förbestämda genomsnittshastigheter mellan kunderna, såväl som ankomsttid hos varje kund. När det anses lämpligt föreslås något minskade hastigheter, för att minska luftmotståndet och därigenom bränsleförbrukningen. Genom att även ta hänsyn till vikt, kan rutten planeras så att en tung del av lasten levereras tidigt, vilket minskar den vikt som transporteras på resterande sträckor. Den föreslagna modellen uppnår i genomsnitt 6,3% lägre bränslekostnad jämfört med den vanligaste ruteplaneringsmodellen, som ger den kortaste totala körsträckan. Om något skulle hända som stör rutten kan det vara omöjligt att leverera alla kunder innan dagen slutar. För att hantera dessa situationer föreslås en andra modell. När transporten är försenad planerar modellen om den ursprungliga rutten och föreslår en ny rutt baserat på kostnaden för att skjuta upp en leverans. Målet är då att leverera så mycket som möjligt till lägsta möjliga kostnad. Den nya rutten består fortfarande av förbestämda medelhastigheter och ankomsttider. Genom att använda den föreslagna modellen tillhandahålls ett verktyg för att hantera den komplexa uppgiften att planera om rutten vid en störning. Sammanfattningsvis ger den första modellen stöd för att planera en rutt som potentiellt sänker driftskostnaderna för lastbilstransportföretag. Om den planerade rutten utsätts för en störning, föreslår den andra modellen en ny rutt med nya hastigheter och ankomsttider. Om det är möjligt innebär den nya rutten fortfarande att lastbilen levererar till alla kunder, om inte skjuts de minsta leveranserna upp till nästa dag. Tillsammans är de två modellerna ett värdefullt stöd för lastbilstransportföretag som vill öka lönsamheten genom att sänka sina driftskostnader.

A comprehensive study is presented of the Capacitated Multi DepotGreen Vehicle Routing Problem (CMDGVRP) applied to a heterogeneous fleet of electronic waste collecting vehicles with two objectives: to reduce the total fuel consumption of the vehicles (environmental sustainability) and to limit the continuous drive-time of the drivers (social sustainability). Research has been limited from this aspect, and in this study, the focus is on the practical application of pickup and delivery of electronic waste. The study also presents results for the online dynamic routing variant of this problem, where traffic congestion appears mid-route. A detailed analysis and parameter optimization has been done for Simulated Annealing, Genetic algorithm(GA), along with more advanced variants like Non-dominated Sorting GA (NSGA II), NSGA III, UNSGA III, and Indicator-Based Selection Evolutionary Algorithm (IBEA). Additionally, the Gini index is used to create a multi-objective model, which is novel in the context of CMDGVRP to the best of our knowledge. The use of the Gini index in the field of CMDGVRP shows excellent potential in balancing environmental, economic, and social sustainability. An extension of the CMDGVRP is introduced where vehicles can visit dropoff locations mid-route and then continue with a new route. This implementation is novel to our knowledge and is named Drop-and-continue. It is shown to increase the performance on large datasets. Results are presented from realistic simulation studies on a public dataset, with varying route lengths and vehicle fleet sizes, along with a real-world dataset from a waste collection company in Sweden. The results show that the optimal choice of algorithm depends on the dataset size and if there is a maximum budget of evaluations or computation time. Realistic problems are solved in a matter of a few seconds, given that they are initiated well. Simulated Annealing and Genetic algorithm prove to be very competitive in the case of large problems and limited computation time budget.