Two-echelon time-dependent vehicle routing problem with simultaneous pickup and delivery and satellite synchronization
This study develops a model for a a two-echelon time-dependent vehicle routing problem considering simultaneous pickup and delivery and satellite synchronization with customers from multiple regions to enhance vehicles’ utilization and save transportation costs.
Introduction
Traffic conditions vary throughout the day, and congestion has become a daily phenomenon. In 2018, 61 % of cities in China were in a slow state during peak hours, and 13 % of cities had obvious congestion (Gaode Map, 2018). In the USA, the average commuter wasted nearly seven full working days in extra traffic delays in 2017. The congestion cost is projected to grow from USD 166 billion in 2017 to USD 200 billion in 2025 (Schrank et al., 2019). Traffic congestion leads to the uncertainty of driving time and increases the time and cost of the whole logistics process, reducing the efficiency of the logistics chain.
Traffic congestion leads to the uncertainty of driving time and increases the time and cost of the whole logistics process, reducing the efficiency of the logistics chain.
Multi-echelon systems are common in express delivery, multi-modal freight transportation, and home delivery services (Sluijk et al., 2023). Such systems can be turned into cost-effective city logistic systems underlying freight management and routing planning in an integrated way. For example, JD.com is China’s largest online retailer and overall retailer, which holds 8 large-scale logistics hubs and more than 1,400 warehouses in China so that 90 % of orders can be delivered within 24 h via a multi-echelon transportation network (JD Logistics, 2022). The European Commission supports an urban e-mobility project called FREVUE. A delivery pattern of its Distripolis case is an instance of a two-echelon transportation network. If the weight of cargo is less than 200 kg, they will be transported to the urban bases at first and electric vehicles (EVs) are used to complete the final delivery.
Delivery process of both systems
The vehicle routing problem (VRP) is extended to consider multiple echelons and various vehicles. Multi-echelon VRP has wide applications, including in urban logistics, where oversize vehicles are not allowed to travel on designated routes during peak hours in many cities. In direct shipping, vehicles with load start from a depot directly to customers, while in multi-echelon VRP, the freight is delivered from depots to customers through intermediate centers, called satellites. Simultaneous pickup and delivery activities at any customer nodes by the same vehicles may enhance vehicles’ utilization and save transportation costs. In a multi-echelon VRP, the direct and opposite flow of freights from depots to customers is not permitted. Instead, depots, satellites, and customers are organized in multi-echelon and only the transportation of freights among entities in the same echelon is allowed. In such a system, freights are shipped from depots/customers to satellites, where the splitting and consolidation take place. At satellites, splitting is performed to break large shipments from large vehicles into small shipments for ease of delivery, in appropriate vehicles to a variety of destinations. Freights are also consolidated and organized at satellites, picked up by large vehicles to their depots.
Purpose of the study
Motivated by the phenomenon of traffic conditions, this study considers the impact of multi-echelon transportation operations on cost-savings. A new variant of VRP, namely, the two-echelon time-dependent vehicle routing problem with simultaneous pickup and delivery and satellite synchronization (2E-TDVRPSPDSS) is introduced, considering several customer regions with different traffic conditions. Time-dependent travel speed/time function and synchronization of satellites are discussed. The problem originates from urban express logistics practice, such as, JD Logistics and SF Express. Demands are delivered to customers during their time windows by two-echelon multi-region distribution networks considering traffic congestions. Vehicles can also perform pickup services in the backhaul and satellite synchronization ensures a balance of inbound and outbound flows at satellites.
Methodology
The multi-echelon distribution strategy has been widely applied in city logistics systems. This study develops a mixed-integer linear programming model for a new variant of vehicle routing problem, namely, a two-echelon time-dependent vehicle routing problem with simultaneous pickup and delivery and satellite synchronization, in which customers are divided into multiple customer regions according to different geographical characteristics. The pickup and delivery activities with hard time windows are performed simultaneously by the same vehicles from depots to satellites in the first echelon and from satellites to customers in different customer regions in the second echelon. A vehicle speed function is developed for each echelon based on traffic conditions. The function depends on commuter traffic and urbanization level. Satellites with storage buffer capacities for split and consolidation are allowed. Thus, demand unloading, storage, and reloading are synchronized. Costs of transportation, loading/unloading, inventory, and environment during one complete distribution process are considered.
Applications and beneficiaries
(1) Transport Coordinator: A new variant of VRP named 2E-TDVRPSPDSS is introduced, where pickup and delivery activities with hard time windows are performed simultaneously.
(2) Schedule Manager: Travel speed/time functions of vehicles are proposed where customers are divided into multiple regions with different traffic conditions.
(3) Distribution Planner: Satellites with storage buffer capacities for split and consolidation are allowed. Thus, demand unloading, storage, and reloading are synchronized.
(4) Cost Control Center: A mixed-integer linear programming (MILP) is developed to determine routes and departure time at nodes of vehicles with minimum cost.
(5) Researchers: A MA is proposed where three-phase construction heuristic, self-adaptive crossover, mutation, and local search operators are designed.
Reference to the research
Guanghui Zhou, Dengyuhui Li, Junsong Bian, Yixiang Zhang. (2024) Two-echelon time-dependent vehicle routing problem with simultaneous pickup and delivery and satellite synchronization. Computers & Operations Research, Volume 167, 106600.
