A novel facility location problem for taxi hailing platforms. A two-stage neighborhood search heuristic approach
| DOI | https://doi.org/10.1108/IMDS-07-2019-0380 |
| Published date | 13 January 2020 |
| Pages | 526-546 |
| Date | 13 January 2020 |
| Author | Hong Ma,Ni Shen,Jing Zhu,Mingrong Deng |
| Subject Matter | Information & knowledge management,Information systems,Data management systems,Knowledge management,Knowledge sharing,Management science & operations,Supply chain management,Supply chain information systems,Logistics,Quality management/systems |
A novel facility location problem
for taxi hailing platforms
A two-stage neighborhood search
heuristic approach
Hong Ma, Ni Shen, Jing Zhu and Mingrong Deng
School of Management, Zhejiang University, Hangzhou, China
Abstract
Purpose –Motivated by a problem in the context of DiDi Travel, the biggest taxi hailing platform in China,
the purpose of this paper is to propose a novel facility location problem, specifically, the single source
capacitated facility location problem with regional demand and time constraints, to help improve overall
transportation efficiency and cost.
Design/methodology/approach –This study develops a mathematical programming model, considering
regional demand and time constraints. A novel two-stage neighborhood search heuristic algorithm is
proposed and applied to solve instances based on data sets published by DiDi Travel.
Findings –The results of this study show that the model is adequate since new characteristics of demand
can be deduced from large vehicle trajectory data sets. The proposed algorithm is effective and efficient on
small and medium as well as large instances. The research also solves and presents a real instance in the
urban area of Chengdu, China, with up to 30 facilities and demand deduced from 16m taxi trajectory data
records covering around 16,000 drivers.
Research limitations/implications –This study examines an offline and single-period case of the
problem. It does not consider multi-period or online cases with uncertainties, where decision makers need to
dynamically remove out-of-service stations and add other stations to the selected group.
Originality/value –Prior studies have been quite limited. They have not yet considered demand in the form
of vehicle trajectory data in facility location problems. This study takes into account new characteristics of
demand, regional and time constrained, and proposes a new variant and its solution approach.
Keywords Facility location, Heuristic algorithm, Regional demand, Vehicle trajectory data
Paper type Research paper
1. Introduction
Urban transportation has been a complicated issue because of the growing density of
population in urban areas and uneven resource allocation. Today, new-fashioned mobile
services, such as Uber, are transforming the way communities and people connect by
creating an efficient market for car-hire services and at the same time eliminating the
uncertainty for both drivers and riders. DiDi Travel is China’s largest homegrown
transportation network company, which provides services including taxi hailing and
private car hailing through its own platform. A total of 7.43bn rides were completed on DiDi
Travel’s platform in the year of 2017 (Zhou, 2018). It is crucial for the company to maintain
drivers’loyalty and willingness to drive, and therefore the travel platform offers additional
financial incentives for its drivers, often taking the form of a rebate when drivers refuel in
gasoline stations with which DiDi Travel has cooperation agreements. For taxi drivers in
major cities in China, refueling is important because taxis operating two shifts of 12 h each
day is a common practice (ShenZhen Daily, 2006). Most full-time drivers work a 12-hour shift
each day. The average distance driven by a taxi driver in a 12-hour shift is usually around
250–350 km. Hence, taxis generally refuel each day because one cannot take the risk of fuel
Industrial Management & Data
Systems
Vol. 120 No. 3, 2020
pp. 526-546
© Emerald PublishingLimited
0263-5577
DOI 10.1108/IMDS-07-2019-0380
Received 15 July 2019
Revised 21 October 2019
Accepted 3 December 2019
The current issue and full text archive of this journal is available on Emerald Insight at:
https://www.emerald.com/insight/0263-5577.htm
This research is supported by Science Fund for Creative Research Groups of NSFC under Grant No.
71821002 and NSFC project under Grant No. 71571160. The authors also wish to express their
gratitude to the data source: DiDi GAIA Initiative.
526
IMDS
120,3
getting exhausted in the midst of a trip. It then becomes obvious that providing the drivers
with a group of well-selected gasoline stations in a densely populated urban area, which
helps minimize the overall travel cost incurred on refueling trips during drivers’idle time,
creates a win-win solution and is mutually beneficial for the platform and its drivers.
In this work, we proposea new variant of the traditional facilitylocation problem, in which
customer demand is derived from big data sets containing vehicle trajectory. The problem is
named as the single source capacitated facility location problem with regional demand and
time constraints (SSCFLP-RDTC). In SSCFLP-RDTC, time constraints are imposed, since we
explicitly assume that drivers refuel during the idle time between two consecutive orders.
In contrast with the traditional facility location problem, demand in SSCFLP-RDTC is not
defined on a single node, but instead, is defined on discretized points spread allover a given
region between two consecutive orders. It is also worth noting that SSCFLP-RDTC can also
be applied to the electric car business, where investment decisions are required, based on
available electric vehicle (EV) trajectory data, for selecting the best group of locations for
setting up public electric-vehicle charging infrastructures from a given candidate set.
In Section 2, previous work related to our problem is reviewed. In Section 3, the problem
is stated in detail, and a mathematical model, the mixed-integer linear programming (MILP)
model, is formulated. Our new solution algorithm is proposed in Section 4, followed by
computational experiments conducted on real data sets and results analysis in Section 5.
In Section 6, we discuss a potential application of SSCFLP-RDTC in the electric car business.
The last section concludes the paper.
2. Related work
The facility location problem addresses a well-known problem referring to the placement of
at least one facility (e.g. a resource or server) among several existing facilities (e.g. demand
points) to serve them (Farahani and Hekmatfar, 2009). It has applications in various areas
such as industry, services, business and economics, to name just a few. Facilities can be
anything which needs to be located such as hospitals, fire stations, fuel stations, retail
outlets, waste disposal sites, etc. (Daskin, 1995). Facility location problems are mainly solved
by using various quantitative techniques from operations research. Depending on the
nature of the facility to be located, various objective functions may be considered. Among
them minimizing travel costs, maximizing service level, minimizing waiting time or
avoiding placement next to hazardous facilities are the most popular.
Based on the characteristics of the problem, there are three types of facility location
problems similar to our problem. One of them is the single source capacitated facility location
problem (SSCFLP), which belongs to the class of NP-h ard problems (Yang et al., 2012). In
SSCFLP each customer has to be assigned to one facility that supplies its whole demand. The
total demand of customers assigned to each facility cannot exceed its capacity. An opening cost
is associated with each facility and is paid if at least one customer is assigned to it. The
objective is to minimize the total cost of opening the facilities and supply all the customers.
Previous studies have developed and applied variousapproaches such as exact methods and
heuristic approaches. With respect to exact methods, Holmberg et al. (1999) developed a
branch-and-bound method with a Lagrangian heuristic and a strong primal heuristic (using
repeated matching). The Lagrangian heuristic is used as a bounding procedure in each node of
the branch-and-bound tree, yielding both lower and upper bounds. Regarding heuristic
approaches, Chen et al. presented a hybrid algorithm, which combines Lagrangian heuristic
and Ant Colony System (LH-ACS) for S SCFLP. The performance of LH-ACS is competitive
with other well-known algorithms. Ahuja et al. (2004) presented a very large-scale
neighborhood search algorithm to solve the real-life instance provided by an Italian cookie
factory. The neighborhood structures are induced by customer multi-exchanges and by facility
moves. Guastaroba and Speranza (2014) extended the Kernel Search heuristic framework based
527
Taxi hailing
platforms
To continue reading
Request your trial