One of the classical problems in Transportation (parcel delivery, bus routing & scheduling, waste collection etc.) deals with identifying the set and sequence of tasks to be assigned to a driver to perform on their delivery route. Depending on the type of service, the planner might choose one among the many possible ways to plan and schedule these routes.
- A postal service might decide to zone their delivery areas based on the density of population (or household) and assign each zone to a specific person. However, under such a policy, when there are days with fewer than planned number of deliveries this may lead to underutilization of the delivery resource. On the positive side, the courier gets to ply familiar routes and the customer enjoys a pretty reliable delivery schedule.
- A bus service might be given a route by the regulator with the target of ensuring a steady arrival rate and they may deploy sufficient buses to achieve those targets. However, arrival rates will be affected by traffic conditions and the bus occupancy may suffer (over or underutilized) depending on the time of day.
- A garbage collection service might decide to deploy trucks on a regular route to collect refuse. However, if there are days with more garbage than normal, dynamically the planner needs to deploy additional trips to ensure collection can be fulfilled within the day, etc.
Examples of Vehicle Routing Applications in Practice
This is a prevalent planning problem in the industry and appropriately, this has led to much interest from the research community in finding efficient solutions. However, finding a solution to this problem is non-trivial and even the simpler form of the routing problem, known as the Traveling Salesman Problem (TSP), is already a well-known computational challenge. Simply put, given a number of destinations, the TSP is the shortest tour that visits all the destinations. Though many researchers have tackled the TSP and come up with clever ways to solve it at scale, the problem statement itself misses some of the actual challenges faced by transportation planners. Such as:
- Planning Multiple vehicles at a time
- Capacity Limits of vehicles
- Travel time (which is affected by traffic conditions) besides the distance.
- Service time at each destination.
- Promised Time windows for delivery, etc.
A particular variant of the TSP that deals with planning multiple vehicle trips to optimize operations is popularly known as the Vehicle Routing Problem (VRP) and transportation planners deal with this operational issue on a daily basis. When delivery time windows need to be catered to, then the problem is termed VRP with Time Windows or VRPTW.
Let’s, for instance, observe a case of parcel delivery operations. With the explosion of online shopping and expectation of door-step delivery, numerous companies have sprung up to provide the fulfilment service. Often, platforms offer a choice of delivery time window to a customer for a small fee and when a customer chooses this paid service, they have high expectation of the service standards. The onus on delivery standards, eventually, falls on the delivery service provider who is expected to manage the complex delivery operations while meeting the customer time windows.
Choosing Delivery Time windows is a common feature in many e-commerce platforms
Competition among the delivery service providers is intense and to remain competitive in the marketplace, the operators work on very thin margins. Hence, to be profitable in their business, the delivery companies rely heavily on reducing their operating costs by optimizing their operations, which includes maximizing the utilization of the delivery vehicle, minimizing wasted travel in their delivery routing, maximizing the on-time deliveries of parcels (and hence avoid missed deliveries), etc.
Given the prevalence of the VRPTW in transport operations and the challenge in solving it at scale, this problem also has had much attention from the research community, Software Solutions and Case Studies that showcase methods and technologies that prove useful in practice. Ironically though, even if the optimal solution can be found, they tend to perform poorly during execution. This is because when dealing with delivery time windows, any delays in the system might lead to failed deliveries. Delays happen when the plans are optimistic and do not cater in the prediction and estimation errors in travel and service times at each destination. It is easy to see that such errors are natural and can occur from many sources, such as weather conditions, traffic situation, service delays etc. As this uncertainty adds another layer of complexity to this class of problems, how does one strategize the delivery operations while mitigating the risk of delayed deliveries?
This is the precise focus of a research study in by Zhang et. al. in their paper “Robust Data-Driven Vehicle Routing with Time Windows”. At the crux, the authors observe that the risk of delivery delays is closely related to the level of uncertainty in the time estimation and propose the construction of the Service Fulfillment Risk Index (SRI) and find an optimal routing that minimizes the SRI. As it turns out, the SRI can be used as a decision lever for the planner to control the service levels guarantees for orders.
The authors also showcase an implementable heuristic that incorporates the SRI. Their numerical analysis suggests that when there is uncertainty in the information, their proposed solution can perform better in practice than an optimal solution that ignores this uncertainty.
Overall, VRPTW faces critical issues and inefficiencies. The authors’ promising approach to mitigate delivery delays by introducing the SRI outperforms traditional methods in handling uncertainty, highlighting the ongoing need for efficient transportation optimization strategies.
