Optimizing taxi dispatch with Voronoi diagrams

Every empty taxi kilometre is money the dispatcher will never see. The standard approach is raw computing power — check every vehicle, one by one, for every passenger. I wanted to see whether there's a faster, more elegant way — one that comes from geometry, not brute-force code.

January 2026

$ git clone github.com/Rudic21302/VoronojTaxi

Yellow taxi parked side-on in a city street, in front of brick buildings and one-way street signs

The "nearest" vehicle isn't always the "available" one.

Image from Pexels by Artem Velychko

Introduction

A taxi dispatch's economic efficiency depends mostly on one thing — minimizing empty running, the time a vehicle drives without a passenger. The goal of this project is to optimize ride assignment with Voronoi diagrams, so every passenger gets the nearest possible vehicle. The ideal solution would be a so-called "space-time Voronoi diagram" (STVD) that also accounts for real traffic and time — but that's beyond the scope of this work. Here I focus on a simpler, static model that serves as a foundation for further development toward that goal.

Model

For this to work at all, I treat the city as a simplified two-dimensional plane, where proximity is measured with the standard Euclidean distance — as the crow flies. The Voronoi diagram itself rests on these rules: a vehicle's Voronoi cell is simply the intersection of all its individual "wins" over the other vehicles in the system. It's a direct variant of the classic "post office problem" from computational geometry — instead of recalculating the distance to every vehicle for every user, it's enough to know which zone the user is in, which turns slow arithmetic into a fast geometric lookup.

Implementation: approach:

To build the Voronoi diagram I use the "plane-sweep" technique — a sweep-line method that reaches the optimal O(n log n) time complexity, with a DCEL (Doubly Connected Edge List) as the standard structure for storing planar graphs. It's implemented in Python; Python is slower than, say, C++ or Java, but that drawback disappears with NumPy and SciPy for vectorized operations. One detail mattered to me in particular: a fixed seed for the random number generator. The vehicle layout is random, but with a fixed seed every run produces the same layout and zone shapes — so I can verify exactly how the system decides which vehicle to assign, without the noise that always-new random data would add.

These few lines define the whole simulation scenario — city size, number of vehicles, number of passengers, and the seed for the random number generator. By changing only these numbers I can test the system under completely different conditions — from 3 vehicles and a couple of passengers to 24 vehicles and 12 passengers at rush hour — without touching a single line of the logic below.

# Constants
GRID_SIZE = 10
NUM_TAXIS = 24
NUM_CUSTOMERS = 12
SEED = 35

A snippet of the code written for this project.

These two lines start two parallel processes. The Voronoi class (using Fortune's algorithm) splits the city into service zones — that's the visual layer, what gets drawn on the map. The KDTree does something more important from an engineering point of view: it arranges the same coordinates into a structure built for fast, level-by-level search, instead of slowly comparing vehicles "one by one". The result is a system with both a picture for humans and a fast structure for the computer — two views of the same data, each optimized for its own purpose.

# Core Logic
vor = Voronoi(taxi_points)
tree = KDTree(taxi_points)

A snippet of the code written for this project.

Each coloured zone on the map belongs to exactly one vehicle — the borders are calculated so that every point inside a zone is closer to that vehicle than to any other. When a new passenger appears, the system doesn't have to check all 24 vehicles one by one — it only needs to look at which zone the passenger is in, and an arithmetic search becomes a geometric one.

Voronoi zones over a map of Subotica: six customers (red crosses) linked by dashed lines to their assigned nearest vehicles (green circles) — Figure 3.4 — Voronoi service zones over a map of Subotica, the output of a program run.

Instead of searching the vehicle list separately for each passenger, the KD-tree receives the full coordinate matrix of all passengers at once. The result is two arrays — the distance and index of the nearest vehicle for each passenger — computed in a fraction of a second, even with hundreds of simultaneous requests.

# Query - Find nearest taxi for ALL customers
distances, indices = tree.query(customer_points)
nearest_taxis = taxi_points[indices]  # Array of nearest taxi coordinates

A snippet of the code written for this project.

Mathematically, the zones at the city's edge never end — they stretch to infinity. The voronoi_finite_polygons_2d function solves this by calculating where the edge "should" end and closing the shape into a valid polygon. The other half of the problem is that those polygons then stick out far beyond the map — for that I use the Sutherland-Hodgman clipping algorithm, which cuts the polygon along each map edge until only the part that truly belongs to the city remains. The result is a clean, closed mosaic of zones without a single visual glitch.

# --- Helper Functions for Finite Voronoi Regions ---
def voronoi_finite_polygons_2d(vor, radius=None):
    """
    Reconstruct infinite voronoi regions in a 2D diagram to finite
    polygons.
    """
    if vor.points.shape[1] != 2:
        raise ValueError("Requires 2D input")

    new_regions = []
    new_vertices = vor.vertices.tolist()

    center = vor.points.mean(axis=0)
    if radius is None:
        radius = vor.points.ptp().max() * 2

    # Construct a map between point index and all ridges
    # (point index, point index) -> [ridge index, ridge index, ...]
    all_ridges = {}
    for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
        all_ridges.setdefault(p1, []).append((p2, v1, v2))
        all_ridges.setdefault(p2, []).append((p1, v1, v2))

    # Reconstruct infinite regions
    for p1, region_idx in enumerate(vor.point_region):
        vertices = vor.regions[region_idx]

        if all_ridges.get(p1) is None:
            continue

        ridges = all_ridges[p1]
        new_region = [v for v in vertices if v >= 0]

        for p2, v1, v2 in ridges:
            if v2 = 0:
                # finite ridge: already in the region
                continue

            # Compute the missing endpoint of an infinite ridge
            t = vor.points[p2] - vor.points[p1]  # tangent
            t /= np.linalg.norm(t)
            n = np.array([-t[1], t[0]])  # normal

            midpoint = vor.points[[p1, p2]].mean(axis=0)
            direction = np.sign(np.dot(midpoint - center, n)) * n
            far_point = vor.vertices[v2] + direction * radius

            new_region.append(len(new_vertices))
            new_vertices.append(far_point.tolist())

        # Sort vertices counterclockwise
        vs = np.asarray([new_vertices[v] for v in new_region])
        c = vs.mean(axis=0)
        angles = np.arctan2(vs[:,1] - c[1], vs[:,0] - c[0])
        new_region = np.array(new_region)[np.argsort(angles)]
        new_regions.append(new_region.tolist())

    return new_regions, np.asarray(new_vertices)

A snippet of the code written for this project.

The lines connecting passengers to their assigned vehicles never cross into another vehicle's zone — visual proof that the maths behind the system works. For every passenger the program calculates the straight-line distance to two decimal places, in a couple of milliseconds on average. That means the system can handle hundreds of simultaneous requests without any lag.

Conclusion

This work confirms that Voronoi diagrams have a real use as a tool for dividing territory — turning a map into zones of influence makes the data understandable to people, which reduces the dispatcher's cognitive load: instead of reading tables, a decision becomes a glance at the map. The architecture proved to be the right call — separating the visual layer (Voronoi for display) from the computational layer (KD-tree for search) is what lets the system run in real time without delay, even on larger datasets.

Still, this is a solid static foundation, not a finished product. To become a commercially usable tool, the system needs: a queue, dynamic vehicle status updates, a move from straight-line distance to the real road network (generalized network Voronoi diagrams), a time component, and integration with API services such as Google Maps. The path from academic demo to a tool with real business potential is clear — it just hasn't been walked yet.

Dev Log

v1.0 · Jan 2026 Basic Voronoi model + KD-tree for nearest-vehicle search
v1.1 · Jan 2026 Solved the infinite-regions problem (voronoi_finite_polygons_2d)
v1.2 · Jan 2026 Added polygon clipping to the map borders (Sutherland–Hodgman)

Need a developer on your team?

I'm available as a developer — for a permanent role or as extra hands on a project.

Stay in the loop!

New posts, projects and tools — straight to your inbox.