No description available.

<p>Detta examensarbete har utförts på och i samarbete med ITN, Institutionen för Teknik och Naturvetenskap, vid Linköpings Universitet. Problemställningen härrör från tidigare projektsamarbete mellan Linköpings Universitet, Telia AB och Ericsson. Uppgiften består i att ta fram en optimeringsalgoritm som använder sig av ett nytt angreppssätt genom att försöka minska osäkerheten på indata.</p>

The modern theory of condition measures for convex optimization problems was initially developed for convex problems in conic format, and several aspects of the theory have now been extended to handle non-conic formats as well. In this theory, the (Renegar-) condition measure C(d) for a problem instance with data d=(A,b,c) has been shown to be connected to bounds on a wide variety of behavioral and computational characteristics of the problem instance, from sizes of optimal solutions to the complexity of algorithms. Herein we test the practical relevance of the condition measure theory, as applied to linear optimization problems that one might typically encounter in practice. Using the NETLIB suite of linear optimization problems as a test bed, we found that 71% of the NETLIB suite problem instances have infinite condition measure. In order to examine condition measures of the problems that are the actual input to a modern IPM solver, we also computed condition measures for the NETLIB suite problems after pre-preprocessing by CPLEX 7.1. Here we found that 19% of the post-processed problem instances in the NETLIB suite have infinite condition measure, and that log C(d) of the post-processed problems is fairly nicely distributed. Furthermore, there is a positive linear relationship between IPM iterations and log C(d) of the post-processed problem instances (significant at the 95% confidence level), and 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the post-processed problem instances. / Singapore-MIT Alliance (SMA)

Detta examensarbete har utförts på och i samarbete med ITN, Institutionen för Teknik och Naturvetenskap, vid Linköpings Universitet. Problemställningen härrör från tidigare projektsamarbete mellan Linköpings Universitet, Telia AB och Ericsson. Uppgiften består i att ta fram en optimeringsalgoritm som använder sig av ett nytt angreppssätt genom att försöka minska osäkerheten på indata.

No description available.

L'autopartage est un service de mobilité qui offre les mêmes avantages que les voitures particulières mais sansnotion de propriété. Les clients du système peuvent accéder aux véhicules sans ou avec réservation préalable. Laflotte de voitures est distribuée entre les stations et les clients peuvent prendre une voiture d'une station et ladéposer dans n'importe quelle autre station (one-way), chaque station disposant d'un nombre maximum de placesde stationnement. La demande pour la prise ou le retour des voitures dans chaque station est souvent asymétriqueentre les stations et varie au cours de la journée. Par conséquent, certaines stations accumulent des voitures etatteignent leur capacité maximale prévenant alors de nouvelles voitures de trouver une place de stationnement.Dans le même temps, des stations se vident et conduisent au rejet de la demande de retrait de clients. Notre travailporte sur l'optimisation des opérations de redéploiement de voitures afin de redistribuer efficacement les voitures surles stations suivant la demande qui varie en fonction du temps et de l'espace. Dans les systèmes d'autopartage àsens unique, le problème du redéploiement de voitures sur les stations est techniquement plus difficile que leproblème de la redistribution des vélos dans les systèmes de vélopartage. Dans ce dernier, on peut utiliser uncamion pour déplacer plusieurs vélos en même temps, alors que nous ne pouvons pas le faire dans le systèmeautopartage en raison de la taille des voitures et de la difficulté de chargement et de déchargement. Ces opérationsaugmentent le coût de fonctionnement du système d'autopartage sur l'opérateur. De ce fait, l'optimisation de cesopérations est essentielle afin de réduire leur coût. Dans cette thèse, nous développons un modèle deprogrammation linéaire en nombre entier pour ce problème. Ensuite, nous présentons trois politiques différentes deredéploiement de voitures que nous mettons en oeuvre dans des algorithmes de recherche gloutonne et nousmontrons que les opérations de redéploiement qui ne considèrent pas les futures demandes ne sont pas efficacesdans la réduction du nombre de demandes rejetées. Les solutions fournies par notre algorithme glouton sontperformantes en temps d'exécution (moins d'une seconde) et en qualité en comparaison avec les solutions fourniespar CPLEX. L'évaluation de la robustesse des deux approches présentées par l'ajout d'un bruit stochastique sur lesdonnées d'entrée montre qu'elles sont très dépendantes des données même avec l'adoption de valeur de seuil deredéploiement. En parallèle à ce travail algorithmique, l'analyse de variance (ANOVA) et des méthodes derégression multilinéaires ont été appliqués sur l'ensemble de données utilisées pour construire un modèle global afind'estimer le nombre de demandes rejetées. Enfin, nous avons développé et comparé deux algorithmesévolutionnaires multicritères pour prendre en compte l'indécision sur les objectifs de l'optimisation, NSGA-II et unalgorithme mémétique qui a montré une bonne performance pour résoudre ce problème. / To buy it. Users can have access to vehicles on the go with or without reservation. Each station has a maximumnumber of parking places. In one-way carsharing system, users can pick up a car from a station and drop it in anyother station. The number of available cars in each station will vary based on the departure and the arrival of cars oneach station at each time of the day. The demand for taking or returning cars in each station is often asymmetric andis fluctuating during the day. Therefore, some stations will accumulate cars and will reach their maximum capacitypreventing new arriving cars from finding a parking place, while other stations will become empty which lead to therejection of new users demand to take a car. Users expect that cars are always available in stations when they needit, and they expect to find a free parking place at the destination station when they want to return the rented car aswell. However, maintaining this level of service is not an easy task. For this sake, carsharing operators recruitemployees to relocate cars between the stations in order to satisfy the users' demands.Our work concerns the optimization of the car relocation operations in order to efficiently redistribute the cars overthe stations with regard to user demands, which are time and space dependent. In one-way carsharing systems, therelocation problem is technically more difficult than the relocation problem in bikesharing systems. In the latter, wecan use trucks to move several bikes at the same time, while we cannot do this in carsharing system because of thesize of cars and the difficulty of loading and unloading cars. These operations increase the cost of operating thecarsharing system.As a result, optimizing these operations is crucial in order to reduce the cost of the operator. In this thesis, we modelthis problem as an Integer Linear Programming model. Then we present three different car relocation policies thatwe implement in a greedy search algorithm. The comparison between the three policies shows that car relocationoperations that do not consider future demands are not effective in reducing the number of rejected demands.Results prove that solutions provided by our greedy algorithm when using a good policy, are competitive withCPLEX solutions. Furthermore, adding stochastic modification on the input data proves that the robustness of thetwo presented approaches to solve the relocation problem is highly dependent on the input demand even afteradding threshold values constraints. After that, the analysis of variance (ANOVA) and the multi-linear regressionmethods were applied on the used dataset in order to build a global model to estimate the number of rejecteddemands. Finally, we developed and compared two multi-objectives evolutionary algorithms to deal with thedecisional aspect of the car relocation problem using NSGA-II and memetic algorithms.

This paper presents a method that uses designed experiments and statistical models to extract information about how solver parameter settings perform for classes of mixed integer programs. The use of experimental design facilitates fitting a model that describes the response surface across all combinations of parameter settings, even those not explicitly tested, allowing identification of both desirable and poor settings. Identifying parameter settings that give the best expected performance for a specific class of instances and a specific solver can be used to more efficiently solve a large set of similar instances, or to ensure solvers are being compared at their best.

The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions. / text

The global community is facing great challenges as the energy system is transforming towards more reliable, effective, clean and renewable production. Small-scale and micro networks will play an important role in this changeover. Its advantages over today’s large conventional energy systems are their reliability and stability. In small-scale and micro networks, there is usually a variety of production units such as photovoltaic, wind power and micro-combined heat and power (micro-CHP). In this study, a small-scale network with an application of two different types of biogas fueled micro-CHPs is analyzed. The units are a micro gas engine (MGM) and a micro gas turbine (MGT). The application of micro-CHP is validated using a reference facility connected to a small-scale district heating network. The reference facility is a heat production plant at a horse race track outside Eskilstuna, Sweden consisting of an oil boiler, a pellet boiler and a heat storage tank. The potential in replacing the oil boiler with renewable micro-CHP is investigated. A simulation model is built in the software GAMS, using Mixed Integer Linear Programming (MILP) and the solver CPLEX, and the model is simulated using the heat demand from the horse race track. Results from the model validation shows that it is possible for both the MGM or the MGT together with the pellet boiler and the heat storage tank to fulfill the heat demand of the facility. The horse race track handles 4 000 m3 of horse manure annually, which is transported 124 km to a compost treatment facility. Therefore, a general analysis of biogas production from horse manure is conducted in order to investigate the possibilities for better horse manure treatment on site. A calculation for a biogas reactor with a capacity for the maximum biogas requirement of the micro-CHP is implemented. Horse manure is suggested to be co-digested with food waste, in order to provide a higher biogas exchange. The result of a Life Cycle Cost (LCC) analysis indicates difficulties in justifying an investment of a micro-CHP together with a biogas plant at current prices for heat and electricity. The results show that the payback period for the MGM is 7 years which is 2 years shorter than its lifetime and the MGT payback period is 12 year which also is it lifetime. The MGM shows the largest investment potential since it has an investment cost approximately 860 kSEK lower than for the MGT. The MGM also has a slightly higher electrical efficiency which results in higher revenues from produced electricity. The chosen MGM in this study is slightly smaller than the MGT, resulting in a lower biogas demand and a lower investment cost for a biogas plant. A sensitivity analysis shows great impact of the electricity price on the payback period for both types of micro-CHP. The results show that with an electricity price of 280 SEK/MWh, both the MGM and the MGT repays within their lifetime. But since MGM has a higher net present value at all electric prices, is the MGM considered to be a more economical feasible investment. What the authors think should be highlighted is also the environmental benefits of more efficient treatment of horse manure at the horse race track together with the possibility of local production of fuel resulting in reduced CO2 emissions by 47 tons/year.

Eftersom det råder bostadsbrist i Sverige finns det ett stort behov att producera bostäder på ett mer effektivt och prisvärt tillvägagångsätt. Det är Sveriges kommuner som ansvarar för planprocessen och de har en stor utmaning att hitta nya innovativa sätt att utveckla och effektivisera planprocessen. Linköpings kommun har vid planprocessen för bostadsområdet Berga äng valt att testa en samverkansform som kallas för byggherresamverkan. Det innebär att byggherrar får vara med och påverka planprocessen, förhoppningen är att genom det göra den mer effektiv och såldes kunna producera bostäder snabbare. För Berga äng har sex byggherrar vunnit en markanvisningstävling och är det är dessa som kommer vara en del av byggherresamverkan för området. Vid tävlingen tilldelades också byggherrarna hur många samt vilken bostadstyp – bostadsrätt eller hyresrätt – som de fick bygga. Inom byggbranschen finns det få standardiseringar då förutsättningarna för varje projekt förändras. Dessa förutsättningar gör att bygglogistiken har en stor påverkansgrad för hur snabbt bostäder kan produceras. För Berga äng har Linköpings kommun gett byggherrarna ansvaret att bestämma vilken byggherre som ska bygga på vilken tomt. Det innebär en förhandling mellan byggherrarna för att komma överens om en fördelning av tomterna. Det kan göras genom att godtyckligt förhandla fram en lösning men byggherrarna har eftersökt ett neutralt perspektiv vilket kan göras genom att använda sig av optimering. Syftet med denna studie är att genom en optimeringsmodell fördela ut tomterna mellan byggherrarna. Intervjuer genomfördes för att få en förståelse för byggherresamverkan och hur byggherrarna värderade tomterna. Utifrån dessa togs sedan en optimeringsmodell fram. För att optimeringsmodellen skulle kunna fördela ut tomterna mellan byggherrarna behövde alla tomter värderas till ett numeriskt värde. Olika värderingsmetoder undersöktes och där en värderingsmetod valdes vilket innebar att alla byggherrarna fick rangordna alla tomter. Dessa värderingar användes i optimeringsmodellen för att kunna fördela ut tomterna mellan byggherrarna. Tre resultat presenterades med olika fördelningar samt hur bra byggherrarna ansåg respektive resultat var. Studiens slutsats visar vad som var viktig för att kunna fördela tomterna i Berga äng men även vad som är viktigt på ett mer övergripande plan. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>