How Genetic Algorithms Optimize Field Service Dispatch: From VRPTW to Real‑World Gains

1 Introduction

Assume there are 4 field engineers and 24 pending orders . The goal is to allocate orders so that each engineer can serve only one order at a time (no overlapping time windows), total travel time is minimized, and the workload is balanced across engineers.

2 Business Background

In the early stage of luxury‑goods recycling, order dispatch relied entirely on manual planning across more than ten cities. Manual dispatch must consider punctual fulfillment, optimal routes, and balanced order distribution, which leads to low efficiency and local‑optimal solutions.

3 Problem Model

The dispatch problem can be modeled as a Vehicle Routing Problem with Time Windows (VRPTW) . Constraints include:

Time‑window constraint : Engineers must arrive and complete service within the specified time window. Order constraint : An engineer may handle multiple orders, but each order belongs to only one engineer. Start‑end constraint : Engineers start and finish at the depot. Sequence constraint : Orders are served in chronological order.

The objectives are to minimize total travel cost and to balance order distribution among engineers.

4 Algorithm Selection

After defining the model, several algorithmic approaches are evaluated:

Exact Algorithms

Advantages : Exhaustive search yields the theoretical optimum. Disadvantages : Exponential time complexity (NP‑Hard); e.g., 5 engineers and 30 orders require >10 minutes of CPU time without finding the optimum. Use case : Small‑scale validation.

Approximate Algorithms

Advantages : Fast computation and simple implementation. Disadvantages : Greedy focus on the next order can lead to local optima. Use case : Initial solution generation for small‑scale, streaming orders.

Reinforcement Learning

Advantages : Learns from trial‑and‑error, suitable for high‑dimensional, multi‑objective problems. Disadvantages : Cold‑start, lack of interpretability, high computational cost. Use case : Companies like Meituan and Uber use it for real‑time scheduling.

Meta‑heuristic Algorithms

Advantages : Avoids combinatorial explosion, provides near‑optimal solutions (95‑100% of optimum) with low latency and no need for high‑end hardware. Disadvantages : Solution quality depends on parameter tuning. Use case : Large‑scale batch dispatch where absolute optimality is not required.

Considering business scale and cost, the meta‑heuristic approach—specifically a genetic algorithm—was chosen for batch dispatch.

5 Genetic Algorithm Overview

Genetic Algorithm mimics natural selection, crossover, and mutation to evolve solutions. Over successive generations, inferior individuals are discarded while superior ones survive, yielding optimal or near‑optimal solutions.

5.1 Principle

Key operations include:

Crossover : Exchange gene segments between two parent solutions to create offspring. Mutation : Randomly alter gene sequences to introduce diversity.

5.2 Application to Automatic Dispatch

Steps:

Population Initialization

Each individual represents a complete dispatch plan (e.g., Engineer A: orders 1 3, Engineer B: orders 2 4). A population of diverse individuals (e.g., 100) is generated.

Fitness Function

The fitness evaluates two objectives: shortest total engineer travel time and most balanced order allocation. A normalized fitness formula combines travel time, maximum travel time in the population, order‑balance standard deviation, successful dispatch count, and total orders, weighted by business‑driven coefficients.

Selection

High‑fitness individuals are selected using strategies such as elite preservation and roulette‑wheel selection, often combined to maintain diversity while promoting quality.

Crossover

Multi‑point crossover swaps gene segments between two parents. For example, swapping segment [3,4,5] from Parent 1 into Parent 2 produces a new offspring.

<code>示例仅展示基因重组原理，实际还需要考虑订单时间窗口冲突问题。</code>

Mutation

Mutation introduces small random changes (e.g., 5%±2% probability) to prevent premature convergence, such as shuffling a gene segment [3,4,5] into [5,3,4].

Survival of the Fittest

After crossover and mutation, individuals with higher fitness are retained while weaker ones are removed, iterating until convergence.

5.3 Convergence Demonstration

Because engineers must follow appointment start times, the final routes may include back‑tracking, as shown in the convergence animation.

6 Summary

6.1 Business Benefits

Replacing manual planning reduced daily labor from 6 person‑hours to 10 minutes , a 97.22% efficiency gain, freeing two staff members.

6.2 Technical Choice

The genetic algorithm was adopted for its robustness, second‑scale response time, and precise fit to the business’s dispatch volume and mode.