Field Service Technician Scheduling Optimization (EDCVRP)

Introduction

In this blog post we demonstrate how we optimized field service technician scheduling for a US telecommunications provider by using a QUBO formulation and running it on the LightSolver platform, benchmarking its performance against the Gurobi solver.

The Equal Demand Capacitated Vehicle Routing Problem (EDCVRP)

The optimal assignment of jobs to field technicians is a challenging optimization task for any service provider with even a modestly large team. For example, there exist more than 10⁹⁴ possibilities of allocating 10 jobs each to a team of 7 field service technicians – a problem size that exceeds the capabilities of current computers.

Mathematically, this challenge can be described as an Equal Demand Capacitated Vehicle Routing Problem (EDCVRP), a variant of the classic Vehicle Routing Problem (VRP) that involves delivering goods or services from a central depot to a set of geographically dispersed locations using a fleet of vehicles, while adhering to equal demand constraints. In the field technician scenario that our client faced, instead of delivering goods, the objective was to efficiently assign field technicians to service various locations or tasks, considering equalized workload distribution. The ultimate goal remained to minimize the total distance within these constraints.

Putting QUBO to work

For this benchmark, we used location data from the telecom provider’s operations in a North American metropolis and conducted calculations for scenarios with up to 20 technicians and up to 10 jobs a day per technician.

Skip the mathematical part and go directly to the results

DEFINITIONS USED:

 

• There is 1 depot
• There are M technicians
• Each technician is assigned N jobs per day
• The total number of customers to be served is K=MN
• All the technicians start and end at the depot
• The traveling distance between two sites i and j is
  C_ij, i,j=0, …, K
  where index 0 refers to the depot

 

We used binary variables x_mnk=1. We set x_mnk=1 if the n^th job of technician m serves customer k. For a solution to be feasible, we mandated that every technician serves exactly one customer at each step. Additionally, we stipulated that each customer is served exactly once.

As the QUBO formulation lacks hard constraints, we adhered to the standard method of incorporating a sufficiently large penalty, controlled by a hyperparameter λ, to account for constraint violations:

 

 

 

As for the objective function itself, the distance between two sites (whether two customers or a customer and the depot) was added to the total distance if they appeared consecutively in the route of a technician. Mathematically, it can be expressed as the following quadratic form:

 

 

 

 

The full QUBO formulation for the problem is the sum of the two terms:

 

 

 

 

Click here to see the full QUBO formulation.

 

The solution

We employed our routing formulation package to formulate the EDCVRP problem as a QUBO problem and resolved it on the LightSolver platform, which accelerates large-scale optimization.

Results and Benchmark

We generated and evaluated 15 instances of EDCVRP, encompassing different numbers of technicians (5, 10, 15, 20) and jobs per day (2, 4, 8, 10) for a maximum of 160 jobs. To mimic real-world, dynamic dispatching scenarios, we constrained runtimes to a maximum of 10 seconds. For each scenario, we recorded the best solution value (minimum total distance) identified by each solver after 0.1, 1, and 10 seconds.

LightSolver generated optimal solutions within fractions of a second, even for instances involving more than 100 jobs to be scheduled. Across all scenarios, it consistently outperformed or matched Gurobi. Notably, in cases with 100 or more jobs to be allocated, Gurobi struggled to identify any feasible solution within the specified time constraints. In the above example for 80 jobs, LightSolver’s solution reduces the total distance traveled by 46%, translating into substantial operational cost savings such as decreased fuel consumption, traveling time, etc.

Conclusion

In today’s fast-paced world, LightSolver helps enterprises seeking a substantial competitive advantage through real-time operational optimization. Beyond the logistics sector, users in manufacturing, aerospace and the finance industry benefit from the accuracy and speed offered by our solver.

Are you ready to put your VRP challenge to the test on our platform and witness our performance firsthand? Reach out to us at info@lightsolver.com for a complimentary benchmark.

Download the full VRP White Paper