The Challenge

Every morning, field service companies face the same puzzle: they have multiple vehicles, dozens of jobs scattered across the city, and every customer has specific time windows when they're available. Some jobs require picking up items before delivering them elsewhere. Drivers have limited hours. Vehicles have capacity constraints.

Planning these routes manually takes hours and rarely produces optimal results. Dispatchers rely on intuition and experience, but they can't calculate hundreds of possible route combinations in their heads. The result? Drivers spend extra time on the road, fuel costs run higher than necessary, and some customers get served late.

The Problem

This is a classic Vehicle Routing Problem with Pickup-Delivery and Time Windows (VRPPDTW). In mathematical terms, it's an NP-hard problem, meaning there's no quick way to find the perfect solution. As you add more stops and vehicles, the number of possible combinations grows exponentially.

For a field service company with 4 vehicles and 20 daily jobs, there are millions of possible ways to assign those jobs and arrange the routes. Finding the best one manually is impossible.

The Solution

We developed a route optimization system using Google's OR-Tools constraint programming library. The system automatically calculates optimal routes that minimize total distance traveled while respecting all real-world constraints.

How It Works

The optimization algorithm considers multiple factors simultaneously:

Distance and Time: The system calculates actual driving distances between all locations using the Haversine formula for geographic coordinates. It accounts for both travel time and service time at each stop.

Vehicle Constraints: Each vehicle has maximum distance and time limits. The algorithm ensures no vehicle exceeds its 8-hour workday or maximum range.

Pickup and Delivery Pairing: When a job requires picking up items at one location and delivering to another, the algorithm ensures the same vehicle handles both stops, and pickup always happens before delivery.

Time Windows: Customer availability windows are strictly enforced. The algorithm only assigns routes that can meet all scheduled appointments.

Depot Starting Point: All vehicles start and end at the same depot location, ensuring they're back at the base by end of day.

The Algorithm

The system uses a heuristic approach called "Parallel Cheapest Insertion" to build initial routes, then refines them through constraint programming. Here's what happens:

First, it builds a distance matrix showing travel times between every pair of locations. Then it begins assigning stops to vehicles, always choosing the insertion point that adds the least additional distance. As it builds routes, it continuously checks all constraints: time windows, vehicle capacity, pickup-delivery pairing, and maximum route duration.

The algorithm intelligently handles edge cases. For example, if calculated service times seem unreasonably long, it caps them at one-third of the total available time to avoid distorting the optimization.

Real-World Example

Imagine a field service company with 4 vehicles and 12 customer locations spread across the city. Without optimization, dispatchers might assign 3 jobs to each vehicle based on geographic proximity alone. But this ignores time windows, pickup-delivery requirements, and actual road distances.

The optimization system analyzes all possible combinations and produces routes that:

  • Minimize the longest route (balanced workload across drivers)
  • Respect all customer time windows
  • Pair pickups with their deliveries on the same vehicle
  • Keep all routes under 4 hours of total time
  • Start and end at the depot

The result: drivers spend less time on the road, fuel costs drop, and customers get reliable service within their requested time windows.

Technical Implementation

The system is implemented as a microservice in Python, deployed on AWS infrastructure to integrate with existing logistics management software. It accepts job data in JSON format, runs the optimization, and returns complete route assignments for each vehicle.

Input data includes customer locations (latitude/longitude), service duration at each stop, vehicle fleet size, depot location, average vehicle speed, maximum distance and time per vehicle, and pickup-delivery pairs that must be handled together.

The output provides each vehicle's complete route as an ordered list of stops, along with total distance for each route and overall fleet distance.

Benefits

Time savings: Route planning that took dispatchers 1-2 hours every morning now happens in seconds.

Cost reduction: Optimized routes typically reduce total driving distance by 15-25% compared to manual planning, directly cutting fuel costs.

Better customer service: Reliable arrival times and fewer missed time windows improve customer satisfaction.

Balanced workload: The algorithm distributes work evenly across drivers, preventing some from being overloaded while others have light days.

Scalability: The system handles growing fleets and increasing job volumes without requiring additional dispatch staff.

Applications

This optimization system works for any field service operation with multiple vehicles and distributed stops:

  • Furniture and appliance delivery services
  • HVAC repair and maintenance companies
  • Plumbing and electrical contractors
  • Medical equipment delivery and pickup
  • Field sales teams with daily appointment routes
  • Last-mile delivery services

Any business that asks "which driver should go where, and in what order?" can benefit from automated route optimization.