Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3056611 bytes, checksum: e73001b52f3f37e092e742b4d599ce04 (MD5) Previous issue date: 2014-02-14 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / This dissertation deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bekta ¸s e Laporte (2011). The objective is to minimize operational and environmental costs while respecting route-load constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. Vehicle speeds are additional decision variables of the problem which complement routing decisions. They impact the total cost, the travel times between the locations, and thus the set of feasible routes. We propose a hybrid method that combines a local search-based metaheuristic with an exact approach and a recursive speed-optimization algorithm. Moreover, two other green VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The results obtained compare very favorably with those found in the literature, and many new improved solutions are reported. / Esta dissertação lida com o Pollution-Routing Problem (PRP), i.e. um Problema de Roteamento de Veículos (PRV) com considerações ambientais, recentemente introduzido na literatura por Bekta¸s e Laporte (2011). O objetivo consiste na minimização dos custos operacionais e ambientais, respeitando as restrições de carga dos veículos e janelas de tempo dos clientes. O custo é baseado no salário dos motoristas e no consumo de combustível, que depende de diversos fatores, como distância percorrida e carga transportada. As velocidades dos veículos são variáveis de decisão adicionais que complementam as decisões de roteamento. Tais velocidades interferem diretamente no custo total, nos tempos de viagem, bem como no conjunto de rotas viáveis. Uma abordagem híbrida que combina uma metaheurística baseada em busca local com uma abordagem exata e um algoritmo recursivo para otimizar as velocidades é proposta para solucionar o problema. Além do PRP, outras duas variantes do PRV com considerações ambientais são tratadas: o PRV considerando consumo de combustível e o PRV com minimização de energia. Os resultados obtidos se mostraram bastante favoráveis quando comparados com os melhores da literatura, e diversas soluções melhoradas são reportadas.

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.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

The dissertation thesis is focused on the optimization of control parameters of an EDM machine; the subject of optimization is cutting speed and surface topography. The first part of the thesis contains a research study on the technology of electrical discharge machining with the attention paid to the optimization methods use for control parameters of this process. The second part of the thesis is focused on real application of knowledge gained from studied sources. Here, a design of experiment aim at optimizing the parameters of the EDM machine is designed and carried on to maximize the cutting speed with the highest possible surface quallity. The result of the work is to build adequate regression models and find the optimal setting of machine control parameters.

Optimization of flight operations is a way to reduce the impact of aviation on the environment and make the use of airspace more effective. Reductions in fuel consumption and flight time are further desired by airlines to minimize operational costs. The flight planning tools of today optimize the vertical profile with the knowledge of wind conditions at different altitudes. Cost optimal speeds are however currently selected by the aircraft computer itself. Because this selection is performed locally and with limited data, e.g., weather, there is reason to believe speeds could be further optimized for an overall lower cost. This work presents a model constructed to optimize speeds through the implementation of modified cost indices along the cruise phase of a flight for minimized cost including fuel and time consumption. First, the effects of different parameters on the economical speed chosen by the aircraft are presented. A brute force approach is then used to establish optimal cost index selection when all possible paths are evaluated. From this, a speed optimizing dynamic programming model is constructed to find optimized cost index paths. Results of the model show reductions in flight costs, presented as either a fuel or a time reduction. Conclusions are derived from the test results to suggest improvements of the model and the next steps for aircraft flight speed optimization. / Optimering av flygverksamhet är ett sätt att minska påverkan av flygindustrin på miljön och effektivisera användandet av luftrummet. Minskningar av bränsleförbrukning och flygtid är vidare efterfrågat av flygbolag för minimering av flygverksamhetskostnader. Dagens planeringsverktyg optimerar den vertikala flygprofilen med information om vindförhållanden på olika altituder. Kostoptimala hastigheter väljs däremot av flygmaskinen själv i nuläget. I och med att dessa val utförs lokalt och med begränsad information, bland annat om väder, finns det anledning att ana att hastigheter kan optimeras ytterligare för att sänka helhetskostnader. Detta arbete presenterar en modell skapad för att finna optimerade hastigheter som implementeras med modifierade kostindex längs sträckflygningsfasen av en flygning för minimerad kostnad inkluderande bränsle- och tidkonsumption. Först presenteras effekten av olika parametrar på den ekonomiska hastigheten vald av flygdatorn. En brute force-metod används sedan för att fastställa den optimala kostindex banan då samtliga möjliga vägar utvärderas. Utifrån detta skapas en dynamisk programmeringsmodell för hastighetsoptimering för att finna en optimal kostindex bana. Resultat från modellen visar minskade flygkostnader i form av antingen bränsle- eller tidsbesparingar. Slutsatser dras utifrån testresultaten för att föreslå förbättringar av modellen och nästa steg för optimering av hastighet för flygplan.

Decreasing the fuel consumption and thus greenhouse gas emissions of vessels has emerged as a critical topic for both ship operators and policy makers in recent years. The speed of vessels has long been recognized to have highest impact on fuel consumption. The solution suggestions like "speed optimization" and "speed reduction" are ongoing discussion topics for International Maritime Organization. The aim of this study are to develop a speed optimization model using time-constrained genetic algorithms (GA). Subsequent to this, this paper also presents the application of machine learning (ML) regression methods in setting up a model with the aim of predicting the fuel consumption of vessels. Local outlier factor algorithm is used to eliminate outlier in prediction features. In boosting and tree-based regression prediction methods, the overfitting problem is observed after hyperparameter tuning. Early stopping technique is applied for overfitted models.In this study, speed is also found as the most important feature for fuel consumption prediction models. On the other hand, GA evaluation results showed that random modifications in default speed profile can increase GA performance and thus fuel savings more than constant speed limits during voyages. The results of GA also indicate that using high crossover rates and low mutations rates can increase fuel saving.Further research is recommended to include fuel and bunker prices to determine more accurate fuel efficiency.