2E-VRP-D Branch-Cut-and-Price Reproduction

This repository contains a Java + Gurobi reproduction of the branch-cut-and-price algorithm from:

Lichau, S., Sadykov, R., François, J., Dupas, R. (2025). A branch-cut-and-price approach for the two-echelon vehicle routing problem with drones.

The goal of this project is to reproduce the paper's main algorithmic structure and deliver strong performance on the Cardiff benchmark family.

This is an independent reproduction for research and educational purposes.

What Is Implemented

• Set-partitioning restricted master problem
• RCSP pricing with long-mask labels and parent-pointer reconstruction
• Split pricing and slot-expanded bidirectional pricing
• Bucket-arc pruning and fixed-point reachability filtering
• Drone schedule enumeration with SPR preprocessing
• Adapted rounded capacity cuts
• Limited-memory rank-one cuts (--lm-r1c)
• Three-phase branching and branch-and-price tree search
• Heuristic route pool, inspection, and incumbent improvement
• Exact and proof-oriented pricing modes

Quick Start

Requirements:

• Java JDK
• Gurobi with the Java API installed

Set your local Gurobi path, build the project, then run an instance:

set GUROBI_HOME=C:\path\to\gurobi\win64
build.bat
run.bat 2E-VRP-D_instances\10_and_15_customers\Cardiff10_01.txt --time 20 --node-time 20 --pricing-time 5 --cols 120 --labels 100000 --bucket 200 --max-neighborhood 10 --split-bidirectional --quiet

For a benchmark batch:

powershell -ExecutionPolicy Bypass -File .\benchmark25.ps1

Verified Results

Representative audited results:

Instance	Result
Cardiff10_01	1223.616667, exact
Cardiff15_01	1332.000000, exact
Cardiff25_02	1979.950000, exact

The 25-customer cases are the main performance target of this implementation. The audited runs are paper-close overall, and several are proven exactly.

Implementation Notes

• long bit masks are used for visited/customer-set operations on the supported benchmark sizes.
• Labels keep parent pointers; routes are reconstructed only when a candidate column survives reduced-cost checks.
• Pricing precomputes dual terms, forbidden-arc masks, and bucketed successor profiles.
• document.md contains the detailed development and reproduction notes.
• COMPLETION_AUDIT.md records the broader audit trail and verification status.

Repository Layout

• src/main/java/evrpd/ - solver implementation
• 2E-VRP-D_instances/ - benchmark instances
• build.bat / run.bat - local build and run helpers
• benchmark25.ps1 - batch benchmark runner
• document.md - detailed reproduction document

Notes

• The project reads Gurobi from the GUROBI_HOME environment variable.
• The solver does not require any external route reference files at runtime.
• Detailed algorithmic coverage and audit notes are kept in document.md.
• Please cite the original paper when using this reproduction for research.
• Benchmark instances are included for reproducibility. Please check the original dataset terms before redistribution or commercial use.