Yusuf SamiRouting · PROJECT / ALNS
Adaptive Large Neighborhood Search for PDPTW
Adaptive destroy and repair operators for pickup-and-delivery routing with time windows, capacity, and precedence constraints.
The problem
The Pickup and Delivery Problem with Time Windows asks a fleet to serve paired requests while respecting pickup-before-delivery precedence, service windows, vehicle capacities, and depot returns. The objective is to minimize total travel distance without breaking feasibility.
The approach
The solver builds an initial solution with randomized insertion, then repeatedly destroys and repairs neighborhoods. Four destroy operators target random, expensive, related, or time-constrained requests. Three repair operators use random, greedy, or regret-k insertion.
Simulated annealing decides whether worse intermediate solutions can be accepted. Operator weights adapt over time according to whether a move finds a global best, improves the current solution, is accepted, or is rejected.
What is measured
The implementation records current and best distance, temperature, operator selection and weights, neighborhood size, and solution feasibility at every iteration. It produces plots of operator adaptation and convergence rather than reporting only the final route.
Limits
- Performance is demonstrated on the included instances, not a comprehensive benchmark suite.
- The implementation is a research and learning framework, not a production dispatch system.
- Solution quality depends on cooling, scoring, and neighborhood parameters that require systematic tuning.
The useful result is the framework itself: each heuristic choice is explicit, logged, and open to comparison.
Full repository documentation
PDPTW (Pickup & Delivery Problem with Time Windows) – ALNS (Adaptive Large Neighborhood Search)
Python implementation of an Adaptive Large Neighborhood Search (ALNS) framework for the
Pickup and Delivery Problem with Time Windows (PDPTW).
This repo is based on an original course template (Rolf van Lieshout) and extended with:
- multiple destroy/repair operators,
- simulated annealing acceptance,
- adaptive operator weighting (decay + score-based updates),
- and basic visualizations for analysis.
Problem Overview (PDPTW)
In PDPTW, each request consists of:
- a pickup node and a delivery node
- precedence constraint: pickup must happen before delivery
- time windows for service at nodes
- vehicle capacity constraints
- routes must start/end at a depot
Objective: minimize total travel distance while keeping routes feasible.
Method: ALNS
ALNS iteratively improves a current solution by:
- Destroy: remove a subset of requests (neighborhood size is randomized)
- Repair: reinsert removed requests using a heuristic
- Accept/Reject using Simulated Annealing
- Update operator weights based on how good the move was
Initial Solution
- Built using random insertion until all requests are served
- New routes are created if insertion into existing routes is infeasible
Destroy Operators (4)
The code supports the following destroy operators:
Random Removal
- Removes random served requests.
Worst Removal
- Removes requests with the highest “distance saving” when removed (largest contribution).
Shaw (Related) Removal
- Removes “related” requests based on spatial closeness and time-window similarity.
Time-Oriented Removal
- Removes requests with the tightest pickup time windows (smallest width).
Repair Operators (3)
Random Insertion
- Tries to insert each unserved request randomly into feasible routes (or creates a new route).
Greedy Insertion
- Chooses the request + insertion producing the smallest increase in distance.
Regret-k Insertion (default k=2)
- Inserts the request with the largest regret value first
(difference between best and k-th best insertion).
- Inserts the request with the largest regret value first
Acceptance: Simulated Annealing
Move acceptance uses simulated annealing:
- Always accept if a new global best is found
- Accept if improves current solution
- Otherwise accept a worse solution with probability:
P = exp(-Δ / T)
where Δ = (new_cost - current_cost) and T is the temperature.
Temperature decreases each iteration:
temperature *= cooling_rate
Adaptive Operator Weights
Destroy/repair operators are chosen via weighted random selection.
After each iteration:
- a score criterion is assigned:
- New global best
- Improved current solution
- Accepted worse solution
- Rejected worse solution
Weights are updated using decay:
[ w \leftarrow decay \cdot w + (1 - decay) \cdot score ]
Then weights are normalized to sum to 1.
Visualizations / Logging
The solver tracks a datalog with:
- iteration number
- current & best distance
- temperature
- chosen operators + weights
- neighborhood size
- feasibility flag
At the end, it plots:
- destroy operator weights over time
- repair operator weights over time
- current vs best distance over time
It also prints feasibility statistics (percentage of feasible temporary solutions).
Repository Structure
pdptw-alns-optimization/
├─ Instances/
│ ├─ .gitkeep
│ ├─ c202C16.txt
│ ├─ lc102.txt
│ ├─ lc108.txt
│ ├─ lc207.txt
│ ├─ lr112.txt
│ ├─ lr205.txt
│ ├─ lrc104.txt
│ ├─ lrc206.txt
│ ├─ r102C18.txt
│ ├─ rc204C16.txt
│ └─ readme.txt
├─ outputs/
│ ├─ .gitkeep
│ ├─ destroy_operator_weights_over_time.png
│ ├─ repair_operator_weights_over_time.png
│ └─ route_distance_over_time.png
├─ src/
│ ├─ ALNS.py
│ ├─ Main.py
│ ├─ Problem.py
│ ├─ Route.py
│ └─ Solution.py
├─ .gitignore
├─ LICENSE
├─ PDPTW_Report.pdf
└─ README.md
How to Run
Requirements
- Python 3.x
- numpy, matplotlib
Install dependencies:
pip install numpy matplotlib
Run:
python Main.py
Selecting an instance
In Main.py, pick an instance using:
test = instances[6]
ACTUAL PROJECT OUTPUTS
Evidence, not decoration.
