Engineering a ETA Engine for Multi-Door Deliveries
Engineering a ETA Engine for Multi-Door Deliveries
Engineering a ETA Engine for Multi-Door Deliveries
tl;dr:
A pragmatic approach to route planning using Classifiers and EA Optimizers.
Identifying the Customer Pain Points
One of the common pain-points in the package delivery experience lies with unpredictable delivery times. Customers are left in the dark, unsure whether they should stay home to receive the package or risk missing the delivery.
The current practice is to provide a broad delivery window which is the entire day of delivery. While this guards against failing to meet specific timeframes, it leaves on the table a chance to elevate customer satisfaction and potential market differentiator for the business.
The model we designed is two-staged. Firstly, we constructed a Server-Side Door-to-Door Predictive Engine. This is a supervised model trained on historic delivery times. Secondly, we constructed a Client-Side Route Sequence Optimizer. This tool is completely independent of internet connectivity and leverages the output of the Door-to-Door Predictive Engine to generate an optimal route sequence for the driver.
Operational Considerations
Estimating delivery ETAs is complex. For this problem, it's not just about calculating distances and times; there were many other dynamic factors at play…
Some examples:
Drivers often adopt multi-modal transport strategies, especially in high-density areas with limited parking. They might park their vehicle and deliver a bunch of packages on foot, which can be faster than driving to each door.
A single driver account can have multiple agents. For example, a family might split up delivery routes to get the job done quicker.
Data connectivity can be spotty, depending on the delivery location and the driver's personal mobile data plan.
With all these complexities in mind, we designed a solution to support, not replace, the driver's wisdom. We aimed for "good enough" predictions that support route planning without the need for access to the internet. Finally, we had to integrate thesolution subtly into the existing driver app UI to ensure a simple transition.
Dataset and Cleaning Process
Our dataset consisted of delivery logs for all drivers in Singapore over a three-month period. Although the data was not perfect, it was a good starting point. We had to process the data methodically to make it useful for our purpose. This involved grouping the data by driver, sorting it by date and time, and pruning the records where time differences followed certain patterns.
We also cross-referenced the delivery data with driver ratings to assign a weight to each pair-wise door-to-door time. This weightage helped us to account for the variability in driver performance and efficiency. The final dataset was a series of pair-wise destinations, each associated with a day, hour, and a weighted-average door-to-door time. This cleaned, processed data formed the core dataset for our model.
Building the Model
The model we designed is two-staged.
Firstly, we constructed a Server-Side Door-to-Door Predictive Engine. This machine learning model makes use of various features such as pick-up location, drop-off location, and delivery time to estimate door-to-door delivery times. It operates by utilizing a classification approach. Rather than predicting delivery times as a continuous variable, we broke them down into 5-minute intervals. This technique, often termed 'time discretization', not only simplifies the problem, but it also leads to higher prediction accuracy by accounting for real-world uncertainties and fluctuations in travel times.
To train this model, we leveraged supervised learning techniques, employing a suitable classification algorithm. The model then outputs the probable duration class for the travel time from one door to another. We have designed this component to push updates to the client-side application periodically whenever an internet connection is available.
Secondly, we constructed a Client-Side Route Sequence Optimizer. This tool is completely independent of internet connectivity and leverages the output of the Door-to-Door Predictive Engine to generate an optimal route sequence for the driver.
As this is fundamentally a Travelling Salesman Problem (TSP), a classic NP-hard problem, an exact solution is often infeasible for large numbers of deliveries due to time and computational constraints. Therefore, we resorted to heuristic and approximation techniques that find good solutions within a reasonable time.
In our implementation, we used Genetic Algorithms (GA). GAs are a subset of a larger set of Evolutionary Algorithms, which generate solutions to optimisation problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover. The choice of GA was guided by its proven efficiency in large combinatorial spaces and ability for for multi-objective optimisation, such as minimisation of petrol or fastest completion.
It's worth noting that other heuristic techniques like Simulated Annealing or Ant Colony Optimization could have been employed. We might explore these avenues in future iterations with the goal on minimizing computational cost, since this would be done on a local mobile device.
Deployment and Validation
Finally, the solution UX was implemented as a incremental change to the existing driver app screen. The emphasis was on minimising cognitive load for the drivers while introducing these new tools. To accomplish this, we incorporated new UI blocks into the existing design, making use of existing screen space and design elements to subtly guide the user's attention to the added functionalities, ensuring that the new features felt like a natural extension of the existing interface rather than an abrupt addition.
Empowering delivery agents by giving them a more effective and efficient means to plan their routes should, theoretically, produce a win-win outcome for both agents and customers. To gauge the success of this initiative, key metrics such as the (1) Net Promoter Score from clients and the (2) churn rates of our delivery agents. This can be assessed against a control group to ensure the validity of the results.
Final Thoughts
All this happened over a 48-hour hackathon. The strength of the project lies in how it selectively mixed ML solutions with other classic AI approaches to a complex, real-world problem with an arguably respectable output.
We allowed ourselves to invest time up-front to problem-seeking and definition, leading to an enjoyable sprint of code slinging. In future iterations, the project could benefit from expanding upon the data cleaning process and exploring the use of different ML techniques such as neural networks.
Well, that’s it for now! Thanks for reading this far.
postscript: Our solution received the “Most Technical” award. Pizzas were roundly shared. Laptops were won and gainful opportunities extended. Overall, a win for everyone involved!
Identifying the Customer Pain Points
One of the common pain-points in the package delivery experience lies with unpredictable delivery times. Customers are left in the dark, unsure whether they should stay home to receive the package or risk missing the delivery.
The current practice is to provide a broad delivery window which is the entire day of delivery. While this guards against failing to meet specific timeframes, it leaves on the table a chance to elevate customer satisfaction and potential market differentiator for the business.
The model we designed is two-staged. Firstly, we constructed a Server-Side Door-to-Door Predictive Engine. This is a supervised model trained on historic delivery times. Secondly, we constructed a Client-Side Route Sequence Optimizer. This tool is completely independent of internet connectivity and leverages the output of the Door-to-Door Predictive Engine to generate an optimal route sequence for the driver.
Operational Considerations
Estimating delivery ETAs is complex. For this problem, it's not just about calculating distances and times; there were many other dynamic factors at play…
Some examples:
Drivers often adopt multi-modal transport strategies, especially in high-density areas with limited parking. They might park their vehicle and deliver a bunch of packages on foot, which can be faster than driving to each door.
A single driver account can have multiple agents. For example, a family might split up delivery routes to get the job done quicker.
Data connectivity can be spotty, depending on the delivery location and the driver's personal mobile data plan.
With all these complexities in mind, we designed a solution to support, not replace, the driver's wisdom. We aimed for "good enough" predictions that support route planning without the need for access to the internet. Finally, we had to integrate thesolution subtly into the existing driver app UI to ensure a simple transition.
Dataset and Cleaning Process
Our dataset consisted of delivery logs for all drivers in Singapore over a three-month period. Although the data was not perfect, it was a good starting point. We had to process the data methodically to make it useful for our purpose. This involved grouping the data by driver, sorting it by date and time, and pruning the records where time differences followed certain patterns.
We also cross-referenced the delivery data with driver ratings to assign a weight to each pair-wise door-to-door time. This weightage helped us to account for the variability in driver performance and efficiency. The final dataset was a series of pair-wise destinations, each associated with a day, hour, and a weighted-average door-to-door time. This cleaned, processed data formed the core dataset for our model.
Building the Model
The model we designed is two-staged.
Firstly, we constructed a Server-Side Door-to-Door Predictive Engine. This machine learning model makes use of various features such as pick-up location, drop-off location, and delivery time to estimate door-to-door delivery times. It operates by utilizing a classification approach. Rather than predicting delivery times as a continuous variable, we broke them down into 5-minute intervals. This technique, often termed 'time discretization', not only simplifies the problem, but it also leads to higher prediction accuracy by accounting for real-world uncertainties and fluctuations in travel times.
To train this model, we leveraged supervised learning techniques, employing a suitable classification algorithm. The model then outputs the probable duration class for the travel time from one door to another. We have designed this component to push updates to the client-side application periodically whenever an internet connection is available.
Secondly, we constructed a Client-Side Route Sequence Optimizer. This tool is completely independent of internet connectivity and leverages the output of the Door-to-Door Predictive Engine to generate an optimal route sequence for the driver.
As this is fundamentally a Travelling Salesman Problem (TSP), a classic NP-hard problem, an exact solution is often infeasible for large numbers of deliveries due to time and computational constraints. Therefore, we resorted to heuristic and approximation techniques that find good solutions within a reasonable time.
In our implementation, we used Genetic Algorithms (GA). GAs are a subset of a larger set of Evolutionary Algorithms, which generate solutions to optimisation problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover. The choice of GA was guided by its proven efficiency in large combinatorial spaces and ability for for multi-objective optimisation, such as minimisation of petrol or fastest completion.
It's worth noting that other heuristic techniques like Simulated Annealing or Ant Colony Optimization could have been employed. We might explore these avenues in future iterations with the goal on minimizing computational cost, since this would be done on a local mobile device.
Deployment and Validation
Finally, the solution UX was implemented as a incremental change to the existing driver app screen. The emphasis was on minimising cognitive load for the drivers while introducing these new tools. To accomplish this, we incorporated new UI blocks into the existing design, making use of existing screen space and design elements to subtly guide the user's attention to the added functionalities, ensuring that the new features felt like a natural extension of the existing interface rather than an abrupt addition.
Empowering delivery agents by giving them a more effective and efficient means to plan their routes should, theoretically, produce a win-win outcome for both agents and customers. To gauge the success of this initiative, key metrics such as the (1) Net Promoter Score from clients and the (2) churn rates of our delivery agents. This can be assessed against a control group to ensure the validity of the results.
Final Thoughts
All this happened over a 48-hour hackathon. The strength of the project lies in how it selectively mixed ML solutions with other classic AI approaches to a complex, real-world problem with an arguably respectable output.
We allowed ourselves to invest time up-front to problem-seeking and definition, leading to an enjoyable sprint of code slinging. In future iterations, the project could benefit from expanding upon the data cleaning process and exploring the use of different ML techniques such as neural networks.
Well, that’s it for now! Thanks for reading this far.
postscript: Our solution received the “Most Technical” award. Pizzas were roundly shared. Laptops were won and gainful opportunities extended. Overall, a win for everyone involved!