Using Hierarchical Facility Location, Single Facility Approach, and GIS in Carsharing Services

Abstract

In the last few years, vehicle sharing has driven a gradual switch from ownership-based private mobility to service usage as a sustainable urban transport alternative. A significant number of cities have implemented mobility sharing programs. Shared transport reduces both traffic congestion, and the need for parking space, decreasing the number of vehicles on the road. The optimization of shared mobility service sites increases potential user access, reduces transportation costs, and augments demand for this transportation modality. Car sharing is a mobility concept where the usage of a vehicle fleet is shared among several people. This is a relatively new concept of transport, with short vehicle rental periods. It provides the convenience of private vehicles without additional charges. A key success factor is the location of sharing stations. The study presented here refers to a car sharing service to be operated by a carmaker in the city of São Paulo (Brazil). This article aims to identify and to select the best places to establish sharing stations within the company’s dealer and servicing network. A geographic information system (GIS) calculates spatial distribution of potential trip demand. Two models of hierarchical facility location are used to determine ideal station locations. It also suggests potential local partners to house car-sharing stations, such as hotels and private car parks. Voronoi diagrams support the location task. The recent rediscovery of Weber’s classic unique facility location problem has also been applied. The selection criterion was to maximize demand and hence operator profit, while minimizing obstacles like the distance to stations.

1. Introduction

The world’s urban population surpassed rural populations in 2007. The gap between urban and rural populations is increasing, as is as the total world population, intensifying problems such as traffic jams and environment deterioration. It also leads to non-planned patterns of suburban development that are difficult to properly serve with public transportation. These challenges could be handled with alternative means of transportation, like shared mobility [1].

Shared mobility consists of supplying mobility as needed, eliminating vehicle ownership. This transport strategy fosters multimodality, avoiding low utilization of transport resources, reducing parking space, traffic congestions, greenhouse gas emissions, and pollution in general [1,2,3,4,5,6,7,8].

In car sharing, clients make short-term car rentals, avoiding vehicle purchase and maintenance costs [1,2,3,4,7]. Since the client is also a driver, fares are less expensive than in a taxi or Uber [9].

There are two car sharing modalities: free-floating or station-based. In free-floating, the carsharing company sets an operating area where rentals can be started and finished. The client can finish the rental and park the vehicle anywhere within that perimeter [8]. In the station-based modality, the sharing company pre-defines stations where vehicles are picked up and delivered (rental start and finish). The station-based modality is divided into two modes: round-trip and one-way. A client returns the rented vehicle to the same station where she started, in a round trip. Or, she can leave the vehicle at a different station, in a one-way trip [1,6,9,10].

To be attractive to customers, station locations for both round-trip and one-way modes need to be properly planned. Thus, the company can improve accessibility to potential users, increasing demand. Amid the techniques applied to define suitable locations are the location-allocation models [11].

Hierarchical facility location is considered a network problem. The aim is to find optimal facility locations at each service level and to determine the closest service levels between location and demand facility. The problem of hierarchical location can be categorized on the basis of available budget, facility location at each service level, and customer assignment to each hierarchy level [12].

The Weber problem concerns finding a potential business among multiple sources of customers and businesses scattered in a geographical area. The selection of a given input source may vary according to the potential business location under study [13].

This article aims to identify the best carsharing station locations within the car manufacturer network (dealers and service workshops) in the city of São Paulo, Brazil. The objective is to demonstrate two location-allocation models applied to new carsharing station locations, using seven different types of location-allocation, and Voronoi diagrams combined with optimization algorithms.

A GIS method estimates spatial distribution of potential travel demand. Two hierarchical facility location models determine suitable locations for car sharing stations and potential partners. The Voronoi diagram, combined with optimization algorithms, were also applied in GIS. In this case, the Weiszfeld algorithm was applied. It is important to highlight the location-allocation methodology determines potential partners in existing locations, and the Weiszfeld algorithm presents an optimal location based on the same commercial establishment data, locating the best place to meet demand generated by these commercial establishments.

From the results of the two GIS applications, the objective of the article was achieved, as optimal locations among partnership candidates were identified. In some cases, the two models chose different establishments, but the proximity among them, belonging to the same districts, corroborates the results.

The next section reviews the literature on siting resources.

2. Literature Review

2.1. Carsharing and Optimal Places to Allocate Resources

Finding optimal places to allocate resources is a common problem in different knowledge areas [14]. Properly placing facilities and other business-related resources is important for objectives like reducing costs [15], improving accessibility [9], or raising profits [16].

However, the number of possible combinations for allocating resources in real problems usually increases exponentially with the problem’s input. Sometimes finding the best combination among all possibilities cannot be accomplished in a feasible amount of time [15,17]. Since this problem is NP-Complete [17], recent works use heuristics to get reasonable solutions [9,15].

Monteiro et al. [9] presented the heuristic simulated annealing method and a mixed-integer linear programming (MILP) model to identify satisfactory public transport pickup and drop-off locations. Although the methods yielded different solutions, they demonstrated the benefits of using heuristics whenever obtaining optimal solutions is difficult.

Lin et al. [15] proposed a swarm intelligence algorithm for facility-location allocation of reverse logistics of end-of-life vehicles network. The algorithm was applied in two real cases and compared solutions obtained from four metaheuristics. All four metaheuristics yielded reasonably good solutions for the problem.

Chen et al. [16] used an MILP model to optimize the location of one-way car sharing stations in the Xuhui District of Shanghai, China. The authors had to simplify the MILP model and to discretize the simulated time in steps. The feasibility and rationality of the model was verified with a case study of the EVCARD car sharing company.

Another common resource allocation method is the location-allocation model. It selects the best locations to settle key facilities and to define who will be served by which facility [18]. In general, location-allocation methods use heuristics both to minimize impedance of facility locations and to maximize coverage of demand points defined in a network [13]. There are other related models based on the location set covering problem, aiming to minimize the number of facilities and to fulfill demand, and the maximal covering location problem, which covers demand points within a closeness constraint [19]. Since the location-allocation models have general purposes, they can be applied to manifold decision-making tasks [20].

Larsen et al. [21] introduced a GIS grid-cell model to locate and choose cycling facilities in Montreal, Canada. They used data from origin–destination surveys, bicycle accident police records, and ambulance records. The grid-cell model proposed can also be used to locate other cycling facilities, such as bike parking and public bike stations.

Classical location-allocation models usually rely on the p-median problem (PMP). It is one of the most studied and used localization models for real-world problems. Given N facility candidate points and M demand search points with a given weight (for example, number of people living in the neighborhood), choose a solution P so that the sum of costs of distance from each point M to the nearest point P will be minimized [22]. This model locates opportunities to maximize search points, limiting the area of influence defined by the analyst. Thus, it assumes the interaction between facility location and demand decreases as the distance increases. In other words, as the distance to the potential supply point increases, the probability of being used decreases. The proper location of a facility will be closer to the greater density of demand points [23].

According to [14] location analysis, mathematical methods are sometimes viewed as too sophisticated for use in emerging countries, but the usefulness of those location methods in decision-making has been demonstrated.

Celsor and Millard-Ball [24] present a study using GIS to evaluate market potential for carsharing in thirteen U.S. cities. Data shows the relation between existing carsharing infrastructure and neighborhood characteristics. The study uses a 0.5-mile radius buffer in ArcGis software.

The chapter published by [25] introduces the technique of location-allocation modelling and illustrates its usage. It presents different forms of the model and how they can be operationalized in a GIS package such as ESRI’s software, ArcGIS. Two examples are provided—optimal location of stop-smoking clinics in Leeds, UK, and police stations in Kuwait.

Lage et al. [11] applied a similar methodology, with ArcGis location-allocation algorithms, using another section of the database used in this work, but in different scenarios (business centers instead of subway stations).

Efthymiou, Chaniotakis, and Antoniou [26] searched the most recent research papers on demographic, environmental, economic, and travel patterns affecting the adoption of vehicle-sharing systems.

The localization model adopted in this study was the PMP, which chooses the best location, from a set of candidate sites, based on their interaction with search sites. Given a set of facilities providing goods and services to a set of search points seeking them, the goal is to locate facilities that increase user demand. The selection criterion is demand maximization (and thus operator profitability), while minimizing hindrances such as distance to stations. The method suggests places to operate car sharing services, and indicates potential business partners such as hotels, private parking lots and others, to shelter car sharing stations, expanding the coverage area.

2.2. Hierarchical Facility Location Problems

Hierarchical facility location problems are classified according to four attributes [27]: flow pattern, service variety, spatial configuration, and objectives.

Flow patterns refer to the flow of goods or services between service levels in a network. The flow pattern is categorized in two classes, single flow and multi flow. In single flow, customers by-pass low levels to reach high levels. In multi flow, demand may be met at any level (low or high) and can also terminate at any level.

Service variety is another factor to be considered in the location of hierarchical facilities. Each system is classified as nested or non-nested according to the availability of services at each level of the hierarchy. In a nested hierarchy, services at each level are contained by specific and additional services at lower levels; different sets of services are provided at each service level.

In spatial configuration, N-level services in hierarchical facility location are classified as spatial coherent or non-coherent. In a coherent system, each requirement can only receive services from a single hierarchy. The service route is also assigned to a hierarchy, for example in carsharing. In non-coherent systems, it is possible for lower-level elements to be assigned to different higher-level elements.

The objectives of facility location targets are classified in coverage, median and fixed-change location models. The first two are object of this article.

If a facility is located within a certain coverage radius, a client will be attended by that facility, according to the coverage model. The objective is to minimize the number of installations needed to cover all clients. The advantage of this model is to be present at a site in the shortest possible time, and to designate each center to respond to an event or emergency based on density of each site, coverage radius and attention to service quality. Some studies using this methodology are [28,29,30].

Median models minimize the total distance weighted by demand (transport cost) between clients and facilities. In other words, the main objective is to locate new premises so that their distance from existing ones is equal. The advantages are to quantify the sum of the distances (costs), from graph theory, to predetermine the number of installations and to find the median points between public services (candidate points), including schools, hospitals, fire stations, ambulances, technical automotive audit stations, etc. [31,32,33].

2.3. Location-Allocation Problem Types

The location-allocation methodology is used in different ways to find the best location to solve a given problem. GIS software is used to solve this type of problem, because it can encompass different types of data and their spatial location, and the integration of these two features solves the problem in a practical and localized way.

Several GIS software has this location-allocation feature; for example the QGis (http://www.qgis.org) (accessed on 15 November 2021) software, which is a free operating system. It features the Location Lab QGIS Plugin where it also does some analysis for this purpose. In this article, ArcGis was used, because it provides many kinds of location-allocation algorithms and also has a user-friendly interface.

The ArcGIS PRO (license granted by ESRI because of the COVID-19 pandemic) location-allocation analysis provides seven types of problems to answer questions like those posed in the two examples above. From Esri [34], they are maximize attendance, maximize capacitated coverage, maximize coverage, maximize market share, minimize facilities, minimize impedance, and target market share.

2.4. Voronoi and Weber Problem

Most transport and logistics problems involve spatial relations, involving the division of territory (definition of traffic areas, for example), the location of facilities (metro stations, depots, goods distribution centers, trans-shipment points, etc.), transport networks, etc. Many problems are discretely formulated, but with advances in computing, continuous models have been increasingly used, mainly in the planning stages of new transportation and logistics systems [13,35].

Drezner and Hamacher [36] seek optimal locations to host diverse facilities to optimize an objective function, such as minimizing transportation costs, maximizing demand attracted by the service, and others. This type of problem is often geometric and combinatorial in nature. The technical literature presents many applications: location of subway stations, hospitals, schools, warehouses, distribution centers, etc.

The Voronoi diagram—also called Thiessen polygon or Delaunay tessellation—is employed in the areas of archaeology, biology, cartography, mineralogy, meteorology, physiology, statistics and, more recently, in urban and regional planning [37].

Voronoi diagrams are useful for spatial analysis and location optimization of various transportation and logistics problems. In this article, a problem of locating stations along a stretch of subway line is presented and discussed. The optimal location of subway stations and the allocation of demand to the various stations are two important aspects related to projects of this urban transport mode [35,38].

Alfred Weber is one of the precursors in solving localization problems, with the experiment of establishing the best production site between raw material suppliers and the consumer market.

However, Weber himself recognized the limitations of the method to solve the initially proposed problem [25]. Thus, the development of localization problems remained stagnant for almost fifty years, until, in the 1960s, several researchers brought new approaches to solving the problem proposed by Weber. Since then, new approaches to the location-allocation problem have been rapidly developed [25].

From Weber [39], a rolling plan defines the problem. It seeks the best location for a plant, minimizing transport costs of moving raw materials and components to the plant and finished product to retail centers. Distances are measured using Euclidean metrics.

3. Materials and Methods

The study area is the city of São Paulo, situated in the Southeast Region of Brazil (Figure 1). It is the country’s largest city, with 12.25 million inhabitants, and a demographic density of 7.4 inhabitants/km² over an area of 1521.101 km². The city of São Paulo accounts for 11% of the Brazilian Gross National Product (GNP) (194.9 billion dollars in 2015) and has a human development index (HDI) of 0.805 [40].

The car manufacturer provided its network (dealerships and service workshops) locations and the most appropriate spots to operate a car sharing system were defined, to maximize the demand and profit, and to minimize access distances to the stations.

Additionally, this study used public free databases, namely: commercial establishments (potential partners to operate the car sharing service) [41], land use map [41], road network [42], São Paulo City districts [42], and transport infrastructure [41,42,43]. These data were used to delimit the car sharing system coverage area and to build the location-allocation model.

Like the methodology presented in [11], this work contemplates three phases. Figure 2 illustrates the methodological steps.

The first phase is the elaboration of baseline data (the same used in [11]), identifying businesses that can shelter a car sharing station, like hotels, shopping malls, parking garages, and colleges/universities. Parking garages and hotels were identified according to the number of employees and only those with over ten employees were selected, assuming medium and large enterprises already have the minimum infrastructure to operate and to maintain a car sharing business.

In the second phase, the coverage model definition of walking time zone was applied, so the dealer is located within a certain radius of coverage and customers will be attended by that dealer. The establishments already filtered in phase 1 were selected in the walking time zone of 30 min. The walking time zone was defined for a potential customer (“car-renter”), walking for less than 30 min, at an average speed of 5 km/h, being able to reach a carmaker station. This model presents possible areas for the implementation of a new collection and deposit station.

Then, the seven types of location-allocation were applied using the ArcGIS PRO 2.5 [34] algorithm. The purpose was to maximize people’s access to the stations, and consequently, increase demand for this mobility option, indicating potential business partners in areas with greater distance from the carmaker stations and increasing the availability of stations for customers.

Continuing to the second phase, the Voronoi diagram was carried out for commercial establishments together with carmaker servicing. After this phase was completed, the Weiszfeld algorithm was applied only within the area selected by the model, the districts of Moema and Vila Mariana. More information about the algorithm can be seen in reference [44].

The third phase is the result of the two applications. The first is the search for potential partners; the other is the possible optimal location of a new carsharing station based on customers who visit these stores.

4. Results

4.1. Network Service Area

A network service area is a region including all accessible streets, i.e., streets within a specified impedance. Service areas help us to evaluate accessibility from the carmaker service station in different directions to identify the carmaker service station’s service area. The travel time zones are within 5, 10, 15, 30, and 45 min walking to the cars. Times were defined assuming walking time as impedance. For the present study, walking time was assumed to an average speed of 5 km/h.

For example, the five-minute service area for a station includes all streets that can be reached in five minutes from that carmaker station. These are usually generated as a polygon layer, superimposed on the network, indicating travel time ranges that had been built around the location of the carmaker service.

For each area, the walking time from the starting point of the carmaker service is broken down by color scheme. In the most distant areas, i.e., over half an hour walking, customers are unlikely to walk to use carsharing. So, from these two location polygons, another station is suggested for carsharing. These areas are shown in Figure 3.

4.2. Location-Allocation Model

To run the location-allocation model, two types of data are needed: (i) facility and (ii) demand. Facility is the car maker service network (vehicle dealerships and servicing workshops), which is the center of supply (or distribution) that must fully meet customer demands, whether subject to the upper limit in facility capacity or not. Transport costs are understood as distances between the points of origin and destination.

Carmakers were chosen because they will cover the carsharing in a comprehensive way, i.e., providing the cars, maintenance and servicing, and the operation of the business. It is important to emphasize that car makers have no physical space to store these cars for the carsharing application [9].

Demand data refer to businesses (potential partners to operate car sharing services) in the coverage area, within the reach of at least one facility that minimizes total distance between supply and demand and, simultaneously, allocate flows between facilities and customers.

Thus, the location-allocation model involves choosing the best location for one or more facilities within a set of possible locations to provide high customer service levels, to minimize operating costs, or to maximize profits. We want to achieve a solution, if possible optimal, that minimizes the total cost of facilities and journeys.

The location-allocation model chooses the best car dealers to settle a car sharing system and recommends potential partners from commercial businesses in the region (buffer zone) using the road network to calculate distances and travel times.

Table 1. Commercial establishments available in the study area (2015 to 2018).

Commercial Establishments	Quantity in the Study Area	Quantity Municipal
Hotels	186	755
Shopping malls	9	47
Parking garages	668	3972
Colleges	169	492
Road network	711 km	20,180 km

present each type of business available in the buffer zone.

Table 2. The result per type of location-allocation applied and the partnership for each type of business establishment.

Location-Allocation Problem Types	Hotels	Shopping Malls	Parking Garages	Colleges
Maximize Attendance	Hotel Stela LTDA	Shopping Paulista	C.E.C. Park	Centro Universitário Belas Artes de São Paulo
Maximize Capacitated Coverage	Red Green Hotel LTDA	Shopping Paulista	Rede Park	Universidade Federal de São Paulo
Maximize Coverage	Hotel Stela LTDA	Shopping Metro Santa Cruz	C.E.C. Park	Centro Universitário Belas Artes de São Paulo
Maximize Market Share	Hotel Stela LTDA	Shopping Metro Santa Cruz	C.E.C. Park	Centro Universitário Belas Artes de São Paulo
Minimize Facilities	Hotel Stela LTDA	Shopping Metro Santa Cruz	C.E.C. Park	Centro Universitário Belas Artes de São Paulo
Minimize Impedance	Hotel Stela LTDA	Shopping Metro Santa Cruz	C.E.C. Park	Centro Universitário Belas Artes de São Paulo
Target Market Share	Hotel Stela LTDA	Shopping Metro Santa Cruz	C.E.C. Park	Centro Universitário Belas Artes de São Paulo

presents the types of location-allocation in the following order: Maximize Attendance, Maximize Capacitated Coverage, Maximize Coverage, Maximize Market Share, Minimize Facilities, Minimize Impedance, and Target Market Share. The commercial units indicated by the location-allocation model as the best locations from a set of candidate sites with potential to shelter a car sharing station are presented.

4.3. Voronoi Diagram

Figure 4a,b details the Voronoi diagram for each type of resource (for example, carmaker service, hotels, shopping malls, colleges, and parking garages). Figure 4a shows the five layers overlapped and Figure 4b shows the Voronoi polygons correspond to each type of business establishment with a particular configuration for each type, depend on the number of each type of occurrence and individual location. Each face refers to a unique resource allocation, as the business establishment is located inside that face.

Two GIS principles were used for assignment. The first uses distances along a transport network, shown in Figure 3. The second uses Voronoi diagrams, i.e., Euclidean distances, shown in Figure 4a,b. To compare which model would be more appropriate, or also, as was the case in this paper, to present whether there is any difference in locality, the result of these two distinct applications is presented in Figure 5.

The store locations were chosen by the location-allocation model. Most of the commercial establishments are in the São Paulo districts of “Vila Mariana” and “Moema”. They are characterized by predominantly upper-class high income, mixed land use, and high level of accessibility (public transportation: subway stations and bus corridors). The optimal points generated from the Voronoi diagram and the application of the Weiszfeld algorithm also present locations very close to the first location, highlighting the same districts of the city of São Paulo. The difference between the two locations, although very close, are due to the fact that Voronoi uses Euclidian distances, which are significatively different from the real ones in a non-planned city like São Paulo.

The rental stores and share points considered are those existing in the two selected regions. The objective of the experiment is to tell the owner of the carsharing system the best options for the installation of car delivery and pick-up points, from the perspective of the vehicle supplier. Aspects referring to the users of the system can be seen in [45].

5. Conclusions

Car sharing facilitates access to vehicles for short-term usage and on a need basis, discouraging ownership. This category of service can positively impact the urban environment, as it can reduce the quantity of vehicles purchased, decrease congestion, and improve air quality.

As mentioned previously (item 3.), the locations chosen by the model application are in the districts of “Vila Mariana” and “Moema”, these being among the most developed regions in the city of São Paulo. They exhibit the largest number of subway stations; there are many colleges, universities, and schools, as well as private and public hospitals. There is an intense circulation of people in this region, both residents and visitors. It is also a link between the south and the center regions of São Paulo.

The location-allocation model helps to choose where to establish a car sharing business and likely partners to operate the service. In a city like São Paulo, with several business enterprises in the same branch of activity, the model supports decision making and clarifies logistical issues, such as parking space availability, closest location to pick up and drop off the car, concentration of sharing users, and so on.

The service area model presents the ability to analyze spatially distributed data. Knowing where clients are not willing to walk to use the service presents possible areas for new carsharing stations. By creating a network of intelligent stations, with stations in strategic locations, it is possible to maximize demand and operator profit while minimizing obstacles. The decision-making process is enhanced, considering demographic and other causal factors in conjunction with a network service area analysis.

Recent developments in computational geometry have paved the way for working with larger and more complex Voronoi diagrams, which has made it possible to solve important rental problems. The use of Voronoi diagrams, associated with location-allocation type optimization models, allows the solving of practical problems in the planning phases of transportation systems, as demonstrated in this work. Similarly, spatial logistics problems can be solved in a similar way.

In fact, Voronoi diagrams can be used to solve logistical problems related to the determination of service zones to be allocated to people or vehicles. The use of Voronoi diagrams in problem solving usually leads to better-balanced business factors among locations. This is because Voronoi diagrams associated with these problems have a greater degree of freedom than zoning resulting from traditional methods.

Using spatial data analysis from free, publicly available databases and the car maker service network, the method yields the most favorable districts in São Paulo city to implement a car sharing system.