Portal de Periódicos da CAPES

Simulation–optimisation framework for City Logistics: an application on multimodal last‐mile delivery

2018; Institution of Engineering and Technology; Volume: 12; Issue: 4 Linguagem: Inglês

10.1049/iet-its.2017.0357

1751-9578

Guido Perboli, Mariangela Rosano, Michael Saint‐Guillain, P. Rizzo,

Advanced Manufacturing and Logistics Optimization

IET Intelligent Transport SystemsVolume 12, Issue 4 p. 262-269 Special Issue: Selected Papers from the Scientific Seminar of the Italian Association of Transport Academicians (SIDT) 2017Free Access Simulation–optimisation framework for City Logistics: an application on multimodal last-mile delivery Guido Perboli, Corresponding Author Guido Perboli guido.perboli@polito.it ICT for City Logistics and Enterprises Center, Politecnico di Torino, Turin, Italy CIRRELT, Montréal, CanadaSearch for more papers by this authorMariangela Rosano, Mariangela Rosano ICT for City Logistics and Enterprises Center, Politecnico di Torino, Turin, ItalySearch for more papers by this authorMichael Saint-Guillain, Michael Saint-Guillain Institute of Information and Communication Technologies, Electronics and Applied Mathematics, Université catholique de Louvain, Louvain-la-Neuve, Belgium Institut National des Sciences Appliquées de Lyon, FranceSearch for more papers by this authorPietro Rizzo, Pietro Rizzo ICT for City Logistics and Enterprises Center, Politecnico di Torino, Turin, ItalySearch for more papers by this author Guido Perboli, Corresponding Author Guido Perboli guido.perboli@polito.it ICT for City Logistics and Enterprises Center, Politecnico di Torino, Turin, Italy CIRRELT, Montréal, CanadaSearch for more papers by this authorMariangela Rosano, Mariangela Rosano ICT for City Logistics and Enterprises Center, Politecnico di Torino, Turin, ItalySearch for more papers by this authorMichael Saint-Guillain, Michael Saint-Guillain Institute of Information and Communication Technologies, Electronics and Applied Mathematics, Université catholique de Louvain, Louvain-la-Neuve, Belgium Institut National des Sciences Appliquées de Lyon, FranceSearch for more papers by this authorPietro Rizzo, Pietro Rizzo ICT for City Logistics and Enterprises Center, Politecnico di Torino, Turin, ItalySearch for more papers by this author First published: 02 March 2018 https://doi.org/10.1049/iet-its.2017.0357Citations: 28AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract City Logistics has attracted considerable interest from the operations research and logistics communities during past decades. It resulted in a broad variety of promising approaches from different fields of combinatorial optimisation. However, research on urban freight transportation is currently slowing down due to two different lacks, limiting the exploratory capacity and compromise the technology transfer to the industry. First, the majority of the instances in the literature are based on the generalisation of classical instances, often not created for urban applications, or on artificial data, i.e. data not coming from any historical or empirical datasets. Thus, the validation of models and methods becomes more difficult, being the results not directly compared with real or realistic settings. Second, even when some data sources become available, there is no standard way to mixing data gathered from different sources and, from them, generate new instances for urban applications. This study aims to overcome these issues, proposing a simulation–optimisation framework for building instances and assess operational settings. To illustrate the usefulness of the framework, the authors conduct a case study, in order to evaluate the impact of multimodal delivery options to face the demand from e-commerce, in an urban context as Turin (Italy). 1 Introduction Taniguchi and Thompson. [1] define City Logistics as ‘the process for totally optimising the logistics and transport activities by private companies with the support of advanced information systems in urban areas considering the traffic environment, its congestion, safety and energy savings within the framework of a market economy’. In such settings, the transportation community has been recently devoting significant efforts to propose efficient and innovative approaches to address many types of City Logistics problems. On the other hand, a standard framework for simulating and studying the impact of optimisation in City Logistics is currently missing, limiting the possibility to validate in real settings the technology transfer to industry. In particular, as highlighted by Kim et al. [2] and observed in Section 2, there is an obvious lack of available realistic benchmark dataset for the city vehicle routing problem (VRP). The instances in the literature are based on the generalisation of classical instances, often not created for urban applications, or on artificial data, i.e. data not coming from any historical or empirical datasets. The validation of models and methods becomes more difficult, being the results not directly compared with real or realistic settings. Even when real data become available, some other issues come from the availability of a finite dataset, the necessity to anonymise them or to mix real data with empirical distributions. Furthermore, in City Logistics the different categories of stakeholders all play an important role in urban applications, but they are rarely considered all together, leading the search to some local optimum [2]. In our opinion, the later issue is due to the following current limitations: unavailability of full data : given an urban area, gathering the real data associated with all four stakeholders usually requires too much time and/or expertise to be actually implemented and difficulty of combining/reusing existing data : whereas existing studies may provide realistic data involving one or more stakeholders, there is still no trivial way to combine such data from different sources. The contribution of this paper is two-fold. First, we propose to mitigate the two above-mentioned limitations by introducing a new standard optimisation–simulation framework for City Logistics, whereas the framework generalises to many types of RPs encountered in urban areas, its generality also allows to describe and combine requirements coming from different stakeholders. We categorise the sources of information and we present a tool able to mix data gathered from different sources. So we can generate new instance sets which are realistic, i.e. they include all the characteristics of the original datasets. Second, we apply our framework to a case study focused on the online urban freight distribution in the city of Turin (Italy). This study concerns the application of the proposed simulation–optimisation framework to address the dynamic and stochastic VRP with time windows (DS-VRPTWs) problem. We analyse how the solution quality in realistic urban scenarios is sensible to various stakeholder parameters such as customers' geographical distribution, the available types of vehicles and their limitations and the use of lockers for delivering part of the demand. Our experimental plan leads to a broad variety of realistic benchmarks, each of these being specialised in a particular operational context in the online urban collection of parcels. This portfolio of benchmarks is made available to the community under a simple common format, in order to reuse them in different case studies. This paper is organised as follows. In Section 2, we review the literature for vehicle routing case studies and applications in realistic urban areas. Section 3 describes the framework we propose in order to analyse realistic urban freight collection problems. Section 4 shows how our framework can be exploited to realise a concrete case study of online freight collection in a realistic urban context. Conclusions and perspectives are discussed in Section 5. 2 Literature review We focus our review on realistic city VRP-related case studies one can find in the literature up to these days. The purpose of this section is primarily to identify the scope of city VRP applications already addressed by the scientific community, and second the benchmarks that are still currently available in that field. This review is initially based on the excellent work [2], which we restrain in order to focus on real case studies, in particular, those for which the benchmarks are still available. In [3], a real-world problem of distributing pharmaceutical products in downtown Bologna (Italy) is considered and modelled as an asymmetric capacitated VRP (CVRP). The test instances, involving up to 70 customers, are still available on the author's web page. Variability in vehicle travel times has been studied from several aspects. In particular, in [4] Kong et al. worked on shortest paths under dynamic travel times in a downtown area in Shanghai. The raw data [1 month of taxi global positioning system (GPS) data, 3 months of bus GPS data in Shanghai during the year 2007] is still currently available on demand to the authors. Multi-level VRPs such as the two-echelon VRP introduced by Perboli et al. [5] have also received recent interest in urban context. In [6], Escuín et al. present a real-world case study involving a time-dependent VRPTW in Zaragoza (Spain), in which customers can be either directly delivered from the classical depot or by means of green vehicles by using intermediate urban depots. Vehicle breakdowns have been considered in [7]. Whenever a breakdown occurs, the re-planning problem is modelled as a modified team orienteering problem over the remaining customers and vehicles. They validate their heuristic method on real data from a food distribution company in Attica (Greece). Note that their benchmark is still available on demand. Environmentally friendly decision systems in the context of (city) VRPs are increasingly studied nowadays under various names: green VRP (GVRP), pollution-RP (PRP), emissions VRP etc. Alternative fuel vehicles are considered in [8] by means of the GVRP. The objective is to minimise the total routing cost given limited refuelling stations. Numerical experiments are conducted based on data from a medical textile supply company in Virginia. These data are still available under demand. In [9], a realistically generated benchmark is used in order to illustrate the PRP over a set of cities in UK. The benchmark is still available. A number of similar studies have been conducted on artificially generated benchmarks, many of them based on Solomon's instances. More recently, Maggioni et al. [10] provided a realistic benchmark for the multi-path travelling salesman problem (TSP) with stochastic travel costs [11] applied to electric and hybrid vehicles in freight distribution. In particular, Maggioni et al. [10] propose a first example of instance generator. However, it was in a prototype form and strictly dependent on the application, lacking a global vision. Our literature review highlights that the city VRP contributions contain very few real-world-based applications and the results are normally based on academic (and unrealistic) datasets. Up to our knowledge, among those studies that are based on realistic data, the corresponding benchmarks are still currently available for only six papers [3, 4, 7-10]. Moreover, these applications lack a global vision and they are scarcely repeatable in a different context. Thus, in the next section, we introduce our simulation–optimisation framework, proposed to overcome these issues. Recently, the DATA2MOVE initiative started to collect data from different sources for logistics and supply chain applications, but the project is still at an early stage [12]. A lack emerging from the literature is the identification of the main sources types, how to mix and how to interface them with one or more simulation and optimisation module in order to give flexible solutions to the stakeholders and the users. 3 Simulation–optimisation framework for VRP in urban areas The simulation–optimisation framework proposed in this paper is depicted in Fig. 1. According to Crainic et al. [13], this framework applies a sequential simulation–optimisation, where the simulations are numerical and based on the Monte Carlo method. The simulation is implemented in Python, while the optimisation modules can be defined directly in Python by the Pyomo modelling tool including the PySP library for stochastic programming problems [14, 15] or can be integrated as external modules. Fig. 1Open in figure viewerPowerPoint Simulation–optimisation framework Thus, the framework is composed of the following modules: i. Data fusion and operational context description : The first phase of the framework consists in describing both the problem studied and the operational context, which may consider different types of data sources. We define the operational context using the following five sources of informations: city network graph, vehicles and travel times, behavioural data (e.g. users choice preferences), socio-demographical data and city constraints (e.g. limited traffic zones, specific restrictions for certain vehicles etc.) and problem objectives and constraints. Some data may be stochastic, i.e. they can be described by random variables, whenever some component of the operational context is uncertain (e.g. service or travel times, customer demand or the presence etc.). The problem is then fully defined by the problem objectives and constraints data type. The framework requires as input a problem (or operational context) description consisting of five types of data: City network graph and maps : They are represented by complete directed graphs over a set of depots and customers. Ideally, vertices should be associated geographical coordinates so that to be visualised on real maps. The city network graph is usually obtained using raw data from cartography and the companies including maps and empirical distributions of customers and depots. Amongst the four main stakeholders identified by Kim et al. [2] (residents, carriers, shippers and local administrators), the city network graph explains the baseline geographical attributes and means of the residents (customer locations), the shippers (the location of the depots) and the carriers (the available road network). Vehicle fleet and travel times : They include the specificities of the vehicle types, as capacity, speed, fuel consumption etc., as well as their respective travel times and costs matrices. Vehicle fleet and travel times capture the means supplied by the shippers. In practise, these are provided by the company and possibly combined with data from external sources (such as sensors spread over the city network). Time dependence and/or uncertainty in the travel times/costs, if any, may also be described here together with other uncertainties (e.g. vehicle breakdown probability distributions). Behavioural and socio-demographic data : They include information concerning the density and the purchasing behaviours of final customers for a specific market. Thus, they clearly describe the resident's stakeholders in all of their possible attributes. In a static context, these capture the customers' constraints (e.g. time windows, demands, origin–destination matrices etc.). In dynamic applications, any stochastic knowledge about the customer habits can be described here (e.g. demand or service-time probability distributions etc.). City constraints : Regulations imposed by the local administrators such as access time windows (e.g. forbidding trucks during rush hours), vehicle weight restrictions (e.g. no heavy truck in the city centre) etc. City constraints clearly represent the administrators in all the regulations that could be imposed on the other stakeholders (e.g. the carriers). Problem objectives and constraints : Describe the problem itself in terms of constraints, preferences, as well as the objective function to be optimised. They can be defined by declaring the specific optimisation module including its interface with the scenarios or using an mixed integer problem (MIP) solver by the Pyomo modelling tool. This partitioning of the data into five distinct types allows to easily study the impact of modifying a specific aspect of the operational context. Furthermore, it provides the possibility of combining/reusing data from existing case studies, hence alleviating the full data unavailability issue discussed in Section 1. For instance, provided a real-world case study on a classical CVRP, modifying only components d and e of the problem allows to study the impact on the total carbon emissions of restricting the access of the city centre to green vehicles. Furthermore, filling component c with customer demand probability distributions permits to study stochastic VRPs, whereas updating component b could allow studying the impact of taking travel time variability into account, as well as to use empirical distributions coming from other studies, letting to anonymise industrial data. ii. Scenario generation and simulation : Once both the problem and the operational context are well defined, a broad set of scenarios is generated by using a high-level scenario generator, which allows the researchers to develop specific scenarios for different frameworks. Each scenario represents a particular realisation of all the random variables involved in the problem data. In other words, each scenario is the description of a particular operational day. If the problem and operational day descriptions contain no uncertain data, the scenario becomes the description itself. Otherwise, a set of instances are generated using Monte Carlo sampling. The framework lets the user define deterministic operational scenarios or stochastic ones with associated scenario tree to each simulation scenario. The present version of the simulator implements a Monte Carlo method, a module for georeferencing the data and a post-optimisation software. In more detail, the method works as follows: The Monte Carlo simulation module repeats the following process for a given number of iterations: o Given the different data of the operational context as well as eventual distributions of the data themselves, the simulator generates a series of city scenarios. o The chosen optimisation module is executed in each scenario. o A first statistical analysis on the aggregate results of the scenario-based optimisation of a single iteration of the Monte Carlo simulation is performed. These data are used in order to check if one or more unrealistic or extreme situations have been introduced in the simulation itself. o To make a more accurate definition of travel times and cost matrices, the georeference module is used. The georeference feature is implemented by means of Google Earth application programming interfaces (APIs) and it is also used to graphically represent the results of the simulation itself. The distribution of the simulation-based optimisation solutions is computed and a series of statistical data are collected. A post-optimisation software module is devoted to compute additional key performance indicators (KPIs) [e.g. carbon dioxide (CO2) and NOx emissions, stop per working hour, service and travel times). iii. Optimisation : During this phase, each scenario is solved using a dedicated optimisation algorithm that we consider here as a black box. Provided that the solver outputs the KPIs required by the case study into consideration, the post-optimisation analysis is conducted. To cope with different contexts in urban areas, this simulation–optimisation framework is composed of different building elements addressing the following problems: Mathematical model generated by the Pyomo modelling tool. VRPTW combined with the load balancing. Stochastic TSP. DS-VRPTW solved by the optimisation algorithm proposed by Saint-Guillain et al. [16]. iv. Context modification : During this phase, some properties of the description are modified, leading to a new operational context to be analysed by reiterating through phases 2–4. 4 Case study: online urban freight collection in Turin (Italy) To demonstrate the potentialities of the proposed simulation–optimisation framework, we adopt it in the case study of the city of Turin (Italy). Our aim is two-fold: analyse the impact of multimodal delivery options to face the demand generated by the e-commerce and highlight the importance of considering real benchmark dataset for DS-VRPTW coming from different sources and stakeholders. 4.1 Operational contexts and benchmark generation Online shopping is rapidly increasing the freight flows which transit into the urban areas. According to the authors in [17-19], while the business-to-consumer segment of e-commerce represents around 30% of the e-commerce turnover, they generate 56% of all e-commerce shipments. Moreover, e-commerce involves individually fragmented and time-sensitive orders of generally small-sized items, leading to more traffic in urban areas and negative externalities on the environment [20]. These are challenging factors for City Logistics applications, which are more and more focused on the integration of different delivery options (e.g. cargo bikes, drones, lockers etc.). In fact, our paper addresses this topic, considering the following four benchmarks: Benchmark 1 (B1) : Only traditional vehicles (i.e. fossil-fuelled vans) are used to manage the parcel delivery in urban areas. Benchmark 2 (B2) : Outsourcing of classes of parcels to green carrier subcontractors (i.e. they use bikes and cargo bikes) is a common practise to obtain operational and economic efficiency and customer proximity while reducing the environmental impact of logistics activities [21]. Thus, in the B2 we consider that a green subcontractor delivers the parcels up to 6 kg in the central and semi-central areas of Turin. On the contrary, the traditional carrier manages all remaining parcels. Benchmark 3 (B3) : We consider the adoption of delivery lockers. They represent self-service delivery location, in which the customer can pick up or return its parcel, according to the best and convenient time for him. In practise, these can be seen as special ‘super-customers’ that aggregate the daily demands of a subset of the actual customers. Benchmark 4 (B4) : In this benchmark, we consider the integration of the vans with both bikes and lockers. These specific benchmarks derive from the combination of three parameters defined ‘a priori’: the size of the traditional vehicles' fleet, the size of the green vehicles' fleet and the number of lockers. These data are provided by an international parcel delivery companies and an international e-commerce operator, which acting in Turin. Other input data considered in the DS-VRPTW are: City network graph and maps : We consider a 2.805 × 2.447 km2 area in Turin, which includes the centre of the city and a semi-central area, as in [21] (see Fig. 2). Moreover, the list of the depots, the locations of lockers and of the potential customers inside the selected area are considered. Concerning the depots, we contemplate a distribution centre located on the outskirts of the urban zone and a mobile depot in the city centre. The former supplies the traditional carrier, while the second represents a satellite facility for the green carrier. In addition, the list of all the roads inside the city area is also required. Such list is arranged as a network of road segments, each road segment is defined as a sequence of two connected points, i.e. the crossroads. The information concerning the roads was extracted from the shapefiles made available by the local public authority in Turin. For each road segment, the average daily speed is measured by speed sensors. Each element of the mentioned lists is defined with a unique identification number and its real GPS coordinates. Vehicle fleet and travel times : As mentioned above, we consider two types of vehicle fleets: vans and cargo bikes. The parcel delivery company interviewed provides the characteristics of vehicle fleets (e.g. capacity, service time and speed). The service time is a vector containing the information for each type of parcel handled, for the upload from the depot and for the download into the locker. According to Perboli et al. [21], we consider three classes of parcels: mailers (i.e. parcel with a weight up to 3 kg) small parcels (i.e. parcel with a weight between 3 and 6 kg) and large deliveries (i.e. a parcel with weight over 6 kg). The expected number of parcels for each class, expressed as a percentage of the total number of parcels delivered, are shown in Table 1. Behavioural and socio-demographic data : The horizon size is given here. We consider an 8 h working day, from 9:00 to 17:00. The time unit considered is 1 min and the time horizon is split into four time buckets with the same length. For each potential customer, the demand expressed as parcel's volume is provided, together with the time window for the service. The time windows are assigned considering the percentage of prime members (i.e. those whose requests are prioritised restricting the time window to the first two time buckets). Then, the expected behaviour of each potential customer of the DS-VRPTW is described. It gives the probability that, for each customer location i and each time unit t of the time horizon, an online request (i.e. picking up a parcel) appears at a time t for location i. City constraints : We do not consider any specific city constraint. Problem objectives and constraints : The objective is first to maximise the (expected) number of online requests satisfied by the end of the horizon and the second minimises the total distance travelled by the vehicles. Fig. 2Open in figure viewerPowerPoint Area considered in the case study. Note that in this figure the mobile depot (square) and a set of offline customers (circles) and lockers (crosses) are represented Table 1a. Input data Classes of parcel Class Weight range, kg Percentage on total parcels, % mailer 0–3 57 small delivery 3–6 13 large delivery >6 30 Capacity Vehicle Parcel size maximum, kg Capacity Coverage locker 6 20a parcels 1 km van 70 700 kg NA cargo bike 6 70 kg NA Speed in urban area Setup time vehicle speed load locker 15 min van 40 km/h load bikes at 15 min — — mobile depot — cargo bike 20 km/h — — Service time to deliver each class of parcels Vehicle Mailer, min Small delivery, min Large delivery van 4 4 5 min cargo bike 2 2 NA a Maximum number of parcels per day. Note that part of the locker is actually filled with the parcels of the previous 3 days. The operational context defines the number of potential customers in the city map, the number of offline customers selected among the potential ones and the percentage of prime members. In this simulation, we generate three different-sized operational contexts with, respectively, 500, 250 and 100 potential customers. Each context contains 70% of offline customers and 25% of prime members. These potential customers are randomly picked from the pool of potential customers listed in the input data and then anonymised for confidentiality matters, by offsetting the Cartesian coordinate system. Once the potential customers are defined, it is possible to compute the matrix of the mutual distances among the customers and the depots on the map. Such distances are computed applying the Dijkstra's shortest path to the network of road segments specified in the input data. The high level of detail in the network, coupled with the haversine formula used to estimate the distance between each pair of points that compose a road segment, provide us an outcome, which is much more accurate than a simple application of the Manhattan distance. The obtained results are in line with the once provided by the most common web-mapping service Google Maps. From the distance, matrix is then possible to compute the travel times between pairs of locations, by using the measured road segments' speeds available in the input data. The set of online requests appearing during the daily time horizon is defined by considering three different degrees of dynamisms: 15, 30 and 45%. Three sub-contexts are thus defined for each operational context, according to the degree of dynamism assignation. For each sub-context, a set of n instances is sampled by generating n Poisson random variates (PRVs) with parameter dependent on the degree of dynamism considered. Each PRV i represents the effective number of online requests that appear in the Instance i. The accorded set of online customers is finally randomly selected from the list of potential ones, allowing multiple requests for the same customers, but provided that they appear at different moments (i.e. time units). Each scenario, which in the case of DS-VRPTW corresponds to a sequence of revealed online requests along the day together with their specific reveal times and locations, is then independently solved by the optimiser. All the instances are generated and classified in classes (i.e. the benchmarks presented above), depending on the operational context, as described in Section 3. The benchmarks are available online on the git repository available at the address https://bitbucket.org/orogroup/city-logistics.git. Table 1 resumes the values of the input data considered in our analysis. This information derives from interviews with Chief Executive Officer and logistic director of an international parcel delivery company a