Solving the Vehicle Routing Problem with Genetic ALgorithm and Simulated Annealing

This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.

The value of a saved tree : The lifecycle of CO2-emissions associated with the combination of printing paper and electricity production of wood in the U.S. and Sweden

The pulp- and paper production is a very energy intensive industry sector. Both Sweden and the U.S. are major pulpandpaper producers. This report examines the energy and the CO2-emission connected with the pulp- and paperindustry for the two countries from a lifecycle perspective.New technologies make it possible to increase the electricity production in the integrated pulp- andpaper mill through black liquor gasification and a combined cycle (BLGCC). That way, the mill canproduce excess electricity, which can be sold and replace electricity produced in power plants. In thisprocess the by-products that are formed at the pulp-making process is used as fuel to produce electricity.In pulp- and paper mills today the technology for generating energy from the by-product in aTomlinson boiler is not as efficient as it could be compared to the BLGCC technology. Scenarios havebeen designed to investigate the results from using the BLGCC technique using a life cycle analysis.Two scenarios are being represented by a 1994 mill in the U.S. and a 1994 mill in Sweden.The scenariosare based on the average energy intensity of pulp- and paper mills as operating in 1994 in the U.S.and Sweden respectively. The two other scenarios are constituted by a »reference mill« in the U.S. andSweden using state-of-the-art technology. We investigate the impact of varying recycling rates and totalenergy use and CO2-emissions from the production of printing and writing paper. To economize withthe wood and that way save trees, we can use the trees that are replaced by recycling in a biomassgasification combined cycle (BIGCC) to produce electricity in a power station. This produces extra electricitywith a lower CO2 intensity than electricity generated by, for example, coal-fired power plants.The lifecycle analysis in this thesis also includes the use of waste treatment in the paper lifecycle. Both Sweden and theU.S. are countries that recycle paper. Still there is a lot of paper waste, this paper is a part of the countries municipalsolid waste (MSW). A lot of the MSW is landfilled, but parts of it are incinerated to extract electricity. The thesis hasdesigned special scenarios for the use of MSW in the lifecycle analysis.This report is studying and comparing two different countries and two different efficiencies on theBLGCC in four different scenarios. This gives a wide survey and points to essential parameters to specificallyreflect on, when making assumptions in a lifecycle analysis. The report shows that there arethree key parameters that have to be carefully considered when making a lifecycle analysis of wood inan energy and CO2-emission perspective in the pulp- and paper mill in the U.S. and in Sweden. First,there is the energy efficiency in the pulp- and paper mill, then the efficiency of the BLGCC and last theCO2 intensity of the electricity displaced by BIGCC or BLGCC generatedelectricity. It also show that with the current technology that we havetoday, it is possible to produce CO2 free paper with a waste paper amountup to 30%. The thesis discusses the system boundaries and the assumptions.Further and more detailed research, including amongst others thesystem boundaries and forestry, is recommended for more specificanswers.

The Optimal trigger speed of vehicle activated signs

The thesis aims to elaborate on the optimum trigger speed for Vehicle Activated Signs (VAS) and to study the effectiveness of VAS trigger speed on drivers’ behaviour. Vehicle activated signs (VAS) are speed warning signs that are activated by individual vehicle when the driver exceeds a speed threshold. The threshold, which triggers the VAS, is commonly based on a driver speed, and accordingly, is called a trigger speed. At present, the trigger speed activating the VAS is usually set to a constant value and does not consider the fact that an optimal trigger speed might exist. The optimal trigger speed significantly impacts driver behaviour. In order to be able to fulfil the aims of this thesis, systematic vehicle speed data were collected from field experiments that utilized Doppler radar. Further calibration methods for the radar used in the experiment have been developed and evaluated to provide accurate data for the experiment. The calibration method was bidirectional; consisting of data cleaning and data reconstruction. The data cleaning calibration had a superior performance than the calibration based on the reconstructed data. To study the effectiveness of trigger speed on driver behaviour, the collected data were analysed by both descriptive and inferential statistics. Both descriptive and inferential statistics showed that the change in trigger speed had an effect on vehicle mean speed and on vehicle standard deviation of the mean speed. When the trigger speed was set near the speed limit, the standard deviation was high. Therefore, the choice of trigger speed cannot be based solely on the speed limit at the proposed VAS location. The optimal trigger speeds for VAS were not considered in previous studies. As well, the relationship between the trigger value and its consequences under different conditions were not clearly stated. The finding from this thesis is that the optimal trigger speed should be primarily based on lowering the standard deviation rather than lowering the mean speed of vehicles. Furthermore, the optimal trigger speed should be set near the 85th percentile speed, with the goal of lowering the standard deviation.

Out-of-town shopping and its induced CO2-emissions

Planning policies in several European countries have aimed at hindering the expansion of out-of-town shopping centers. One argument for this is concern for the increase in transport and a resulting increase in environmental externalities such as CO2-emissions. This concern is weakly founded in science as few studies have attempted to measure CO2-emissions of shopping trips as a function of the location of the shopping centers. In this paper we conduct a counter-factual analysis comparing downtown, edge-of-town and out-of-town shopping. In this comparison we use GPS to track 250 consumers over a time-span of two months in a Swedish region. The GPS-data enters the Oguchi’s formula to obtain shopping trip-specific CO2-emissions. We find that consumers’ out-of-town shopping would generate an excess of 60 per cent CO2-emissions whereas downtown and edge-of-town shopping centers are comparable.

Trips and their CO2 emissions induced by a shopping center

Most previous studies have focused on entire trips in a geographic region, while a few of them addressed trips induced by a city landmark. Therefore paper explores trips and their CO2 emissions induced by a shopping center from a time-space perspective and their usage in relocation planning. This is conducted by the means of a case study in the city of Borlänge in mid-Sweden where trips to the city’s largest shopping mall in its center are examined. We use GPS tracking data of car trips that end and start at the shopping center. Thereafter, (1) we analyze the traffic emission patterns from a time-space perspective where temporal patterns reveal an hourly-based traffic emission dynamics and where spatial patterns uncover a heterogeneous distribution of traffic emissions in spatial areas and individual street segments. Further, (2) this study reports that most of the observed trips follow an optimal route in terms of CO2 emissions. In this respect, (3) we evaluate how well placed the current shopping center is through a comparison with two competing locations. We conclude that the two suggested locations, which are close to the current shopping center, do not show a significant improvement in term of CO2 emissions.

Optimal retail location and CO2 emissions

In this paper, the p-median model is used to find the location of retail stores that minimizes CO2 emissions from consumer travel. The optimal location is then compared with the existing retail location,and the excess CO2 emissions compared with the optimal solution is calculated. The results show that by using the environmentally optimal location, CO2 emissions from consumer travel could be reduced by approximately 25percent. 

The effects of taxing truck distance on CO2 emissions from transports in retailing

To finance transportation infrastructure and to address social and environmental negative externalities of road transports, several countries have recently introduced or consider a distance based tax on trucks. In the competitive retail market such tax can be expected to lower the demand and thereby reduce CO2 emissions of road transports. However, as we show in this paper, such tax might also slow down the transition towards e-tailing. Considering that previous research indicates that a consumer switching from brick-and-mortar shopping to e-tailing reduces her CO2 emissions substantially, the direction and magnitude of the environmental net effect of the tax is unclear. In this paper, we assess the net effect in a Swedish regional retail market where the tax not yet is in place. We predict the net effect on CO2 emissions to be positive, but off-set by about 50% because of a slower transition to e-tailing.

Annual CO-emissions of combined pellet and solar heating systems

Emissions are an important aspect of a pellet heating system. High carbon monoxide emissions are often caused by unnecessary cycling of the burner when the burner is operated below the lowest combustion power. Combining pellet heating systems with a solar heating system can significantly reduce cycling of the pellet heater and avoid the inefficient summer operation of the pellet heater. The aim of this paper was to study CO-emissions of the different types of systems and to compare the yearly CO-emissions obtained from simulations with the yearly CO-emissions calculated based on the values that are obtained by the standard test methods. The results showed that the yearly CO-emissions obtained from the simulations are significant higher than the yearly CO-emissions calculated based on the standard test methods. It is also shown that for the studied systems the average emissions under these realistic annual conditions were greater than the limit values of two Eco-labels. Furthermore it could be seen that is possible to almost halve the CO-emission if the pellet heater is combined with a solar heating system.

CO2 Emissions, GDP and trade : a panel cointegration approach

This paper examines the relationships among per capita CO2 emissions, per capita GDP and international trade based on panel data sets spanning the period 1960-2008: one for 150 countries and the others for sub-samples comprising OECD and Non-OECD economies. We apply panel unit root and cointegration tests, and estimate a panel error correction model. The results from the error correction model suggest that there are long-term relationships between the variables for the whole sample and for Non-OECD countries. Finally, Granger causality tests show that there is bi-directional short-term causality between per capita GDP and international trade for the whole sample and between per capita GDP and CO2 emissions for OECD countries

Measuring CO2 emissions induced by online and brick-and-mortar retailing

We develop a method for empirically measuring the difference in carbon footprint between traditional and online retailing (“e-tailing”) from entry point to a geographical area to consumer residence. The method only requires data on the locations of brick-and-mortar stores, online delivery points, and residences of the region’s population, and on the goods transportation networks in the studied region. Such data are readily available in most countries, so the method is not country or region specific. The method has been evaluated using data from the Dalecarlia region in Sweden, and is shown to be robust to all assumptions made. In our empirical example, the results indicate that the average distance from consumer residence to a brick-and-mortar retailer is 48.54 km in the studied region, while the average distance to an online delivery point is 6.7 km. The results also indicate that e-tailing increases the average distance traveled from the regional entry point to the delivery point from 47.15 km for a brick-and-mortar store to 122.75 km for the online delivery points. However, as professional carriers transport the products in bulk to stores or online delivery points, which is more efficient than consumers’ transporting the products to their residences, the results indicate that consumers switching from traditional to e-tailing on average reduce their CO2 footprints by 84% when buying standard consumer electronics products. 

Measuring CO2 emissions induced by online and brick-and-mortar retailing

We develop a method for empirically measuring the difference in carbon footprint between traditional and online retailing (“e-tailing”) from entry point to a geographical area to consumer residence. The method only requires data on the locations of brick-and-mortar stores, online delivery points, and residences of the region’s population, and on the goods transportation networks in the studied region. Such data are readily available in most countries, so the method is not country or region specific. The method has been evaluated using data from the Dalecarlia region in Sweden, and is shown to be robust to all assumptions made. In our empirical example, the results indicate that the average distance from consumer residence to a brick-and-mortar retailer is 48.54 km in the studied region, while the average distance to an online delivery point is 6.7 km. The results also indicate that e-tailing increases the average distance traveled from the regional entry point to the delivery point from 47.15 km for a brick-and-mortar store to 122.75 km for the online delivery points. However, as professional carriers transport the products in bulk to stores or online delivery points, which is more efficient than consumers’ transporting the products to their residences, the results indicate that consumers switching from traditional to e-tailing on average reduce their CO2 footprints by 84% when buying standard consumer electronics products. 

Emissions Characterisation of residential pellet boilers during start-up and stop periods

In this study, gaseous emissions and particles are measured during start-up and stop periods for an over-fed boiler and an under-fed boiler. Both gaseous and particulate matter emissions are continuously measured in the laboratory. The measurement of gaseous emissions includes oxygen (O2), carbon dioxide (CO2), carbon monoxide (CO), nitrogen oxide and (NO). The emissions rates are calculated from measured emissions concentrations and flue gas flow. The behaviours of the boilers during start-up and stop periods are analysed and the emissions are characterised in terms of CO, NO, TOC and particles (PM2.5 mass and number). The duration of the characterised periods vary between two boilers due to the difference in type of ignition and combustion control. The under-fed boiler B produces higher emissions during start-up periods than the over-fed boiler A. More hydrocarbon and particles are emitted by the under-fed boiler during stop periods. Accumulated mass of CO and TOC during start-up and stop periods contribute a major portion of the total mass emitted during whole operation. However, accumulated mass of NO and PM during start-up and stop periods are not significant as the duration of emission peak is relatively short.

EMISSIONS CHARACTERISTICS OF A RESIDENTIAL PELLET BOILER AND A STOVE

Gaseous and particulate emissions from a residential pellet boiler and a stove are measured at a realistic 6-day operation sequence and during steady state operation. The aim is to characterize the emissions during each phase in order to identify when the major part of the emissions occur to enable actions for emission reduction where the savings can be highest. The characterized emissions comprised carbon monoxide (CO), nitrogen oxide (NO), total organic carbon (TOC) and particulate matter (PM 2.5). In this study, emissions were characterised by mass concentration and emissions during start-up and stop phases were also presented in accumulated mass. The influence of start-up and stop phases on the emissions, average emission factors for the boiler and stove were analysed using the measured data from a six-days test. The share of start-up and stop emissions are significant for CO and TOC contributing 95% and 89% respectively at the 20kW boiler and 82% and 89% respectively at the 12 kW stove. NO and particles emissions are shown to dominate during stationary operation.

Speed prediction for triggering vehicle activated signs

Accurate speed prediction is a crucial step in the development of a dynamic vehcile activated sign (VAS). A previous study showed that the optimal trigger speed of such signs will need to be pre-determined according to the nature of the site and to the traffic conditions. The objective of this paper is to find an accurate predictive model based on historical traffic speed data to derive the optimal trigger speed for such signs. Adaptive neuro fuzzy (ANFIS), classification and regression tree (CART) and random forest (RF) were developed to predict one step ahead speed during all times of the day. The developed models were evaluated and compared to the results obtained from artificial neural network (ANN), multiple linear regression (MLR) and naïve prediction using traffic speed data collected at four sites located in Sweden. The data were aggregated into two periods, a short term period (5-min) and a long term period (1-hour). The results of this study showed that using RF is a promising method for predicting mean speed in the two proposed periods.. It is concluded that in terms of performance and computational complexity, a simplistic input features to the predicitive model gave a marked increase in the response time of the model whilse still delivering a low prediction error.