25 November 2021
Hiroshi Uchigaito
Research & Development Group, Hitachi, Ltd
The convenience of online shopping based on stable supply chains has become something we take for granted in our daily lives, and its importance has only grown with the role it played in ensuring people received necessary goods in a timely manner, serving populations in remote areas as well those whose mobility may be restricted for a variety of reasons, including the current outbreak of COVID-19. Ensuring the efficient delivery of items in minimum time, i.e., minimizing customer waiting time from order to delivery, is central to ensuring the reliability of this “convenience.” My colleagues and I looked at how we could use tour division and dynamic route optimization, which takes into consideration the dynamic changes in traffic and order conditions, to minimize customer waiting time. This is particularly pertinent to same day deliveries.
Currently available services such as Uber Eats or Amazon Prime Now would largely benefit from a dynamic delivery route planning algorithm which directly minimizes customer waiting time. However, many of the currently available dynamic vehicle routing methods work to reduce overall tour length (distance) and do not directly address minimizing customer waiting. Further, they cannot handle multiple stochastic events such as traffic jams and order updates simultaneously. To solve the problems, my colleagues and I devised a new delivery-tour planning algorithm which minimizes the customer waiting time by a division of the delivery-service area into a set of routes of equal length and incorporates dynamic tour adjustments to account for stochastic events such as order cancellations and traffic jams.
Our proposed delivery-tour planning algorithm executes two processes: division of the delivery-service area and dynamic route optimization.
1. Division of the delivery-service area
The delivery-service area is modeled by a graph with vertices and edges, which represent potential customer locations and the road network, respectively, as can be seen from Figure 1. The proposed algorithm divides the area into a set of delivery routes of equal length. In the example below, there are four routes. The number of routes is optimized so that the customer waiting time is minimized according to the size of the area. In the delivery service, first, goods ordered by customers are loaded into a delivery vehicle at a depot. The goods are then delivered to the customers on each route in the order of A, B, C, D. After delivery on each route, the vehicle returns to the depot and is loaded with newly ordered goods. By this division, the vehicle returns to the depot with higher frequency. This shortens the customer waiting time by reducing time intervals between loading the good into the vehicle and its delivery.
Figure 1. Example of the area division into four routes
2. Dynamic route optimization
The proposed algorithm dynamically optimizes the route during delivery by addressing stochastic events: order cancellations and traffic jams. As shown in Figure 2, when customer B canceled the order during delivery, the proposed algorithm updates the delivery route by adding customer D between customer A and customer C (customer D can be visited with a slight detour from the existing route). Additionally, when traffic jams occur during delivery, the delivery route is dynamically updated to avoid the traffic jams.
Figure 2. Dynamic route optimization after order cancellation
The average customer waiting time in the case of the proposed algorithm was compared with that in the case of the Lin-Kernighan heuristic (LKH), which is the state-of-the-art solver for the traveling salesman problem. The result is shown in Figure 3 “Number of vertices” on the horizontal axis corresponds to the number of customers in the delivery-service area (in other words, the size of the area). As shown in Figure 3, by applying the proposed algorithm, the average customer waiting time is reduced by roughly 30% not depending on the size of the delivery-service area.
Figure 3. Average waiting time of LKH vs the proposed algorithm for varying number of vertices
We devised a new delivery-tour planning algorithm that minimizes the customer waiting time both by the division of the delivery-service area and by dynamic tour adjustments to address stochastic events such as order cancellations and traffic jams. Our aim is to apply this technology to new delivery services for improving customer satisfaction.
This work was presented at the 2020 International Symposium on Nonlinear Theory and Its Applications (NOLTA2020) on 18th November 2020 [1].
