Skip to content

Vehicle Routing Problem

Definition

The vehicle routing problem asks for a minimum-distance set of vehicle routes that start and end at a depot, visit every required location, and respect the vehicle's restrictions. In the course example, one depot serves eight required locations. The vehicle can travel at most 100 miles between refuelling stops, and refuelling is possible only at the depot.

Interpretation

The vehicle routing problem plans trips from a depot so that every required location is visited and the total distance is as small as possible. The range limit makes it harder than a single round trip: the locations may have to be split over several trips, and both the split and the order within each trip are decisions.

An independent schematic of a depot and eight locations served by two round trips; no distances or range feasibility are asserted.

This independent schematic shows how routes start and end at the depot and together visit all eight locations. It does not represent the 232-, 214- or 202-mile numerical example below. No distances are assigned, so the picture alone does not establish whether either trip satisfies a range limit. To be a feasible solution, a plan must also satisfy that limit on every trip.

Serving every location by its own trip from the depot is feasible here, and joining successive visits while keeping each trip within range can shorten the plan; such heuristic plans give upper bounds on the minimum distance. Dropping the range limit is a relaxation: its optimum is a lower bound, but its route may be too long for the vehicle. With the distances of the Examples, this traps the optimum between 202202 and 214214 miles (optimization bounds).

A common slip is to take the relaxed route as the answer: it is shorter only because it ignores refuelling, so it is a bound, not a plan that can be driven.

Key Results

  • Every required location must be visited and every trip must respect the fuel limit.
  • Joining successive visits can improve a plan if feasibility is retained.
  • Removing the fuel limit gives a lower bound, not automatically a feasible route for the original problem.

Examples

  • Separate visits from the depot produce the stated 232-mile heuristic plan.
  • The improved plan has length 214; the relaxed optimum has length 202.

Prerequisites

Sources

Aliases: VRP

Last updated: 27 October 2026 11:52