Resources
Article

How to get started: Last Mile Delivery Problem

Quantagonia macht alte Software fit für Quantencomputer. Würde Frank Thelen investieren?

Jul 9, 2024
5
min read
Read full article

Hands-On: Mixed Integer Linear Programming for Last-Mile Delivery

Among others, pharmaceutical last-mile delivery involves medication delivery and medical equipment transport from a distribution center to pharmacies, clinics, medical centers, and more. Drug delivery systems must be highly reliable, efficient, and responsive to sudden changes in demand during emergencies and accidents.

What if the fastest way you could receive emergency care was through the sky?

Like the drone medical delivery of an AED that delivered the first shocks to a man who suffered cardiac arrest while scraping snow in Sweden - before ambulance personnel arrived1. Or drone-powered blood unit distribution in large cities and rural areas2. The point is that providing rapid access to life-saving equipment avoids harm in emergencies.

How does Mixed Integer Linear Programming help with distribution?

In essence, we want to solve a Capacitated Vehicle Routing Problem from the Operations Research field. Which is the optimization of the payload for each vehicle, ensuring that the most critical payloads are prioritized and determining the optimal routes for drones to minimize lead time. The goal is to maximize care by mixing two known Integer Programming problems:

  • Load Capacity (Knapsack Problem)
  • Time Urgency (Traveling Salesman Problem)

In combination, the algorithm selects payload and addresses delivery sequencing within a MILP Problem, a.k.a. the Capacitated Vehicle Routing Problem.

Ultimately, this tutorial helps logistics professionals, analysts and business consultants understand how to use Quantagonia’s Hybrid Solver to calculate these mathematical problems.

How to Implement Mixed Integer Linear Programming in Python

Setting up an Optimization Problem in Python is a straightforward process.

  1. Define Problem Parameters (e.g. Delivery locations)
  2. Define Objective Function (e.g. Minimize total distance)
  3. Define Constraint Functions (e.g. Vehicle capacity)
  4. Optimize Model
  5. Process the Results

This structure ensures clarity, making it easier to understand and modify the code later on.

Code Implementation: Optimizing Drone Deliveries for Munich

By way of example, we generate random locations within Munich. Each drone has an item-carry limit of three, with each location needing one. The goal is to administer all drone deliveries as fast as possible (minimize cost, which is distance in this case). If a drone has supplied its three items, it has to restock at the warehouse.

From there, we can formulate the constraints:

  • meet the demands of every location
  • do not exceed the capacity of a drone
  • don’t allow double visits within a tour
  • ensure the elimination of sub-tours

We then pass the Model to the HybridSolver API and solve for the most efficient routes.

The solution groups similar locations into a single trip. However, the routing can become increasingly more complex once you introduce multiple drones, variable payloads, and different warehouses. Try it out yourself. Here is the code implementation of the Tutorial.

Application of Knapsack and Traveling Salesman Problems

The combination of the Knapsack Problem and the Traveling Salesman Problem applies to Last-Mile Delivery and the Logistics Industry. The s.c. Capacitated Vehicle Routing Problems require solving multi-stop routes with limited transport capacity. Here are exemplary use cases for higher satisfaction while using fewer resources:

Ride-Sharing, Car Sharing & Carpooling

Optimal Routing for Ride-Sharing services can improve their services by using CVRP optimization to match drivers with multiple passengers efficiently. By determining the optimal sequence of pick-ups and drop-offs while considering vehicle capacity, ride-sharing services can reduce wait times, improve fuel efficiency, and enhance user satisfaction.

Field Service Management, Paramedics & Firefighters

Companies that provide field services, such as maintenance or repairs, and first responders benefit from optimized planning to improve emergency coverage with optimized routing and schedules. CVRP optimization ensures they can attend to more service calls, reduce response time, and enhance customer success.

Lean Logistics

Streamlined warehouse management for online stores and logistics companies can solve the Knapsack problem to load delivery vehicles optimally, and TSP finds the best routes from the fulfillment center. Companies can reduce costs, improve delivery speeds, and address large volumes effectively by applying insight from CVRP optimization.

Public Transport Scheduling

Public transportation systems can utilize CVRP optimization techniques to schedule buses and trains more efficiently, reducing wait times and improving service reliability.

Warehouse Management

In automated warehouses, robots can pick and place items with optimized paths and load balancing. By applying CVRP optimization, warehouse operations are more efficient, reducing time and energy consumption in inventory management.

You can simulate many of the use-cases above by customizing using the outline given within the Colab Notebook. We are happy to coach you through model formulation for your application help@quantagonia.com. Solve last-mile delivery with efficiency and resilience against emergencies with HybridSolver.

References

1 https://www.nejm.org/doi/10.1056/NEJMc2200833

2 https://www.thelancet.com/journals/langlo/article/PIIS2214-109X(22)00048-1/fulltext

Quantagonia Application Logo

Want to get entangled or stay up to date?

Let's push the boundaries of technology and create a quantum-powered future.