My Portfolio
Research archive
Optimization & Decision Science2026 · Verified algorithmic study

Multi-Period Delivery Routing with ALNS

Poster summary

Python · adaptive large-neighborhood search · heuristic evaluation · pytest

A tested optimization study for a single-vehicle, multi-day routing problem with multiple customer time windows and an explicit cost of postponement.

Repository
01

Research question

Can adaptive large-neighborhood search improve route distance and postponement cost while maintaining complete service on the supplied 300-customer instance?

02

Methodology

Greedy initialization, adaptive destroy-and-repair operators, opportunity-cost weighting, multi-stage parameter search, three-seed evaluation, and baseline comparison

03

Dataset

A supplied instance with 300 customers and 1,359 delivery windows; Euclidean travel assumptions and one vehicle

04

Main finding

The tuned three-seed configuration maintained 100% completion and reported a 32.39% lower objective, 25.17% lower distance, and 32.43% lower postponement penalty than greedy insertion.

Multi-Period Delivery Routing with ALNS

Overview

This algorithmic study models a single-vehicle, multi-day delivery problem in which customers may have multiple service windows and each order can be completed once during the planning week. The objective prioritizes complete service while balancing postponement, travel distance, waiting, and schedule slack.

Problem Definition

Can adaptive large-neighborhood search improve route distance and postponement cost while maintaining complete service on the supplied 300-customer instance?

Economic or Technical Motivation

A locally short route can still be operationally poor if it leaves difficult customers for later days. The solver therefore assigns an opportunity cost to postponement and searches jointly over route order and delivery-day assignment.

Data

The final report uses one supplied instance containing 300 customers and 1,359 time windows. Travel is based on Euclidean coordinates and a fixed-speed conversion. The experiment represents a benchmark-like planning environment, not observed fleet operations.

Methodology

The implementation combines greedy initialization with adaptive destroy and repair operators. Route feasibility is re-evaluated against multiple customer windows after each insertion. A multi-stage tuning process moves from debugging to random screening and focused comparison; the selected configuration is evaluated over three seeds.

Main Findings

The tuned configuration reports a mean objective of 5,236,503, 100% completion, 1,534.59 km total distance, and a 521.67 postponement penalty. Relative to greedy insertion, the report records a 32.39% reduction in objective, a 25.17% reduction in distance, and a 32.43% reduction in postponement penalty.

Robustness, Validation, or Model Assessment

The study compares nearest-neighbor, earliest-deadline-first, greedy-insertion, default ALNS, screening, and tuned ALNS variants. The selected configuration is averaged across three seeds. The repository includes unit tests for distance, time-window feasibility, objective behavior, and time parsing; the earlier audit executed seven tests successfully, while the current bundled Python environment lacks pytest.

Tools and Technologies

Python, pandas, NumPy, adaptive large-neighborhood search, heuristic baselines, parameter search, and pytest tests are directly demonstrated.

Limitations

The experiment uses Euclidean distance, one vehicle, fixed travel speed, no live traffic, and a limited three-seed final comparison. The selected configuration is best within the executed tuning budget; it is not a proof of global optimality.

Deliverables

  • Source-controlled ALNS solver and operators
  • Baseline and tuning pipeline
  • Unit tests and diagnostic outputs
  • Schedules, metrics, and tuning artifacts
  • Final technical report