Applying Graph Algorithms and Pub/Sub Structure to Cut Last-Mile Delivery Costs by 30%

Project Background and Core Challenges:


In the supply chain of the e-commerce industry, "Last-Mile Delivery" - the process of transporting goods from the inner-city distribution center to the buyer - is always considered the "Achilles heel" of Logistics companies. Although it only takes up a very short distance, this step consumes more than 50% of the total operating costs of the entire chain. This Case Study project analyzes a domestic express delivery group that is falling into a serious operational crisis when the number of orders skyrockets 300% during super sale seasons. Dispatchers are still dividing routes for drivers manually based on personal experience and postal code (Zip code). As a result, routes overlapped (two drivers delivering in the same neighborhood), delivery delays skyrocketed, fuel costs ballooned, and the rate of wasted truck loading space reached alarming levels. Businesses need a major technological surgery to automate the entire dispatch center.


Technical Solution: Solving the VRP problem (Vehicle Routing Problem):


The software architect team recognizes that route arrangement is not simply connecting points A, B, C on the map. It is an extremely complex combinatorial optimization problem called VRP (Vehicle Routing Problem), which comes with a series of strict constraints: Customer's requested delivery time frame (Time Windows), limited load and volume of each type of truck, along with the driver's shift time.


To handle this huge amount of calculation, the traditional relational database system has been upgraded. provided by integrating the Spatial Database management system based on the PostGIS extension of PostgreSQL. All customers' text delivery addresses are standardized (Geocoded) into absolutely accurate Latitude/Longitude coordinates. Instead of using slow for-loops, the Backend system (built with Java Spring Boot to take advantage of multi-threaded processing capabilities) has embedded deep graph algorithm libraries (Graph Algorithms) such as the improved Dijkstra algorithm and Heuristics. In less than 1 minute, thousands of orders waiting to be shipped are automatically grouped by the system and calculate the most optimal travel routes, including turning points and avoiding roads that prohibit loading according to prescribed hours.


Real-time Architecture with Pub/Sub and Redis:


However, the algorithm can only solve the static planning part. Real streets are always fluctuating with unexpected factors: traffic jams due to accidents, heavy rains and flooding, or customers suddenly cancel orders. To create "liveness" for the system, an event-driven architecture is established. The system embeds a Pub/Sub network (Publish/Subscribe) through the Apache Kafka platform. Whenever there is a bad weather event or traffic jam updated from a third-party API, Kafka will immediately issue an alert signal.


This data stream is fed into a super-high-speed In-memory Cache layer using Redis. The routing AI system will immediately read data from Redis, recalculate the route in milliseconds and push the new route coordinates (Re-routing) directly to the driver's mobile application via a WebSockets connection. Meaning, the driver never has to F5 the app or reload the map; The blue road on their phone screen will automatically bend and change direction to avoid traffic jams in real time. All data about travel speed and dwell time (Dwell time) at a delivery point are recorded back into the Data Lake to continue training Machine Learning models to predict delivery times more and more accurately.


Results and Business Value Contribution:


After 4 months of implementing the core system and running tests (A/B Testing) in the 3 largest urban areas, The results obtained overwhelmed the entire board of directors. The average number of kilometers traveled by the vehicle fleet decreased sharply by 28%, leading to a 30% decrease in fuel costs. The ability to optimally cram orders along the route has increased delivery productivity per driver by 40% (from 80 orders to 112 orders/day). Most importantly, the On-time Delivery rate has jumped to 98.5%, completely restoring brand reputation in the eyes of retail partners. This far-reaching digital transformation project demonstrates the power of combining foundational algorithms (Core Computer Science) with modern real-time data transmission architectures, completely changing the fiercely competitive landscape of the Logistics industry.