Real-time fleet optimization in urban freight distribution using real traffic data

62 第 49 卷第 1 期 七月 2024 Diqiu Kexue - Zhongguo Dizhi Daxue Xuebao/Earth Science Journal of China University of Geosciences https://dqkx-periodicals.com Vol. 49 No. 1 2 0 2 4 https://doi.org/10.3799/dqkx.2024.5681 Real-time fleet optimization in urban freight distribution using real traffic data Abdolreza Sheikholeslamia,*, Reza Behzadb aAssociate Professor, Department of Transportation Engineering and Planning, School of Civil Engineering, Iran University of Science and Technology, Tehran, Iran. bPh.D. candidate, Department of Transportation Engineering and Planning, School of Civil Engineering, Iran University of Science and Technology, Tehran, Iran. *Corresponding author: [email protected] Received: 18 April 2024 Accepted: 13 May 2024 Published: 25 May 2024 Abstract: Freight distribution is one of the main components of city logistics. The use of intelligent transportation systems and technological advances in communication and information has made it possible to integrate freight transportation management with network traffic elements. This paper provides a framework for real-time management of the freight distribution fleet under real-time traffic conditions. In this framework, the freight distribution process was optimized under traffic conditions and network events. The main innovation of this article was the simultaneous optimization of the routes (sequence of customers) and the paths (sequence of roads between customers). The presented framework uses two modules: shortest path module and routing and scheduling module, to optimize fleet performance and costs based on real-time data. In the computational experiment in the current research, the real network was used. Real-time traffic data was received from Google Maps at specified intervals, and the simulator program (Python) simulated freight distribution operations. Experimental results showed using this framework, fleet travel time would reduce 9% in wide time windows and 11% in the narrow time windows. Although early time service had not changed significantly in the narrow time windows scenario, but late service time reduced about 14%. Keywords: Freight distribution, Real-time traffic data, Real-time fleet management 63 1. Introduction City logistics has been defined as the process for totally optimizing the logistics and transport activities by 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 (Taniguchi et al., 2001). Distribution of goods and provision of services is one of the main components of city logistics, including scheduling and operating fleet vehicles to satisfy clients' demands. This issue appears in a variety of situations, such as the transportation of patients to hospitals or the pickup and delivery of goods. More specifically, Vehicle Routing Problems (VRP) are the problems of creating a set of least expensive vehicle routes that meet the needs of a geographically dispersed clientele while adhering to operational constraints. There are different factors that influence this problem, such as clients' demand and service condition (amount and position of demand, time windows, service times, and others), fleet operational conditions (capacity, position, states, and availabilities of vehicles), and traffic conditions (travel time). Depending on these factors, the problem is classified as Static or Dynamic. In Static problems, design parameters and factors have constant values and do not change. While in Dynamic problems, the elements of the problem are variable. The introduction of new clients with a demand for products or services is the most common source of dynamism in routing; other sources include dynamically revealed demands for a set of known clients, dynamic travel times, and vehicle availability (Pillac et al., 2012). Gathering and processing the input data variety makes it possible to optimize the dynamic VRP and effective fleet management in freight and services distribution. Simultaneous use of GIS, GPS, smartphones, traffic flow detectors, etc., makes it possible to provide real-time data such as vehicle location, new client demand, travel time determination, etc. These ICT advances have led to easy and fast real-time data acquisition, and its processing is feasible and affordable. In a study, Falek et al. (2022) investigated the impact of real-time rerouting on the road network of the city. The results of this article showed that rerouting with real-time travel time only reduces travel time during busy hours and during long trips. Our main innovation was to provide a framework for real-time fleet management and scheduling used as a decision support system (DSS) to improve urban logistics. Travel time changes, events in the road network, and new requests can be optimized using this decision support system. In the presented framework, the network links' actual travel time was received from the traffic condition of Google maps, and events such as new requests were created randomly. The decision support system optimizes the routes and schedules during the freight distribution depending on the road network's current conditions and new demands and events. The advantage of the proposed framework is that it uses two modules, routing and real time shortest path. Fleet management in this process is done in such a way that while optimizing the routes (sequence of customers), the shortest path between two customers in the road network is dynamically determined. Another accomplishment of this paper was solving dynamic VRP using real-time travel time in the real world network during the distribution of goods and services. For this purpose, an Adaptive Large Neighborhood Search (ALNS) method based on Ropke and Pisinger (2006) with a simulated annealing heuristic optimizes the routes and schedules. The ALNS method can be used when it has a short run time. Therefore, we modified the Ropke and Pisinger (2006) method. The evaluation results showed that the modification is effective. 2. Literature review While the literature has extensively examined the static version of the vehicle routing problem (VRP), advancements in information and communication technology have expedited the study of the dynamic version of the problem. The dynamic vehicle routing problem (DVRP) is predicated on the fleet manager's partial knowledge of demand and the continuous disclosure of new real-time information during the operation period. Ghiani et al. (2003), Eksioglu et al. (2009), Pillac et al. (2013), Ritzinger et al. (2015), Abbatecola et al. (2016), and Psaraftis et al. (2016) are a few of the studies that provide in-depth analyses of the dynamic VRP. A taxonomy of DVRP papers was created by Psaraftis et al. (2016) based on eleven criteria. These include the problem type, the logistical context, the mode of transportation, the objective function, the size of the fleet, the time constraints, the vehicle capacity constraints, the ability to turn away clients, the dynamic element's nature, the nature of any stochasticity, and the solution method. The term "type of problem" in this taxonomy refers to either dynamic or static, deterministic or stochastic. In deterministic and dynamic problems, certain information elements depend on time, and all data are known beforehand. 64 Stochastic processes are used to represent uncertain data in stochastic and dynamic problems, which are also referred to as real-time routing and dispatching problems. Due to advancements in information and communication technologies, this novel problem class enables more accurate handling of applications in the real world. The benefit is that stochastic knowledge about the disclosed data is taken into account in addition to effectively managing dynamic events. In previous studies, the dynamic nature of the routing problem's components referred to the dynamics of requests, travel times, length of service, and availability of vehicles, and the stochastic nature of the routing problem referred to deterministic or stochastic of these components. During the course of the plan's execution, dynamic requests can include additions, deletions, and modifications to the client's locations and/or demands. A mathematical model for dynamic fleet management was developed by Cheung et al. (2008). It took into account dynamic data like vehicle locations, travel times, and incoming client orders. It then used a re-optimization process to update the route plan whenever new dynamic information became available. Schmid (2012) demonstrated approximate dynamic programming algorithms for the dynamic ambulance relocation and dispatching problem under uncertainty of requests location. Ferrucci et al. (2013) developed an approach that guides vehicles into new requests that stochastic knowledge of recent call exploited from past request data. DVRP that considers uncertainty in the client's demand can be found in Juan et al. (2011), Goodson et al. (2013), Zhu et al. (2014), and Florio et al. (2018). Travel time variety and uncertainty is another dynamic aspect of VRP. There are different ways to model dynamic travel time as time-dependent, stochastic, or stochastic time-dependent. Malandraki and Daskin (1992), as introduction studies on VRP with time-dependent travel time, define, formulate, and create solutions for the timedependent traveling salesman problem and the time-dependent VRP. This paper indicates that most of the existing heuristic for static VPR cannot be easily extended to time-dependent problems and present the nearest neighbor heuristic for time-dependent VRP. Fleischmann et al. (2004) present a general framework for implementing timevarying travel times in vehicle-routing algorithms using travel time data from contemporary traffic information systems. Real-time client requests and dynamic travel times are taken into account and addressed in dynamic vehicle routing and scheduling problems with time windows. Li et al. (2009) presented and investigated real-time vehicle rerouting problems with time windows, which are relevant to pick up-delivery services that experience service disruptions due to vehicle breakdowns. In such cases, one or more vehicles must be rerouted in real time to perform uninitiated services in order to reduce a weighted sum of operating, service cancellation, and route disruption costs. James et al. (2019) presented a solution to solve the VRP with online demand. In this solution, they reduced the calculation time by combining Neural Combinatorial Optimization and Deep Reinforcement Learning. Liu et al. (2023) solved the freight distribution problem with real travel time, they solved the problem statically, that the actual travel time between customers is received before route optimization. Jie et al. (2022) presented a hybrid model to solve the distribution problem, in which travel time is considered as time dependent. In this paper, the problem is evaluated on the modified Salamon test benchmark. More studies of dynamic vehicle availability or vehicle breakdowns can be found. 2.1. Dynamic travel time in the dynamic vehicle routing problem The development of data collection equipment and Intelligent Transportation System (ITS) has made it possible to perceive changes in traffic conditions and travel time at different times and consider its effects on routing. Travel time information based on ITS is classified into three categories: (a) historical, (b) real-time, and (c) predicted. Historical travel times provide information about previous travel times. If travel times follow a normal distribution, they can represent historical travel times on road network links. The probabilistic vehicle routing and scheduling processes rely on historical travel time data to determine the best starting time and visit clients' orders. Real-time travel times provide dynamic data regarding current travel times. Advanced information systems will typically provide travel times that are 5 minutes before the current time. Vehicle routing and scheduling algorithms require real-time travel time data. Predicting travel times is useful for planning vehicle operations, taking into account events, road construction, and other factors. However, techniques for accurately predicting future traffic conditions are necessary. This paper 65 presents a framework for freight distribution management that solves and compares VRP statically and dynamically. The framework uses real-time travel time in freight distribution management. In other words, in this paper, the vehicle routing problem is solved in real-time on a real network. 3. Problem definition Several factors influence the allocation of goods and services, which gives VRP its dynamic nature. These include changes in travel time and traffic congestion. With the development of ITS and ICT, the road network's real-time traffic data can be determined, and the possibility of real-time fleet planning and management has been provided. This paper presents a decision support system that uses real-time data on travel time, client demand, monitoring of the fleet's position and performance, the status and time of client service to make appropriate decisions in the management of the fleet . Figure 1 shows the conceptual framework of the real-time fleet management system (RFMS). This process optimizes dynamic routing and scheduling using real-time data such as online orders, real-time traffic state, etc. Figure 1. Conceptual framework of the real-time fleet management system (RFMS) 3.1. Shortest path module As in the literature review, most VRP studies consider connections between clients, and its travel time between them has a constant value. In other words, the VRP is defined on a graph whose nodes are clients, and links are the connection between clients. The weight of links is the travel time between clients, which can be considered deterministic or stochastic, historical or real-time, or predicted. While in the real world, vehicles have to travel a path between clients that includes roads and intersections in the road network. This path can be defined by the sequence of nodes and links of the road network graph. And the length of the path indicates the distance between two clients. On the road network, there are several paths between two clients. The shortest path between the existing paths should be 66 selected to minimize travel costs. So, two graphs are defined for the VRP. The first graph is the road network graph; the shortest path between clients is determined from it. The second graph is the client graph; the vehicle route among clients is distinguished from it. The links between clients in the client graph are the shortest path between clients in the road network graph. And the weight of the links (travel time between clients) in the client graph is the shortest path length in the road network graph. The classic VRP is solved on the client graph, and the output is the client sequence (routes) assigned to a vehicle. Changing traffic congestion and the roads' travel time during the day, shortest paths, and travel time between the clients change. Thus, the shortest path module should determine the shortest path by changing the travel time of roads. If the paths and travel time between the clients change, the client graph links' weight should be modified, so RFMS should optimize routes and schedules. In this paper, the Dijkstra algorithm is used to determine the shortest path between clients in the road network. The Dijkstra algorithm's input is the road network graph, and its output is the shortest path from a specific node to all nodes. In the RFMS, the real traffic state portal collects road travel time during distribution operations. And the shortest path module determines the best path between clients based on the real-time travel time and then modifies the client graph. It is better for vehicles to use arterial roads and do not travel in the collector and local roads except to reach the clients from an operational perspective. In this paper, the actual travel time is multiplied by the road function coefficient (a) to calculate the shortest path. This coefficient is different for each type of road. In this paper, the coefficient (a) is considered to be 1.3 for local roads, 1.2 for collectors, and 1 for arterial. The use of these coefficients means that arterial had priority in calculating the shortest path. If the arterial's actual travel time is higher than the collector at least 20%, then the arterial is selected. It should be noted that this coefficient is used only in choosing the shortest path and is not considered in calculating the travel time of the shortest path. 3.2. Vehicle fleet monitoring The vehicles' trip starts from depo and move towards the first client in the specified route. The sequence of road network nodes defines this route. Each device serves that client after reaching the destination (the first client on the to-do list). Serving each client takes as long as the service time. At the end of the service, the vehicle moves to the next client. In real-time fleet management, it is necessary to determine the location and status of the fleet. The vehicle fleet monitoring component allows us to determine the location of vehicles. The system generally works with GPS and communication technologies such as smartphones and will enable vehicles to be tracked. In this paper, to evaluate the RFMS, the vehicle operates in the distribution process was simulated. This simulation started with the beginning of the distribution time and, at specified intervals, determined the position of the moving vehicles according to the route and actual travel time. When the vehicle was serving the client, the vehicle stopped during the client's service time and started moving at the end of the service. This process continued to complete the service to all clients. So, the position and status of the fleet can be determined at any time from this simulator. 3.3. Real traffic state portal With the development of ITS and ICT, it is possible to collect real-time traffic data. Real-time traffic data includes various data such as travel time, traffic flow, congestion, level of service, traffic incident, etc. The combination of data collection equipment, analysis, and presenting information makes the advanced passenger information system (APIS). APIS data can be obtained from equipment installed on roads, traffic control centers, vehicles, and users. Using APIS allows the user to make the appropriate decision to continue the trip. This article uses real-time traffic data to manage and guide the freight distribution fleet. As Figure 1 shows, in the RFMS, real-time traffic data is received through the Real traffic state portal. The real-time data collected includes the traffic situation and network events. RFMS uses two types of real-time data: 1) route and schedule re-optimization use real-time travel time to optimize fleet operation during freight distribution. The real-time travel time data is received from the real traffic state portal. 2) Network events such as incidents are detected through this portal, then rerouting and rescheduling module re-optimize routes and schedules by considering detected events. In this paper, the RFMS is implemented on the real network using real-time data. The real-time travel time of the road is received using the API code from the Google Map. Although this article does not consider the validation of Google data, in various studies, the validity of Google traffic data has been demonstrated (such as Zhao and Spall 67 2016; Sana, Castiglione, and Cooper 2017; Rahmani, Koutsopoulos, and Jenelius 2017). In this article, it is essential to receive real-time traffic data on the real network, which data from Google Maps is thought to be accurate and easy to implement. 3.4. Routing and scheduling module The main component of the RFMS is the routing and scheduling module. This part determines the routes that include the client sequence and client service time to optimize freight distribution costs. In other words, it solves VRP in this module. The routing and scheduling module's input is client information (including demand, the earliest service time, service time), travel time or cost information, fleet specifications (including the number of vehicles available and each vehicle's capacity). As mentioned in the literature review, various methods have been proposed to solve DVRP. In this paper, the Adaptive Large Neighborhood Search (ALNS) method has been used that is described below. 3.4.1. Adaptive Large Neighborhood Search (ALNS) The ALNS method was introduced by Ropke and Pisinger (2006) and Pisinger and Ropke (2007) to solve various routing problems. It has extended the Large Neighborhood Search (LNS), which is developed by Shaw (1997). The process of choosing heuristics, accepting produced solutions, and adding and removing heuristics make up the bulk of ALNS. Then, Algorithm 1, which represents the overall ALNS procedure, is explained in pseudo-code. Algorithm 1: General framework of the ALNS Set initial feasible solution, yinit Initialize T Calculate removal & insertion heuristic initial probabilities While stop criterion met: Choose removal & insertion heuristic Apply removal heuristic to y → ytemp Apply insertion heuristic to ytemp → ynew Generate a random number, 𝜉 If (𝑒– (𝑧(𝑦𝑛𝑒𝑤)−𝑧(𝑦)) 𝑇 ⁄> 𝜉) then Set: y = ynew , z(y) = z(ynew) If ( z(y*) > z(ynew) ) then Set: y* = ynew , z(y*) = z(ynew) Set: T = cT Calculate removal & insertion heuristic probabilities Return y* The ALNS method uses an initial feasible solution and improves the solution using removal and insertion heuristics. Removal heuristics that remove some clients from the routes and insertion heuristics that reinsert them into the routes generate a solution's neighborhood. A roulette-wheel technique select removal and insertion heuristics to generate a neighborhood in each iteration. To select the remove and insert heuristic in each iteration, the probability of each heuristic i is calculated (Wi / ⅀Wj). πi is the heuristic score i obtained in each time segment. Each time segment contains 100 iterations. πij the heuristic score i in segment j is 0 at the beginning of the segment, and in each iteration, one of the following values depending on the new solution is added to πij: σ1: The last remove-insert operation resulted in the new global best solution. σ2: The last remove-insert operation resulted in a solution that has not been accepted before, and the cost of the new solution is better than the cost of the current solution. σ3: The last remove-insert operation resulted in a solution that has not been accepted before. The new solution's cost is worse than the current solution's cost, but the solution was accepted . At the end of each segment, each heuristic weight is calculated from Wij+1=Wij(1-r) + r.πi/θi. In this equation, θi is the number of heuristic i, and r is the reaction factor determining how much Wi is affected by the recent segment's results. 68 The ALNS method runtime depends on the number of clients that are removed and inserted in each iteration. In this article, we have limited the number of removes and inserts to reduce runtime. The removal heuristic removes some of the clients at the beginning of the routes. The value of a is the percentage of total initial clients and is constant during the distribution process. During the distribution process, clients who have received services are eliminated, and the number of clients is reduced. Since the value of a is constant, the percentage of clients that the removal heuristic removes increases until the removal heuristic includes all clients. ALNS uses a simulated cooling and heating method for the local search framework. The new ynew solution with the total cost of z(ynew) is acceptable if 𝑒– (𝑦𝑛𝑒𝑤−𝑦) 𝑇 ⁄> 𝜉. Where T represents temperature, and ξ represents a random number between zero and one. In each iteration, the temperature decreases with the cooling rate (0 < c < 1). The temperature starts at Ts and is calculated from Tn = c.Tn-1. The initial value of temperature (Ts) is determined from w.z(yinit), where w is the temperature control parameter. Removal heuristics In this paper, three removal heuristics were used. In each iteration, one of the heuristics was selected by the roulettewheel technique. The selected remove heuristic deletes some clients from the existing solution and adds them to the removal list. The removal list includes all clients whose request has not been answered. The following removal heuristics are described: Random removal heuristics: This heuristic removes the q client randomly from the routes and adds them to the removal list. Random removal Heuristic is the simplest heuristic that causes variation in the results of the solution. Worst removal heuristics: In this heuristics, the aim is to remove high-cost clients. Client cost was calculated by changing the total cost of service by removing the client. After calculating the cost of each client, clients were ranked in descending order based on cost. q Clients were randomly removed from the top of this ranking. Random selection prevents a client was repeatedly removed. The randomness control parameter (p) is multiplied by a random number between zero and one and the number of clients to select clients randomly. The product sets the position of the client to be removed from the list. Small p values cause clients to be selected from the beginning of the list, and the larger p values lead to selection at a lower rank (Ropke and Pisinger, 2006). Related removal Heuristics The purpose of this heuristic, introduced by Shaw (1997), is to remove similar clients. By removing similar clients from a solution, it is possible to interchange clients in a new place and create new solutions. In this algorithm, first, a client is randomly selected, and then its relatedness with other clients is calculated. In calculating the relatedness (Rij), four indicators of the distance between clients, service time, client demand, and Being on the same route, are used. Thus Rij = a1 (dij) + a2 (| Ti-Tj |) + a3 (Di-Dj) + a4 (X) where dij, Ti, Tj, Di and Dj Are normalized in the range (0,1) and the value of X is 1 if two clients are on the same path and otherwise 0. The parameters determine the weight of each indicator. After calculating the value of Rij, clients are ranked down. The q client is randomly removed using the p parameter, which has a similar role in the worst removal. Insertion Heuristic: This paper used two insertion heuristics presented by Ropke and Pisinger (2006). The insertion Heuristic was used after the removal heuristic and inserts the clients removed from the routes and included in the removal list. Greedy heuristics: In this heuristic, the best position to enter each client into the existing solution was determined. The best place was the route and the place on the route, with the least change in total distribution costs. The greedy algorithm determines the list of the lowest insertion cost of clients in each iteration. Finally, the clients insert the solution at the lowest cost. 69 Regret heuristic: The basic greedy heuristic clearly has a problem in that it frequently delays placing challenging clients until the very end, when our options are limited. The regret heuristic selects the request to insert by taking look-ahead information into account in an attempt to get around the issue. In each regret heuristic iteration, the difference between the insertion cost in the best place and the second-best place is calculated. The client with the highest value is selected to insert into the best place. This process continues until all removed clients insert into the solution. 4. Computational Experience A series of computational experiments were designed and used to evaluate the characteristics and performance of the RFMS. The real network of Zanjan city was used for the computational test. This city is located in the center of Iran, and its graph model of the road network includes 1869 links and 1235 nodes. Network links are divided into three categories: arterial, collector, and local roads. Road function coefficient (a) is assumed to avoid the fleet through the collector and local roads. (See 3.1) A program has been written in the Python environment using the Google Maps API to receive real-time travel time. This program updates the travel time of arterial roads in 5-minute intervals. The designed experiment consists of two scenarios that differ in the width of the service time window. In the first scenario, a wide time window with 4 hours interval is selected for service. In the second scenario, the time window is narrow and has a time interval of 1 hour. Both scenarios involve a depot that serves 100 clients by a homogeneous fleet (with the same capacity and physical and dynamic characteristics). Client status and specifications (including demand, service time, and schedule) are randomly assigned. Ten different replication were designed for each scenario to ensure the randomness of the experiment. In each replication, depot position and client properties were randomly determined. Each replication was run on different days to take into account other traffic situations. (The network graph and client position in one of the replications are shown in Figure 2) Figure 2. The network graph and client position in one of the replications 70 Three methods simulated the designed experiments, and the results were compared. These methods include: 1Without using the real-time fleet management system (static VRP). 2Using the real-time fleet management system without re-optimizing (RFMS without re-optimizing). 3Using the real-time fleet management system with re-optimization (RFMS) In the case without using the real-time fleet management system (static VRP), the VRPTW is first optimized using the method described in 3.5; then, the simulation program simulates freight distribution operation in real-time. In the simulation program, the fleet travels to clients and services in real-time based on the predetermined distribution plan. The simulation program receives actual travel time from Google Maps. Thus, in the execution of freight distribution without using the real-time fleet management system (static VRP), the routes and schedules optimize before the start of distribution operation using historical traffic data. And distribution operations are performed based on real-time road data. In the case, using the real-time fleet management system without re-optimizing (RFMS without re-optimizing), the freight distribution process is performed based on RFMS (see in figure 1) without the rerouting and rescheduling module. At first, routes and schedules are optimized. While simulating the fleet service in real-time during the distribution operation, only the shortest path between clients is calculated. The client sequence (route) is the same predetermined route and does not change. Thus, in this case, routes and schedules are optimized once at first using historical traffic data. And distribution operations are performed based on real-time road data with modifying realtime shortest path. In the case, using the real-time fleet management system with re-optimization (RFMS), the freight distribution process is performed based on RFMS (see in figure 1). At first, the optimal distribution route and program are determined. While simulating the fleet service in real-time during the distribution operation, the rerouting and rescheduling module re-optimizes the distribution plan based on the fleet's position and status and real-time traffic data. Thus, in this case, routes and schedules are optimized before and during the distribution operation using realtime data. Following performance indicators have been used to evaluate RFMS: • Total travel time of fleet • early service time (total time that vehicles wait to be started time window when vehicle arrive at the client before the start of time window) • late service time (total time that vehicles visit the client after end of the time window) 5. Results Table 1 shows the freight distribution simulation results in the first scenario (the wide time window). As mentioned, in the first and second cases, the VRP problem was statically optimized before distributing operations, and the routes were fixed. With the difference that in the second case, the shortest path between clients modifies in real-time. In the third case, the VRP problem is dynamically optimized during freight distribution using real-time data. The results shown in table 1 were obtained from an average of 10 different simulations on different days. In all these simulations, the number of depots was one, and the number of clients was 100, and the number of optimal routes to serve clients was ten routes. The last column of the table shows the results of the average total travel time. As seen in Table 1, the first scenario (Wide Schedule), using RFMS without re-optimization, improves the total travel time by about 5% compared to static VRP. And RFMS with re-optimization has approximately 9% better travel time results than static VRP.