Skip to content

ALGORITHMS.md

Latest commit

 

History

History
620 lines (441 loc) · 16.6 KB

ALGORITHMS.md

File metadata and controls

620 lines (441 loc) · 16.6 KB

Algorithm Documentation

This document provides detailed documentation for each metaheuristic algorithm implemented in the TOPTW package.

Table of Contents

  1. Genetic Algorithm (GA)
  2. Simulated Annealing (SA)
  3. Tabu Search
  4. GRASP
  5. Ant Colony Optimization (ACO)
  6. Particle Swarm Optimization (PSO)

1. Genetic Algorithm (GA)

Overview

Genetic Algorithms are population-based evolutionary algorithms inspired by natural selection. They maintain a population of solutions that evolve over generations through selection, crossover, and mutation operators.

Why suitable for TOPTW: GAs can explore diverse regions of the solution space simultaneously through their population-based approach, and the crossover operator allows combining good partial solutions (routes) from different parents.

Implementation Details

Solution Encoding

solution = [[tour_1], [tour_2], ..., [tour_v]]

Each solution is a list of v tours (one per vehicle), where each tour is a list of Node objects representing customers in visitation order.

Initial Population

  • Method: Random greedy construction
  • Process: For each tour, randomly select feasible customers until no more can be added
  • Population size: 200 individuals (configurable)

Selection Operator

  • Method: Random selection (no fitness bias)
  • Process: Two parents selected uniformly at random from population

Crossover Operator

Tour-level exchange crossover:

Input: Parent solutions P1 and P2
Process:
  1. Select random tour index i from P1
  2. Select random tour index j from P2
  3. Swap P1[i] with P2[j]
  4. Repair both solutions (remove duplicate customers)
Output: Two offspring solutions

Mutation Operators

1. Insertion Mutation (80% probability)

Input: Solution S, tour index i
Process:
  1. Find all unvisited customers
  2. For random positions in tour:
     - Try inserting each unvisited customer
     - Accept first feasible insertion
Output: Modified solution

2. Removal Mutation (20% probability)

Input: Solution S, tour index i
Process:
  1. If tour has > 2 customers:
     - Remove random customer from tour
Output: Modified solution

Fitness Function

fitness(solution) = Σ (score of all customers in feasible tours)

Only tours that satisfy all time window and time budget constraints contribute to fitness.

Replacement Strategy

Elitist with random component:

  1. Combine parents and offspring (pool of ~400 solutions)
  2. Sort by fitness (descending)
  3. Select: 70% best solutions + 30% random from remainder
  4. Result: Next generation of 200 individuals

Termination Criteria

  • Maximum generations: 500 (default)
  • Time limit: Optional

Parameters

Parameter Default Description
population_size 200 Number of individuals in population
generations 500 Number of evolution iterations
num_threads 100 Parallel threads for offspring generation
elite_ratio 0.7 Fraction of best individuals always kept

Pseudocode

Algorithm: Genetic Algorithm for TOPTW
Input: Problem instance, parameters
Output: Best solution found

population ← GenerateRandomPopulation(population_size)

for generation = 1 to max_generations:
    offspring ← []

    parallel for i = 1 to num_threads:
        parent1 ← RandomSelect(population)
        parent2 ← RandomSelect(population)
        child1, child2 ← Crossover(parent1, parent2)
        child1 ← Mutate(child1)
        child2 ← Mutate(child2)
        offspring.add(child1, child2)

    pool ← population ∪ offspring
    Sort(pool, by=fitness, descending)

    elite ← pool[0:elite_count]
    random_selection ← RandomChoice(pool[elite_count:], k=random_count)
    population ← elite ∪ random_selection

return BestSolution(population)

2. Simulated Annealing (SA)

Overview

Simulated Annealing is a probabilistic local search algorithm inspired by the annealing process in metallurgy. It accepts worse solutions with a probability that decreases over time, allowing escape from local optima.

Why suitable for TOPTW: SA can escape local optima through its probabilistic acceptance, which is important for complex routing problems with many constraints.

Implementation Details

Note: This algorithm is implemented in C++ for performance.

Neighborhood Structure

Three neighborhood operators are applied in sequence:

1. Swap Within Tour (swap_in_tour)

- Select random tour
- Swap two random positions within the tour
- Accept if feasible, retry up to 2 times

2. Swap Between Tours (swap_between_two_tour)

- Select two random tours
- Swap one node between them
- Accept if both tours remain feasible
- Retry up to 6 times

3. Local Search Insertion (local_search_insertion)

- For each position in each tour:
  - Try inserting unvisited customers
  - Accept first feasible insertion

Initial Solution

  • Method: Random construction
  • Randomly select feasible customers until no more fit

Cooling Schedule

Geometric cooling:

T_new = α × T_current
Parameter Value
Initial temperature (T₀) 150
Cooling rate (α) 0.5
Iterations before cooling 1000
Moves per iteration 30

Acceptance Probability

Metropolis criterion:

If new_score > current_score:
    Accept (always)
Else:
    Δ = current_score - new_score
    p = exp(Δ / T)
    Accept with probability p

Parameters

Parameter Default Description
num_runs 5 Independent restarts
time_limit_per_run 60s Time limit per run
Initial temperature 150 Fixed in C++
Cooling rate 0.5 Fixed in C++

Pseudocode

Algorithm: Simulated Annealing for TOPTW
Input: Problem instance
Output: Best solution found

for run = 1 to num_runs:
    T ← 150
    α ← 0.5
    solution ← RandomInitialSolution()
    best ← solution

    while T > 0 and time < time_limit:
        for j = 1 to 30:
            candidate ← SwapInTour(solution)
            candidate ← SwapBetweenTours(candidate)
            candidate ← LocalSearchInsertion(candidate)

            if Score(candidate) > Score(solution):
                solution ← candidate
                best ← candidate if Score(candidate) > Score(best)
            else:
                Δ ← Score(best) - Score(candidate)
                if random() ≤ exp(Δ/T):
                    solution ← candidate

        T ← α × T

return best

3. Tabu Search

Overview

Tabu Search is a memory-based local search algorithm that maintains a list of recently visited solutions or moves to prevent cycling and promote exploration.

Why suitable for TOPTW: The tabu list prevents revisiting recent configurations, forcing exploration of new regions of the solution space.

Implementation Details

Note: This algorithm is implemented in C++ for performance.

Tabu List Structure

  • What's stored: Route indices (not specific moves or solutions)
  • Structure: Array of counters, one per route
  • Mechanism: When a route is modified, its counter is set to tabu_tenure; counters decrement each iteration

Tabu Tenure

  • Value: Equal to number of vehicles (team_number)
  • Type: Fixed (not adaptive)

Aspiration Criteria

Not implemented: Tabu moves are never accepted, even if they would improve the best solution.

Neighborhood Operators

Same three operators as SA:

  1. Swap within tour (checks tabu status)
  2. Swap between tours (checks tabu status)
  3. Local search insertion (always available)

Intensification/Diversification

Not explicitly implemented: Relies on tabu list alone for diversification.

Parameters

Parameter Default Description
num_runs 5 Independent restarts
max_iterations 5000 Iterations per run
Tabu tenure num_vehicles Fixed in C++
Swap attempts 100 Max attempts per operator

Pseudocode

Algorithm: Tabu Search for TOPTW
Input: Problem instance
Output: Best solution found

for run = 1 to num_runs:
    solution ← RandomInitialSolution()
    best ← solution
    tabu_list ← [0, 0, ..., 0]  // One per route

    for iteration = 1 to max_iterations:
        // Apply operators (skip if tabu)
        if not IsTabu(tour_index):
            candidate ← SwapInTour(solution, tour_index)
            SetTabu(tour_index, tabu_tenure)

        candidate ← SwapBetweenTours(candidate)
        candidate ← LocalSearchInsertion(candidate)

        if Score(candidate) > Score(best):
            solution ← candidate
            best ← candidate

        // Decay tabu counters
        for i in range(num_routes):
            if tabu_list[i] > 0:
                tabu_list[i] -= 1

return best

4. GRASP

Overview

GRASP (Greedy Randomized Adaptive Search Procedure) is a multi-start metaheuristic that combines greedy construction with local search. Each iteration constructs a solution using a randomized greedy approach, then improves it with local search.

Why suitable for TOPTW: The greedy construction respects time windows naturally, and the randomization ensures diverse starting points for local search.

Implementation Details

Note: This algorithm is implemented in C++ for performance.

Greedy Construction

Greedy function:

ratio(candidate) = score² / distance_to_current

Restricted Candidate List (RCL):

  • Size: 7 candidates
  • Selection: Random from top 7 by greedy ratio

Construction Process:

For each vehicle:
    current ← depot
    tour ← []
    while candidates exist:
        Sort candidates by greedy ratio
        Select random from top 7
        If feasible: add to tour, update current
        Else: retry (up to 6 times)

Local Search

Insertion improvement (3 iterations):

For each tour position:
    For each unvisited customer:
        If insertion is feasible:
            Insert customer
            Break

Parameters

Parameter Default Description
num_runs 5 Independent runs
max_iterations 100,000 Constructions per run
time_limit_per_run 30s Time limit per run
RCL size 7 Fixed in C++
Local search iterations 3 Fixed in C++

Pseudocode

Algorithm: GRASP for TOPTW
Input: Problem instance
Output: Best solution found

for run = 1 to num_runs:
    best ← null
    best_score ← 0

    while time < time_limit and iterations < max_iterations:
        // Construction phase
        solution ← GreedyRandomizedConstruction()

        // Local search phase (3 iterations)
        for i = 1 to 3:
            solution ← InsertionLocalSearch(solution)

        if Score(solution) > best_score:
            best ← solution
            best_score ← Score(solution)

return best

5. Ant Colony Optimization (ACO)

Overview

ACO is a swarm intelligence algorithm inspired by ant foraging behavior. Artificial ants construct solutions probabilistically using pheromone trails that are updated based on solution quality.

Why suitable for TOPTW: The pheromone mechanism can learn which edges (customer pairs) are frequently used in good solutions, guiding future constructions.

Implementation Details

Pheromone Matrix

  • Structure: 2D matrix τ[i][j] for each pair of nodes
  • Initial value: τ₀ = 1.0
  • Updates: During construction and after evaporation

Heuristic Information (η)

η(i, j) = score_j / (max(distance, time_gap) × time_window_duration + 1)

Where:

  • time_gap = open_time_j - current_time - service_time_i
  • time_window_duration = close_time_j - current_time - service_time_i - distance

Construction Phase

Selection probability:

p(i, j) = (η(i,j) × τ[i][j]) / Σₖ(η(i,k) × τ[i][k])

Process:

  1. Find all feasible next customers
  2. Calculate η×τ for each
  3. Select customer with maximum probability (or random if all zero)
  4. Update pheromone on selected edge

Pheromone Update

During construction:

τ[i][j] ← τ[i][j] + ψ × τ₀

After each iteration (evaporation):

τ[i][j] ← (1 - ρ) × τ[i][j]   for all i, j

Local Search

Same insertion improvement as GRASP, applied twice per iteration.

Parameters

Parameter Default Description
rho (ρ) 0.1 Evaporation rate
psi (ψ) 0.1 Pheromone deposit rate
tau_zero (τ₀) 1.0 Initial pheromone value
time_limit_per_run 180s Time limit per run

Pseudocode

Algorithm: Ant Colony Optimization for TOPTW
Input: Problem instance
Output: Best solution found

τ ← Initialize(n × n matrix, τ₀)
best ← null
best_score ← 0

while time < time_limit:
    // Construct solution
    solution ← []
    for vehicle = 1 to v:
        tour ← ConstructTour(τ, η)
        solution.add(tour)

    // Local search (twice)
    solution ← InsertionLocalSearch(solution)
    solution ← InsertionLocalSearch(solution)

    if Score(solution) > best_score:
        best ← solution
        best_score ← Score(solution)

    // Evaporation
    τ ← (1 - ρ) × τ

return best

6. Particle Swarm Optimization (PSO)

Overview

PSO is a swarm intelligence algorithm where particles (solutions) move through the solution space influenced by their personal best position and the global best position of the swarm.

Why suitable for TOPTW: PSO balances exploration and exploitation through the interaction between personal experience and swarm knowledge.

Implementation Details

Population Structure

  • Particles: 100 complete solutions
  • Personal best (p_best): Best solution found by each particle
  • Global best (g_best): Best solution found by any particle

Operators

Mutation operators applied to each particle:

  1. Swap mutation: Swap two nodes within a tour (if feasible)
  2. Insert mutation (80%): Insert unvisited customer
  3. Remove mutation (20%): Remove random customer

Position update via tour exchange:

  1. Exchange with p_best (10% of tours):

    • Swap random tours between current and personal best
    • Repair duplicates

  2. Exchange with g_best (30% of tours):

    • Swap random tours between current and global best
    • Repair duplicates

Parameters

Parameter Default Description
population_size 100 Number of particles
max_iterations 5000 Iterations per run
p_best_weight 10 % tours exchanged with p_best
g_best_weight 30 % tours exchanged with g_best
num_runs 3 Independent runs

Pseudocode

Algorithm: Particle Swarm Optimization for TOPTW
Input: Problem instance
Output: Best solution found

for run = 1 to num_runs:
    population ← RandomInitialize(population_size)
    p_best ← copy(population)
    g_best ← BestOf(population)

    for iteration = 1 to max_iterations:
        for each particle j:
            // Apply mutations
            particle[j] ← MutationSwap(particle[j])
            particle[j] ← MutationInsertOrRemove(particle[j])

            // Exchange with personal best
            particle[j] ← ExchangeTours(particle[j], p_best[j], p_best_weight)

            // Exchange with global best
            particle[j] ← ExchangeTours(particle[j], g_best, g_best_weight)

            // Update bests
            if Score(particle[j]) > Score(p_best[j]):
                p_best[j] ← particle[j]
            if Score(particle[j]) > Score(g_best):
                g_best ← particle[j]

return g_best

Algorithm Comparison

Feature GA SA Tabu GRASP ACO PSO
Type Population Single solution Single solution Multi-start Population Population
Memory No No Tabu list No Pheromone Personal/Global best
Language Python C++ C++ C++ Python Python
Parallelization Yes (threads) No No No No No
Escape mechanism Crossover Accept worse Tabu restriction Restart Pheromone diversity Swarm influence

Choosing an Algorithm

For quick results: GRASP or SA (fast construction/iteration)

For best quality (with more time): GA or ACO

For balance: Tabu Search or PSO

For large instances: C++ implementations (SA, Tabu, GRASP) are faster