Order-Biker Assignment Algorithms

This project demonstrates and compares two different approaches for solving the order-biker assignment problem in a food delivery system: a greedy algorithm and the Hungarian (Munkres) algorithm.

Overview

The project simulates a real-world scenario where food delivery orders need to be assigned to available delivery bikers in an optimal way. It includes two different implementation strategies:

1. Greedy Algorithm (greedy-assign.py)

   • Assigns each order to the nearest available biker
   • Simple and fast, but may not find the global optimal solution
   • Good for real-time assignments with limited computational resources

2. Hungarian Algorithm (hungarian-assign.py)

   • Uses the Hungarian (Munkres) algorithm to find the globally optimal assignment
   • Minimizes the total distance traveled by all bikers
   • More computationally intensive but guarantees optimal results

Requirements

numpy
scipy

Install dependencies using:

pip install -r requirements.txt

Usage

Run either implementation:

# Run the greedy algorithm implementation
python greedy-assign.py

# Run the Hungarian algorithm implementation
python hungarian-assign.py

Features

• Geographic Distance Calculation: Uses Haversine formula to calculate real-world distances
• Random Data Generation: Creates test scenarios with random orders and biker positions
• Configurable Parameters: Easily modify number of orders and bikers
• Performance Metrics: Shows total distance for comparing algorithm effectiveness

Project Structure

├── README.md
├── requirements.txt
├── greedy-assign.py     # Greedy algorithm implementation
└── hungarian-assign.py  # Hungarian algorithm implementation

Implementation Details

Both implementations share common classes:

• Order: Represents a delivery order with pickup and dropoff locations
• Biker: Represents a delivery biker with current location
• Assignment: Represents an order-biker pairing with distance

The main difference is in the assignment strategy:

• Greedy approach pairs each order with its closest available biker
• Hungarian approach optimizes the total distance across all assignments simultaneously

Sample Output

The simulation outputs:

1. Generated orders and their locations
2. Available bikers and their positions
3. Final assignments with individual distances
4. Total distance for all assignments

Use Cases

This boilerplate is useful for:

• Testing different assignment strategies
• Benchmarking algorithm performance
• Learning about optimization problems
• Building real-world delivery systems

License

MIT License