Vehicle Routing Problem (VRP)

The VRP is a classic NP-hard combinatorial optimization problem. The number of possible routes grows factorially with the number of customers, making exhaustive search computationally intractable for real-world instances. Solving a VRP with just 20 customers yields more possible route combinations than there are stars in the observable universe, necessitating heuristic and metaheuristic solution approaches.

Every VRP variant is governed by an objective function that the algorithm seeks to minimize or maximize. Common objectives include:

• Minimize total distance traveled by the fleet
• Minimize total cost, incorporating fuel, labor, and vehicle maintenance
• Minimize number of vehicles required to service all customers
• Maximize customer service level, such as on-time deliveries within specified time windows
• Minimize total route duration, including travel and service time

VRP variants are distinguished by their constraint sets, which define the feasibility of a solution. Core constraints include:

• Capacity Constraints: Each vehicle has a finite weight or volume limit that cannot be exceeded
• Time Window Constraints: Customers specify hard or soft intervals during which service must occur
• Route Duration Limits: Maximum driving or working time per vehicle before a mandatory return to the depot
• Precedence Constraints: Certain customers must be visited before others (e.g., pickup before delivery)
• Vehicle Heterogeneity: The fleet contains vehicles with different capacities, speeds, and cost profiles

When formulated for reinforcement learning, the VRP is modeled as a sequential decision process. The state includes the current location of each vehicle, remaining capacity, unvisited customers, and elapsed time. The action is the selection of the next customer to visit. The state space is combinatorial and dynamic, growing with each new customer and vehicle added. This high-dimensional representation is why Deep Q-Networks and Pointer Networks are employed to approximate optimal policies.

A critical distinction exists between static and dynamic VRP formulations:

• Static VRP: All problem data (customer locations, demands, time windows) is known with certainty before route construction begins. The solution is computed once and executed without modification.
• Dynamic VRP: New orders, cancellations, or traffic disruptions arrive in real-time during execution. The routing plan must be continuously re-optimized, requiring online algorithms that balance solution quality with computational responsiveness.

The physical topology of the operation defines the VRP variant:

• Single Depot: All vehicles start and end their routes at one central location, typical of last-mile delivery from a single warehouse
• Multi-Depot VRP (MDVRP): Vehicles are stationed at multiple geographically distributed depots, requiring simultaneous assignment of customers to depots and routing from each depot
• Open VRP (OVRP): Vehicles are not required to return to the depot after completing deliveries, common in third-party logistics where carriers own the vehicles