Vehicle Routing Problem: A Method Guide to Formulations and Algorithms

1. Introduction

1.1 Problem Statement

The Vehicle Routing Problem, first formulated by Dantzig and Ramser in 1959, addresses a basic question in logistics: given a fleet of vehicles with limited capacity and a set of geographically dispersed customers with specific demands, how should deliveries be organized to minimize total cost while satisfying all service constraints? The question is easy to state and hard to solve. VRP belongs to the class of NP-hard problems, so the effort needed to find a provably optimal solution grows very quickly with the number of delivery locations.

Real operations add further requirements: tight delivery windows, several competing objectives such as fuel use, driver workload balance and vehicle utilization, and changes that arrive during the day such as traffic or new requests. These are the reasons the basic formulation is extended into the variants described in Section 2.

Manual planning by an experienced dispatcher can work for a small number of stops, but it becomes hard to apply consistently as stops and constraints multiply. Simple rules such as nearest-neighbor or geographic clustering are easy to implement, but they make myopic choices and can violate time windows or capacity when constraints are tight. Search-based methods exist to handle that interaction between route structure and constraints.

1.2 Scope and Objectives

This paper explains the method. It does not present original research, field results or case studies. Its scope is:

• Mathematical formulation of the VRP and its principal variants, including capacitated VRP (CVRP), VRP with time windows (VRPTW) and dynamic VRP (DVRP)
• Algorithm families: exact methods, construction heuristics, local search, metaheuristics and hybrids
• Data requirements for building a routing model and the quality problems to check for
• A suggested sequence for applying the method, from data assessment to a pilot to wider use
• Evaluation: how to compare routing plans across operational, financial and service dimensions
• An illustrative worked example with made-up numbers, in Section 4

The intended reader is a technical or operations lead who needs to understand what a routing solver does, what it assumes, and where it can mislead.

1.3 When Routing Optimization Applies

Routing optimization is relevant when there are enough stops that a plan has many alternatives, when constraints such as capacity or time windows interact, and when the cost of a route (distance, time, fuel, driver hours) is measurable. It is less useful when the stops are few and fixed, when routes are dictated by contract or regulation, or when the distance and time data are too unreliable to trust. In those cases improving the data or the process comes first.

2. Background

2.1 Mathematical Foundations of VRP

The classical VRP can be defined on a complete graph G = (V, E) where V = {0, 1, 2, ..., n} are vertices (vertex 0 is the depot and vertices 1 through n are customers) and each edge has an associated cost c_ij. The objective is to determine a set of routes such that:

• Each route begins and ends at the depot (vertex 0)
• Each customer is visited exactly once by exactly one vehicle
• The total demand of customers on each route does not exceed vehicle capacity Q
• The total cost (typically distance or time) across all routes is minimized

This can be written as an integer linear program with a binary variable x_ij for each edge, flow-conservation constraints at each customer, and capacity (subtour elimination) constraints. The number of possible route sets grows combinatorially with n, which is why direct enumeration is impractical beyond very small instances.

Variants extend this basic formulation with additional constraints:

2.2 Common Approaches and Their Limitations

Organizations route vehicles in several ways, each with characteristic limitations.

Manual routing by dispatchers uses domain knowledge and spatial reasoning, and often handles familiar patterns well. Its limits are consistency and scale: quality depends on the individual, many simultaneous constraints are hard to track by hand, and there is no built-in way to quantify how good a plan is.

Simple rule-based heuristics such as nearest-neighbor or geographic clustering are cheap to compute and easy to explain. Because they decide one step at a time, they can leave obvious improvements on the table and can break time-window or capacity constraints.

Commercial routing software offers interfaces and standard VRP variants. Some products expose little about their method or constraint handling, which makes it harder to diagnose a poor plan or adapt to an unusual rule. Understanding the underlying method makes it easier to evaluate such tools.

Custom implementations give maximum flexibility but need operations research and data engineering skills, and are often held back by data preparation and integration more than by the algorithm.

3. Method

3.1 How This Paper Was Prepared

This paper is a synthesis of standard material on the VRP from the operations research literature (see the references). It contains no experiments, no data collected by MCP Analytics, and no surveys or customer interviews. Where it describes how an algorithm behaves in general terms, the description is qualitative. Any numeric values appear only in the labelled illustrative example in Section 4, where they are made up for explanation.

3.2 Data Considerations for VRP

A routing model is only as good as its inputs. The main categories are:

3.3 A Suggested Sequence for Applying the Method

The following sequence is a general working pattern, not a measured protocol. Durations depend entirely on the organization and are deliberately not given.

Step 1: Data assessment and preparation

Inventory the data sources and check quality across the categories above. Identify missing elements, such as vehicle location history or recorded service times, and decide how to collect them. Consolidate routing-relevant data from order, fleet and customer systems into one place.

Step 2: Baseline measurement and problem formulation

Document current performance: route distance and duration, vehicles used, cost per stop, on-time performance and utilization. This baseline is what any later plan is compared with. Choose the VRP variant that matches reality, separating hard constraints (time windows, capacity) from soft objectives (total distance, route balance).

Step 3: Pilot on a limited scope

Apply a solver to one region, service type or day of the week. Compare its routes with both the baseline and the routes drivers currently run, and review them with dispatchers and drivers to find constraints the model does not capture.

Step 4: Refinement and scaling

Add the constraints and objectives found in the pilot, widen the scope gradually, and keep measuring so that any benefit seen in the pilot is checked as scope grows. Define how exceptions and manual overrides are handled.

Step 5: Dynamic optimization and ongoing review

If the operation needs it, move from fixed daily plans to re-optimization as conditions change. Feed actual execution data back to recalibrate travel and service times, and review the model periodically as operations change.

3.4 Algorithmic Techniques Overview

Solution methods fall into a few families:

Exact algorithms such as branch-and-bound and branch-and-cut return provably optimal solutions but their running time grows rapidly with instance size, so they suit small instances, validating heuristics on test cases, and solving sub-problems inside decomposition schemes.

Construction heuristics build a feasible solution step by step. The Clarke-Wright savings algorithm starts with one route per customer and repeatedly merges the pair of routes that saves the most distance, subject to capacity. Insertion methods add customers to routes at the cheapest feasible position. They run fast and give a feasible starting point, but they do not guarantee quality and are usually improved afterwards.

Local search improves a solution by small changes. Intra-route operators such as 2-opt and Or-opt reorder stops within a route, and inter-route operators such as relocate, swap and cross-exchange move stops between routes. Search stops at a local optimum, a solution that no single move improves.

Metaheuristics such as tabu search, simulated annealing, genetic algorithms and variable neighborhood search guide the search so that it can escape local optima. They typically need more computation time than a single pass of local search, which matters when plans are needed quickly.

Hybrid designs combine these. A typical architecture builds an initial solution with a construction heuristic, improves it with local search, and applies a metaheuristic when the time budget allows. Which combination fits depends on instance size, how quickly a plan is needed, and how much solution quality matters for the decision at hand.

4. Worked Example (Illustrative)

5. Key Points and Practical Considerations

5.1 Technical Considerations for Implementation Teams

Data integration needs design. Routing depends on data from order management, fleet management, customer records and traffic sources, each with its own update frequency and quality. Pipelines should include validation, and failures in data engineering are a common reason a routing project underdelivers.

Measure several dimensions. Optimizing only total distance can produce plans that violate soft constraints or load some drivers far more than others. Track operational metrics (distance, time, utilization), service metrics (on-time performance, time-window compliance), cost metrics (fuel, labor, depreciation) and qualitative feedback. Multi-objective or constrained formulations make trade-offs explicit.

Plan for the human side. Planners and drivers know constraints that no data file contains. Involve them in constraint definition, make the logic of the solver understandable, and allow overrides for exceptions. A routing system works best as support for human judgment, not a replacement for it.

5.2 Scalability Considerations

Decomposition splits a large instance into sub-problems, for example by geographic clustering into regions that are solved separately, with a rule for the boundaries between them. Dynamic routing can combine an offline plan with fast re-optimization when something changes.

Computing resources. Optimization runs are typically batch jobs and can often be parallelized, so elastic computing capacity is a natural fit for peak planning periods.

Standard data models and interfaces make it easier to bring a new depot or business unit into an existing routing setup.

6. Guidance for Applying the Method

The following is general guidance based on the method described above. It is not derived from measured results.

6.1 Sequencing by Starting Point

An organization with little routing data should begin with data collection and a baseline, using a simple solver on clean data. One with an existing routing system and decent data can focus on calibrating travel and service times and on the choice of solver. One with an established system can look at dynamic routing, multi-objective formulations, or learned predictors for service time and demand.

7. Conclusion

The Vehicle Routing Problem is a well-studied optimization problem with many variants. This paper has explained its formulation, the families of algorithms used to solve it, the data a routing model depends on, and a staged way of applying the method. It is an explanation of a method, not a study: it reports no measured results, and the worked example uses made-up numbers.

Whether routing optimization pays off in a given operation depends on that operation's stops, constraints and data quality. The way to find out is to record a baseline, apply a solver on a limited scope, and compare the results with the baseline on several metrics.

In practice the quality of the inputs, the fit between the formulation and real constraints, and the acceptance of the plan by the people who run it matter at least as much as the choice of search algorithm.