Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem

1. 1
   Deconstruct Your Problem into Bilevel Decisions

   Identify a complex optimization problem with interdependent decisions. Structure it into an 'upper level' (e.g., strategic routing) and a 'lower level' (e.g., tactical charging or resource allocation) where upper-level decisions influence the lower level.
2. 2
   Formulate Objectives for Each Level

   Define the primary objective function and decision variables for your upper level. Then, formulate the secondary objective and decision variables for the lower level, considering their dependency on the upper-level choices.
3. 3
   Implement Late Acceptance Hill Climbing (LAHC)

   Integrate LAHC as the core metaheuristic search algorithm. This involves defining a neighborhood structure, a cost function, and the LAHC acceptance list logic to explore the solution space effectively, particularly at the upper level.
4. 4
   Design a Surrogate Objective Function

   Develop a simplified or approximate model (surrogate function) to quickly evaluate the complex interactions between upper and lower-level decisions. This allows for faster exploration without needing full, computationally expensive simulations at every step.
5. 5
   Implement Dynamic Decision Management

   Create a mechanism to dynamically switch between optimizing decisions separately (e.g., optimize routing, then optimize charging based on routes) and jointly (e.g., optimize both simultaneously) depending on the search stage or problem state.
6. 6
   Iterate and Refine Your Optimization

   Combine the LAHC with the surrogate objective and dynamic decision management. Continuously iterate through the search process, evaluating solutions, updating the acceptance list, and refining parameters until an optimal or near-optimal solution is found.

import random
import math

def objective_function(x):
    """A simple objective function to minimize (e.g., f(x) = x^2)"""
    return x**2

def get_neighbor(current_solution, step_size=0.1):
    """Generate a neighbor solution by adding a random perturbation."""
    return current_solution + (random.random() - 0.5) * step_size * 2

def late_acceptance_hill_climbing(objective_func, initial_solution, max_iterations, list_length, step_size=0.1):
    """Basic implementation of Late Acceptance Hill Climbing (LAHC)."""
    current_solution = initial_solution
    current_cost = objective_func(current_solution)

    # Initialize acceptance list with the initial cost
    acceptance_list = [current_cost] * list_length
    list_index = 0

    best_solution = current_solution
    best_cost = current_cost

    for i in range(max_iterations):
        neighbor_solution = get_neighbor(current_solution, step_size)
        neighbor_cost = objective_func(neighbor_solution)

        # Get the threshold from the acceptance list
        acceptance_threshold = acceptance_list[list_index]

        # Check acceptance criteria (minimization problem: accept if better or within threshold)
        if neighbor_cost <= current_cost or neighbor_cost <= acceptance_threshold:
            current_solution = neighbor_solution
            current_cost = neighbor_cost

        # Update the acceptance list with the cost of the accepted solution (or current if none accepted)
        acceptance_list[list_index] = current_cost
        list_index = (list_index + 1) % list_length

        # Update overall best solution found so far
        if current_cost < best_cost:
            best_solution = current_solution
            best_cost = current_cost

    return best_solution, best_cost

if __name__ == "__main__":
    # Example usage for minimizing f(x) = x^2
    initial_sol = random.uniform(-10, 10) # Start from a random point
    iterations = 10000 # Number of iterations
    la_list_len = 20   # Length of the acceptance list
    step = 0.5         # Step size for generating neighbors

    print(f"Starting LAHC with initial solution: {initial_sol:.2f}")
    best_sol, min_cost = late_acceptance_hill_climbing(
        objective_function, initial_sol, iterations, la_list_len, step
    )
    print(f"LAHC found best solution: {best_sol:.4f} with cost: {min_cost:.4f}")

• Paperarxiv.org