Apurba Saha

I'm currently working as a Software Engineer - Level 3 in the Logistics and Dispatcher team at Chaldal, a startup based in Bangladesh & California, and the biggest online grocery platform in Bangladesh. My primary goal is to achieve full automation of warehouse and routing operations, eliminating the need for manual interventions. The system uses a Distributed architecture with .NET (C#/F#) for backend, React for frontend and Python for algorithm and ML services, all managed on our in-house infrastructure. I am involved in designing and building backend systems, research and development of algorithms to optimize delivery processes and also some frontend development for web and mobile applications. Below I will describe some of the projects that I have worked on.

Overview

When a customer places an order on Chaldal, the order is sent to the Dispatcher and Logistics systems for preparing the order and delivering it to the customer. These two systems as a whole are responsible for the entire delivery process. Dispatcher is responsible for managing the warehouse and assigning tasks to pickers, while Logistics is responsible for assigning routes to delivery persons and ensuring on-time delivery.

The dispatcher system is comprised of the following components:

• Shelves: Shelves contain the products. All the shelves in the warehouse are uniquely numbered and the system keeps track of the products in each shelf.
• Pickers: Pickers are responsible for picking products from the shelves and preparing the order. The system keeps track of all the pickers in the warehouse, including who is available, their last known location, which task they are on, and the estimated time to complete the task.
• Zones: The warehouse is divided into zones. To keep things simple, we are only going to talk about a single zone called the Dispatch Zone, where the orders are kept after all the products of an order are picked.

The logistics system is the most complicated system in the delivery process and is comprised of the following components:

• Shipments: Shipments are the orders that need to be delivered. The system keeps track of the shipments, including the location of the shipments, the time window of the shipments, the weights and volumes of the shipments, etc.
• Delivery Persons: Delivery persons are responsible for delivering the shipments to the customers. The system keeps track of all the delivery persons, including their location, the time when they will be available at the hub.
• Vehicles: We have 3 types of vehicles: cycle, bike, and van. Each types of vehicles has different capacity constraints.

Dispatcher Automatic Task Assignment

• Goal: The goal of this project is to automate the task assignment process for pickers. Before this project, the pickers used to pick tasks manually.
  
• Our Work: We developed an algorithm that takes all the tasks that need to be picked, all the pickers that are online including their location and when they will be free from their current task, and assigns tasks to pickers so that high priority orders get dispatched first and also the picker movement is minimized. The algorithm uses a combination of some greedy heuristics and a Min Cost Max Flow Matching algorithm to solve the assignment problem.
  
• My Contribution: I was responsible for designing the algorithm, implementing it, integrating it with the existing backend system and also the frontend changes in the Picking App that were required to show the tasks to the pickers.
  

Logistics Routing Algorithm

• Goal: The goal of this project is to assign routes of multiple shipments to a delivery person so that the delivery person can deliver all the orders in the same go. In the previous system, the routes were assigned manually by the dispatcher in charge. The manual assignment is effective for low order volumes, but as the order volume increases, the manual assignment becomes inefficient.
  
• Challenge: The main challenge of this project is that the problem is an NP-Hard problem, and the number of possible routes grows exponentially with the number of shipments. The off-the-shelf algorithms like Google OR-Tools and Gurobi Optimizer were not able to handle the problem. Also, some constraints were very specific to our business and could not be modeled using the off-the-shelf algorithms.
  
• Our Work:
  • Algorithm: We developed a new routing algorithm to fully automate the route assignment process. The algorithm takes all the shipments that need to be delivered, the location of the shipments, the time window of the shipments, the weights and volumes of the shipments, the time when each of the delivery persons will be available at the hub, the vehicles that are available, and the vehicle capacity, and outputs a list of routes. A route consists of an ordered list of shipments and the delivery person who will deliver the shipments. The main objective of the algorithm is to deliver the shipments on time and to minimize the total travel time of all the delivery persons. We used Clustering, TSP, Simulated Annealing, Tabu Search, and various neighbor-generating heuristics to achieve this.
    
  • Backend: The backend system is responsible for calling the algorithm, tracking the shipment states, such as whether it's routed or not, and the estimated delivery time if it's routed, etc. It also tracks the delivery person states, like their location and the time when they will be available at the hub. The backend system keeps track of the routes assigned to the delivery persons and the shipments assigned to the routes. It updates the states of the shipments, delivery persons, and vehicles as the delivery persons deliver the shipments.
    
• My Contribution: I was responsible for leading the project, designing the algorithm, implementing it, and integrating it with the existing backend system.
• Demonstration: Here is a simplified demonstration of the algorithm. All the things shown here are dummy data. The images are from a simulation program that we developed to test and visualize the algorithm results, and also to simulate a total warehouse environment.

  

  

  

  

  
  In the Fig 1, there are 10 shipments shown in black and the warehouse/hub shown in blue. There are 3 vehicles available: a cycle, a bike, and a van. The corresponding routes for the vehicles are shown in the next 3 images. The colors in the shipments represent whether the shipment is on time or not. Shipments colored in yellow are early, shipments colored in green are on time, and shipments colored in red are late.

ASAP Delivery

• Goal: In regular Chaldal orders, the customers are shown some fixed delivery time windows, e.g., (8 am - 10 am, 4 pm - 6 pm) for placing orders. These windows are usually at least 1 hour away from the order placing time and it typically takes 2-3 hours to deliver. The goal of ASAP Deliveries is to offer special quick delivery option to customers where they will get the best delivery time window 20 minutes / 40 minutes away from order placement time. ASAP deliveries can be supported in two cases:
  1. We have enough time to spare on an existing route that a new order can be fit into it without making the rest of the deliveries late.
  2. We have a free driver who can go and deliver the order.
• Our Work: For supporting both cases, in our model, we introduce a concept called ASAPSocket. ASAPSockets are calculated for every route leg (a route leg is a segment of a route with fixed start and end locations; these locations are either hub address or shipment address). The ASAPSocket class contains:
  • Slack time: The maximum time that can be spared for delivering an ASAP order within this route leg without making the next shipments late.
  • Slack capacity: The maximum weight and volume capacity the ASAP shipment can have without overloading the route vehicle.
  • Areas: Polygons representing locations on the map where an ASAP order can be placed for this route leg.
  • Delivery time: Estimated delivery time of an ASAP order placed within this route leg if the customer address is inside the calculated areas.
  Along with ASAPSockets for route legs, we also calculate ASAPSockets for free drivers. These sockets consist of the areas around the hub where a driver can deliver an ASAP order after completing one route and before starting another.
• My Contribution: I led the logistics (algorithms and backend) aspect of the project.
• Demonstration: Here is a demonstration of the ASAPSockets for the previous route legs and free drivers.

  

  

  

  

  
  Different ASAP Socket colors represent different route legs. In Fig 6, there's no ASAP Socket for the bike route because it already has a late shipment. In Fig 8, the ASAP Socket for the free bike driver is shown.

Others

• Traffic Estimation: We use the open-source routing engine Valhalla for estimating the travel distance and time between different locations. Valhalla is built on top of OpenStreetMap data. To get accurate travel time estimates, we need to input road speeds at 5-minute intervals for each day of the week and for each road segment. To collect this data, we had a team who manually collected the data from Google Maps for each road segment. On top of that, we polled the Google Maps API for the traffic data for important road segments. Using this data, we interpolated the road speeds for each 5-minute interval for each road segment. This data is then fed to the Valhalla routing engine to get the travel time estimates.
• Dispatcher Task Duration Estimation: Trained a Machine Learning model that takes different features of a task, such as the type of task, the number of products, the weights of the products, etc., and predicts the duration of the task so that the algorithm and the picker incentive system can use it. The model is trained on the historical data of the tasks that were completed in the warehouse.
• Dispatcher Picker Incentive System: Developed an algorithm that takes the performance of the pickers, the predicted duration of all the tasks in a day, and the predicted duration of the tasks that the picker completed in that day, and assigns a score to each picker. The incentive system uses the score to give incentives to the pickers.
• Audit Tasks: Developed a new type of task called Audit Task that is assigned to pickers to audit a shelf in the warehouse. The picker has to go to the shelf, input the products on the shelf, and the system will compare the inputted products with the products that are supposed to be on the shelf. This is used to keep track of the products in the warehouse and to find any discrepancies.

A New Approach to Parameterized String Matching with Fixed Mismatch Tolerance

Undergraduate thesis work

Co-authors: Iftekhar Hakim Kaowsar, Mahdi Hasnat Siyam, Dr. M. Sohel Rahman (Supervisor)

String matching, Data structure, FFT

In this work, we drew an efficient solution to find matching locations between parameterized text and pattern with fixed mismatch tolerance. Two solutions have been introduced:

For the first one, we solved it by using Segment Tree data structure, hashing and some insightful observations for transformation of string. For the later, we improved previously known matching solution by incorporating Fast Fourier Transform (FFT) and Minimum cost bipartite matching. Our solution is also parallelizable on multi-core machine and does not depend on value of tolerance.