Heuristic optimization of the p-median problem and population re-distribution

This thesis contributes to the heuristic optimization of the p-median problem and Swedish population redistribution.   The p-median model is the most representative model in the location analysis. When facilities are located to a population geographically distributed in Q demand points, the p-median model systematically considers all the demand points such that each demand point will have an effect on the decision of the location. However, a series of questions arise. How do we measure the distances? Does the number of facilities to be located have a strong impact on the result? What scale of the network is suitable? How good is our solution? We have scrutinized a lot of issues like those. The reason why we are interested in those questions is that there are a lot of uncertainties in the solutions. We cannot guarantee our solution is good enough for making decisions. The technique of heuristic optimization is formulated in the thesis.   Swedish population redistribution is examined by a spatio-temporal covariance model. A descriptive analysis is not always enough to describe the moving effects from the neighbouring population. A correlation or a covariance analysis is more explicit to show the tendencies. Similarly, the optimization technique of the parameter estimation is required and is executed in the frame of statistical modeling. 

On statistical bounds of heuristic solutions to location problems

Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region. 

A stopping rule while searching for optimal solution of facility-location

Solutions to combinatorial optimization, such as p-median problems of locating facilities, frequently rely on heuristics to minimize the objective function. The minimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. However, pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small branch of the literature suggests using statistical principles to estimate the minimum and use the estimate for either stopping or evaluating the quality of the solution. In this paper we use test-problems taken from Baesley's OR-library and apply Simulated Annealing on these p-median problems. We do this for the purpose of comparing suggested methods of minimum estimation and, eventually, provide a recommendation for practioners. An illustration ends the paper being a problem of locating some 70 distribution centers of the Swedish Post in a region.

Optimization heuristic solutions, how good can they be? : With empirical applications in location problems

Combinatorial optimization problems, are one of the most important types of problems in operational research. Heuristic and metaheuristics algorithms are widely applied to find a good solution. However, a common problem is that these algorithms do not guarantee that the solution will coincide with the optimum and, hence, many solutions to real world OR-problems are afflicted with an uncertainty about the quality of the solution. The main aim of this thesis is to investigate the usability of statistical bounds to evaluate the quality of heuristic solutions applied to large combinatorial problems. The contributions of this thesis are both methodological and empirical. From a methodological point of view, the usefulness of statistical bounds on p-median problems is thoroughly investigated. The statistical bounds have good performance in providing informative quality assessment under appropriate parameter settings. Also, they outperform the commonly used Lagrangian bounds. It is demonstrated that the statistical bounds are shown to be comparable with the deterministic bounds in quadratic assignment problems. As to empirical research, environment pollution has become a worldwide problem, and transportation can cause a great amount of pollution. A new method for calculating and comparing the CO2-emissions of online and brick-and-mortar retailing is proposed. It leads to the conclusion that online retailing has significantly lesser CO2-emissions. Another problem is that the Swedish regional division is under revision and the border effect to public service accessibility is concerned of both residents and politicians. After analysis, it is shown that borders hinder the optimal location of public services and consequently the highest achievable economic and social utility may not be attained.

Analysis of tapping test results in a test battery for advanced PD patients

Objective: To compare results from various tapping tests with diary responses in advanced PD. Background: A home environment test battery for assessing patient state in advanced PD, consisting of diary assessments and motor tests was constructed for a hand computer with touch screen and mobile communication. The diary questions: 1. walking, 2. time in off , on and dyskinetic states, 3. off at worst, 4. dyskinetic at worst, 5. cramps, and 6. satisfied with function, relate to the recent past. Question 7, self-assessment, allows seven steps from -3 ( very off ) to +3 ( very dyskinetic ) and relate to right now. Tapping tests outline: 8. Alternately tapping two fields (un-cued) with right hand 9. Same as 8 but using left hand 10. Tapping an active field (out of two) following a system-generated rhythm (increasing speed) with the dominant hand 11. Tapping an active field (out of four) that randomly changes location when tapped using the dominant hand Methods: 65 patients (currently on Duodopa, or candidates for this treatment) entered diary responses and performed tapping tests four times per day during one to six periods of seven days length. In total there were 224 test periods and 6039 test occasions. Speed for tapping test 10 was discardedand tests 8 and 9 were combined by taking means. Descriptive statistics were used to present the variation of the test variables in relation to self assessment (question 7). Pearson correlation coefficients between speed and accuracy (percent correct) in tapping tests and diary responses were calculated. Results: Mean compliance (percentage completed test occasions per test period) was 83% and the median was 93%. There were large differences in both mean tapping speed and accuracy between the different self-assessed states. Correlations between diary responses and tapping results were small (-0.2 to 0.3, negative values for off-time and dyskinetic-time that had opposite scale directions). Correlations between tapping results were all positive (0.1 to 0.6). Conclusions: The diary responses and tapping results provided different information. The low correlations can partly be explained by the fact that questions related to the past and by random variability, which could be reduced by taking means over test periods. Both tapping speed and accuracy reflect the motor function of the patient to a large extent.

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. 

How do different densities in a network affect the optimal location of service centers?

The p-median problem is often used to locate p service centers by minimizing their distances to a geographically distributed demand (n). The optimal locations are sensitive to geographical context such as road network and demand points especially when they are asymmetrically distributed in the plane. Most studies focus on evaluating performances of the p-median model when p and n vary. To our knowledge this is not a very well-studied problem when the road network is alternated especially when it is applied in a real world context. The aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the density in the road network is alternated. The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 service centers we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000. To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when nodes in the road network increase and p is low. When p is high the improvements are larger. The results also show that choice of the best network depends on p. The larger p the larger density of the network is needed. 

How does the use of different road networks effect the optimal location of facilities in rural areas?

The p-median problem is often used to locate P service facilities in a geographically distributed population. Important for the performance of such a model is the distance measure. Distance measure can vary if the accuracy of the road network varies. The rst aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the road network is alternated. It is hard to nd an exact optimal solution for p-median problems. Therefore, in this study two heuristic solutions are applied, simulating annealing and a classic heuristic. The secondary aim is to compare the optimal location solutions using dierent algorithms for large p-median problem. The investigation is conducted by the means of a case study in a rural region with an asymmetrically distributed population, Dalecarlia. The study shows that the use of more accurate road networks gives better solutions for optimal location, regardless what algorithm that is used and regardless how many service facilities that is optimized for. It is also shown that the simulated annealing algorithm not just is much faster than the classic heuristic used here, but also in most cases gives better location solutions.

To what extent are CO2 emissions from intra-urban shopping trips by cars affected by drivers’ travel behaviour and store location?

Transportation is seen as one of the major sources of CO2 pollutants nowadays. The impact of increased transport in retailing should not be underestimated. Most previous studies have focused on transportation and underlying trips, in general, while very few studies have addressed the specific affects that, for instance, intra-city shopping trips generate. Furthermore, most of the existing methods used to estimate emission are based on macro-data designed to generate national or regional inventory projections. There is a lack of studies using micro-data based methods that are able to distinguish between driver behaviour and the locational effects induced by shopping trips, which is an important precondition for energy efficient urban planning. The aim of this study is to implement a micro-data method to estimate and compare CO2 emission induced by intra-urban car travelling to a retail destination of durable goods (DG), and non-durable goods (NDG). We estimate the emissions from aspects of travel behaviour and store location. The study is conducted by means of a case study in the city of Borlänge, where GPS tracking data on intra-urban car travel is collected from 250 households. We find that a behavioural change during a trip towards a CO2 optimal travelling by car has the potential to decrease emission to 36% (DG), and to 25% (NDG) of the emissions induced by car-travelling shopping trips today. There is also a potential of reducing CO2 emissions induced by intra-urban shopping trips due to poor location by 54%, and if the consumer selected the closest of 8 existing stores, the CO2 emissions would be reduced by 37% of the current emission induced by NDG shopping trips.

The effects of Ikea and external shopping centers on regional trade and retail growth : A comparative analysis of Ikea’s establishment in Kalmar and Karlstad

This paper examines the effects of Ikea store establishment in Kalmar and Karlstad on the trade and retail inside the two cities, and as well on the trade and retail in the close neighboring municipalities and in further peripheral municipalities in both regions. After the establishment of Ikea store, Kalmar and Karlstad have experienced significant growth in trade and retail. The question, however, is how big this growth is in both cities? And how different locations on different distances from Ikea have been affected? What impact there was on different segments of the retail? How different business branches have been affected? How large the catchment area for the emerging new large-scale retail locations is? These questions, in addition to few others, are investigated in this paper. The thesis starts with an introduction chapter containing a background of the topic, problem description, the investigated questions, the purpose, and the outline of the paper. The next chapter includes the frame of reference which consists of literature review and theoretical framework about the external shopping centers and their impact on retail and regional trade development. It includes also information gathered from previous studies technical reports and other available sources about the subject. The third chapter includes description for the methods used to collect the primary and secondary data needed for the purpose of this study. Then the empirical framework which demonstrates the results of the conducted research followed by analysis and concluded in discussion and conclusion. Mixed methods are used as research strategy in this thesis, and the method to conduct the research is based on telephone interviews for the primary (qualitative) data, and documents and desk research for the secondary (quantitative) data. The gathered data is analyzed and designed in a way that allows the usage of comparative analysis technique to present the findings and draw conclusions. The results showed that new established Ikea retail store outside the city boundaries results with many effects on the city center and on the neighboring municipalities as well. The city center seems not to be affected negatively, but on the contrary positive effects were witnessed in both regions, these positive effects are linked to the increase inflow of customers from the external retail area which is known as spillover effect. III On the other hand, the neighboring towns and municipalities are more negatively affected especially with the trade of con-convenience goods as the consumers in these towns and municipalities start to go to the area of Ikea and the large external retail center to do their purchasing, the substitution effect is then said to be occurred. Moreover, the further far municipalities do not seem to be significantly affected by the establishment of Ikea. These effects whether positive or negative could be monitored by looking to few trade parameters such as the turnover, the sales index, and the consumers’ expenditure, these parameters can be very useful to measure the developments and changes in the trade and retail in a given place.