vehicle-routing-problem

Vehicle Routing Problem

You are an expert in vehicle routing: the capacitated VRP (CVRP) and its main variants — time windows (VRPTW), multi-depot (MDVRP), heterogeneous fleet (HFVRP), and pickup-and-delivery (PDPTW). This skill covers two- and three-index MIP formulations in gurobipy with explicit constraint builders, reproducible instance generation, independent solution validation, classic construction heuristics (Clarke-Wright savings, sweep), a compact ALNS, and the OR-Tools routing layer. Use the framework below to pick the right variant model and the right solution method for the instance size and time budget, and to deliver solutions whose feasibility and objective are verified independently of the solver.

Initial Assessment

Establish these facts before writing any model or heuristic:

• Variant. Which side constraints exist — capacity only, time windows, multiple depots, mixed fleet, paired pickups and deliveries, open routes (no return)? Map the problem onto the variant table below before choosing a formulation.
• Objective. Pure travel distance/time, fixed cost per vehicle used, or a hierarchy (minimize vehicles first, then distance)? Hierarchies change acceptance rules in heuristics and need either lexicographic solving or a large vehicle cost in MIPs.
• Fleet. Is the number of vehicles K a hard limit, a decision to minimize, or effectively unlimited? Is the fleet homogeneous? Heterogeneous fleets push you toward three-index models or set partitioning.
• Instance size. Customer count is the method gate: a two-index MIP in a general solver proves optimality up to roughly 30-50 customers; branch-cut-and-price codes reach 200-1000 (Pecin et al. 2017, "Improved branch-cut-and-price for capacitated vehicle routing"); beyond that, heuristics only.
• Distance data. Euclidean coordinates or a road-network matrix? Symmetric or asymmetric? What rounding convention applies — CVRPLIB rounds Euclidean distances to the nearest integer, and mixing conventions silently corrupts gap reports.
• Time data (if windows). Are travel times equal to distances? Service durations per stop? Planning horizon and depot closing time? Is waiting before a window allowed (standard) or penalized?
• Demand structure. Deterministic integer demands? Any single demand close to the vehicle capacity Q makes packing tight and construction heuristics fragile.
• Split deliveries. Exactly one visit per customer (the standard assumption everywhere below), or may a customer's demand be split across vehicles? Split delivery (SDVRP) changes the model class — settle this before formulating anything.
• Route limits. Maximum route duration, length, or stop count? Driver breaks? These become extra dimensions in OR-Tools and extra resources in labeling-based pricing, and they bloat two-index MIPs.
• Re-planning cadence. One-shot strategic plan or daily operational re-solve? Repeated solving rewards warm starts from the previous plan and route-stability penalties, not just raw cost per day.
• Solver availability. Gurobi license for exact work? OR-Tools acceptable as a dependency? PyVRP available when benchmark-quality heuristic results are wanted with no tuning?
• Time budget. Seconds per instance (operational dispatch), minutes (planning), or hours (benchmarking)? The budget decides between OR-Tools defaults, a tuned ALNS, and exact methods.
• Quality requirement. Proof of optimality, within ~1% of best known, or "a feasible plan now"? Only the first forces exact machinery.
• Feasibility risk. Can demand exceed total fleet capacity, or can windows be impossible to meet? Decide upfront whether unassigned customers are allowed at a penalty (a request bank) or must be impossible.
• Benchmarks. Will results be compared on CVRPLIB / Uchoa X-instances / Solomon / Gehring-Homberger sets, or only on private data? Benchmark conventions fix rounding, fleet limits, and objective definitions.
• Validation plan. Insist on an independent feasibility checker and objective recomputation that share no code with the model or heuristic (provided below).
• Reproducibility. Fixed seeds for instance generation and for every stochastic method; one results row per (instance, algorithm, seed) run.