The Vehicle Routing Problem

At its core, the Vehicle Routing Problem (VRP) is about finding the most efficient set of routes for a fleet of vehicles to serve a group of customers. This fundamental challenge in logistics aims to minimize total transportation costs—be it time, distance, or money—while adhering to real-world operational rules. This interactive guide explores why this seemingly simple problem is one of the most complex computational challenges in modern industry.

Why is VRP "NP-Hard"?

VRP is classified as NP-hard, meaning finding a perfect, optimal solution becomes computationally impossible as the problem size grows. This is due to two key concepts: combinatorial explosion and the difference between finding and verifying a solution.

The "Rich" VRP: Real-World Complexity

The basic VRP is hard enough. In the real world, layers of constraints make it a "rich" problem, compounding the difficulty. Each constraint interacts with the others, creating a deeply complex optimization puzzle.

Quantum Advantage for VRP

Vehicle Routing Problems are NP-hard, and complexity grows rapidly with more locations, vehicles, and constraints. Quantum computing offers a way to explore large solution spaces more efficiently than classical heuristics.

Key Benefits

  • Faster search for high-quality routing solutions.
  • Better handling of multiple constraints simultaneously.
  • Potential for real-time re-optimization in dynamic operations.

VRP Planning Assumptions & Data Handling Framework

Key assumptions used for planning and data filtering in the current VRP prototype.

A. Distribution Centers & Fleet Usage

  • Only jobs and fleets associated with DC001, DC002, and DC003 are included. DC004 and its jobs are excluded due to missing fleet data and unclear operational logistics.
  • Vehicles marked for “Inter-DC” or “Inter-Warehouse only” operations are excluded from store delivery planning.
  • All vehicle routes are single daily closed loops, requiring return to home depot by end of shift.
  • Job–vehicle–depot compatibility is solely enforced using skills matching.
  • Jenis Badan / Body Type information is ignored as it has no impact on current VRP constraints.

B. Store and Job Validity Filtering

  • Stores not listed in the constraint table but available in coordinates/demand data are assumed to have no constraints.
  • Stores missing road connectivity (PDO4, P047, P071, T022, TQ01) are excluded due to non-serviceable logistics.
  • Stores listed in constraints (D002, DA01, DB01, P077, DB02, DB09, DB07) but missing coordinates/demand are removed.
  • Store ID changes (Q055→EKTP, Q042→ELKG, Q038→EMLM) are not applied; original IDs retained due to missing replacement data.

C. Delivery Rules & Order Value Policy

  • Jobs with order values under RM 3,000 are still delivered on the same day; no carry-forward rule is applied.
  • Operations are planned Monday–Friday only; Saturday is excluded due to lack of delivery data.
  • Carton limit constraints are ignored due to missing conversion to CBM volumetric capacity.

D. Time Windows & Service Behavior

  • Vehicle and depot operations windows are assumed 24-hour; job time windows are strictly enforced where provided.
  • All jobs assume a default 1.5 hr service time unless specified, covering unloading and driver rest.

E. Optimization Objective

  • The solver focuses on maximum job coverage (maximize deliveries/pickups completed).
  • Cost optimization is not prioritized in the current version.

Data Visualization

Results Visualization

The Search for a Solution

Since finding a perfect solution is often impossible, the industry relies on clever algorithms and emerging technologies to find "good enough" solutions quickly.

The Quantum & Future Frontier

Emerging paradigms like quantum computing (via platforms like D-Wave or IBM Quantum) and optical computing (e.g., LightSolver) offer new ways to explore the vast solution space, potentially solving large-scale problems that are intractable for classical computers. Companies like spindle.sg are pioneering these quantum-based solutions for logistics.

Heuristics & Approximation

These are the workhorses of the industry. Algorithms like Tabu Search or Genetic Algorithms don't guarantee the absolute best solution, but they find excellent, practical routes in a fraction of the time, balancing quality with speed.

Commercial Solvers

Sophisticated software platforms that bundle powerful heuristic algorithms with user-friendly interfaces. They handle numerous real-world constraints and provide dynamic re-optimization in response to events like traffic jams or new orders.