Simulated Annealing Schedule Optimizer
Mar 2025Advanced metaheuristic optimization using Simulated Annealing to assign orders to 20 students while maximizing profit, respecting delivery time windows and student eligibility constraints. Complex real-world logistics problem solving with sophisticated algorithmic approaches.
Student Consulting Services B.V needs to assign delivery orders to 20 consultants to maximize profit. Constraints: (1) Max shift time: 8 hours per student, (2) Orders have location-dependent driving times, (3) Only eligible students can take specific orders, (4) Profit = order value - driving + work time. Initial solutions yield €5,000-5,500. Goal: optimize using Simulated Annealing.
Local Search Operators (4 types):
• Insert Order (35%) — Add unassigned order to student's route if feasible
• Remove Order (10%) — Remove assigned order for reassignment
• Move Order (20%) — Transfer order between students
• Two-Opt Swap (35%) — Reverse route segment to minimize driving time
Cooling Schedule: Initial temperature 1,000,000 → cooling rate 0.999999 (very gradual) ensures extensive exploration of solution space before convergence. Temperature-dependent acceptance probability prevents getting stuck in local optima.
Initial experiments: Cooling rate 0.01 yielded only €5,379
Tuned parameters: Cooling rate 0.999999 achieved €8,974.05
Improvement: 66.8% gain through slower cooling (better exploration)
Verification: 121,500 iterations/second × 150 seconds = 18M iterations total. All constraints satisfied; solution verified as valid.
import java.util.*;
import java.io.File;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;
public class SimulatedAnnealingSolver {
// Constants
private static final int MAX_SHIFT_TIME = 8 * 60 * 60;
private static final int HQ_NODE = 251;
private static final int NUM_STUDENTS = 20;
// Data structures
private static int[][] drivingTimes;
private static Order[] orders;
private static int numOrders;
private static Solution bestSolution;
// Parameters for SA
private static final double INITIAL_TEMPERATURE = 1000000;
private static final double MIN_TEMPERATURE = 1e-8;
private static final double COOLING_RATE = 0.999999;
private static final int MAX_RUNTIME_SECONDS = 150;
// Tunable parameters for operator selection
private static final double[] OPERATOR_WEIGHTS = {0.35, 0.1, 0.2, 0.35};
private static double[] cumulativeWeights;
// Statistics tracking
private static long acceptedMoves = 0;
private static long rejectedMoves = 0;
static class Order {
int id, node, duration, profit;
boolean[] eligibleStudents;
int[] drivingTimesFromHQ;
int[] drivingTimesToHQ;
Order(int id, int node, int duration, int profit, boolean[] eligibleStudents) {
this.id = id;
this.node = node;
this.duration = duration;
this.profit = profit;
this.eligibleStudents = eligibleStudents;
}
void precomputeDrivingTimes() {
drivingTimesFromHQ = new int[numOrders + 1];
drivingTimesToHQ = new int[numOrders + 1];
drivingTimesFromHQ[numOrders] = drivingTimes[HQ_NODE][node];
drivingTimesToHQ[numOrders] = drivingTimes[node][HQ_NODE];
for (int i = 0; i < numOrders; i++) {
drivingTimesFromHQ[i] = drivingTimes[HQ_NODE][orders[i].node];
drivingTimesToHQ[i] = drivingTimes[orders[i].node][HQ_NODE];
}
}
}
static class Solution {
List<Integer>[] routes;
Set<Integer> unassignedOrders;
double profit;
int[] routeTimes;
int[] routeDrivingTimes;
int[] routeWorkTimes;
int[] routeProfits;
@SuppressWarnings("unchecked")
public Solution() {
routes = new ArrayList[NUM_STUDENTS];
for (int i = 0; i < NUM_STUDENTS; i++) {
routes[i] = new ArrayList<>();
}
unassignedOrders = new HashSet<>();
routeTimes = new int[NUM_STUDENTS];
routeDrivingTimes = new int[NUM_STUDENTS];
routeWorkTimes = new int[NUM_STUDENTS];
routeProfits = new int[NUM_STUDENTS];
profit = 0;
}
public Solution copy() {
Solution copy = new Solution();
for (int i = 0; i < NUM_STUDENTS; i++) {
copy.routes[i] = new ArrayList<>(this.routes[i]);
copy.routeTimes[i] = this.routeTimes[i];
copy.routeDrivingTimes[i] = this.routeDrivingTimes[i];
copy.routeWorkTimes[i] = this.routeWorkTimes[i];
copy.routeProfits[i] = this.routeProfits[i];
}
copy.unassignedOrders = new HashSet<>(this.unassignedOrders);
copy.profit = this.profit;
return copy;
}
private void calculateRouteMetrics(int student) {
int drivingTime = 0;
int workTime = 0;
int routeProfit = 0;
List<Integer> route = routes[student];
if (route.isEmpty()) {
routeDrivingTimes[student] = 0;
routeWorkTimes[student] = 0;
routeProfits[student] = 0;
routeTimes[student] = 0;
return;
}
int currentNode = HQ_NODE;
for (int i = 0; i < route.size(); i++) {
int orderIndex = route.get(i);
Order order = orders[orderIndex];
drivingTime += drivingTimes[currentNode][order.node];
workTime += order.duration;
routeProfit += order.profit;
currentNode = order.node;
}
drivingTime += drivingTimes[currentNode][HQ_NODE];
routeDrivingTimes[student] = drivingTime;
routeWorkTimes[student] = workTime;
routeProfits[student] = routeProfit;
routeTimes[student] = drivingTime + workTime;
}
public void recalculateAllMetrics() {
profit = 0;
for (int i = 0; i < NUM_STUDENTS; i++) {
calculateRouteMetrics(i);
profit += routeProfits[i] - routeTimes[i];
}
}
public void updateMetricsAfterInsert(int student, int orderIndex, int position) {
calculateRouteMetrics(student);
profit = 0;
for (int i = 0; i < NUM_STUDENTS; i++) {
profit += routeProfits[i] - routeTimes[i];
}
}
public void updateMetricsAfterRemove(int student) {
calculateRouteMetrics(student);
profit = 0;
for (int i = 0; i < NUM_STUDENTS; i++) {
profit += routeProfits[i] - routeTimes[i];
}
}
public boolean isRouteFeasible(int student) {
return routeTimes[student] <= MAX_SHIFT_TIME;
}
public boolean verify() {
for (int i = 0; i < NUM_STUDENTS; i++) {
if (routeTimes[i] > MAX_SHIFT_TIME) {
return false;
}
}
boolean[] assigned = new boolean[numOrders];
for (int i = 0; i < NUM_STUDENTS; i++) {
for (int orderIndex : routes[i]) {
if (assigned[orderIndex]) return false;
assigned[orderIndex] = true;
}
}
for (int i = 0; i < NUM_STUDENTS; i++) {
for (int orderIndex : routes[i]) {
if (!orders[orderIndex].eligibleStudents[i]) return false;
}
}
return true;
}
}
public static void main(String[] args) throws Exception {
readDrivingTimes("drivingtimes.txt");
readOrders("orders.txt");
precomputeOperatorWeights();
Solution currentSolution = initializeSolution();
currentSolution.recalculateAllMetrics();
bestSolution = currentSolution.copy();
double currentProfit = currentSolution.profit;
double bestProfit = bestSolution.profit;
double temperature = INITIAL_TEMPERATURE;
long startTime = System.currentTimeMillis();
long endTime = startTime + MAX_RUNTIME_SECONDS * 1000;
int iterations = 0;
ThreadLocalRandom random = ThreadLocalRandom.current();
System.out.println("Starting simulated annealing...");
while (System.currentTimeMillis() < endTime) {
iterations++;
Solution neighborSolution = applyRandomOperator(currentSolution);
double delta = neighborSolution.profit - currentProfit;
boolean accept = false;
if (delta > 0) {
accept = true;
} else if (temperature > 0) {
double acceptanceProbability = Math.exp(delta / temperature);
accept = random.nextDouble() < acceptanceProbability;
}
if (accept) {
acceptedMoves++;
currentSolution = neighborSolution;
currentProfit = neighborProfit;
if (currentProfit > bestProfit) {
bestSolution = currentSolution.copy();
bestProfit = currentProfit;
}
} else {
rejectedMoves++;
}
temperature *= COOLING_RATE;
}
System.out.println("Simulated annealing completed:");
System.out.println("Total iterations: " + iterations);
System.out.println("Best profit: " + (bestProfit / 60.0) + " euros");
System.out.println("Solution valid: " + bestSolution.verify());
}
}A7 — Profitable Printing
Mar 2024Dynamic programming for optimal book partition. Determine how to split n chapters into contiguous books to maximize total profit, where each book partition has a predetermined profit value P[i,j].
A printing company publishes a story with n chapters. Publishing chapters i...j as one book yields profit P[i,j]. Find the partitioning that maximizes total profit.
public static int calculateMaxProfit(int[][] profit, int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
// Dynamic programming loop
for (int i = 1; i <= n; i++) {
// Consider alternatives for the last book
for (int j = 1; j <= i; j++) {
// j = first chapter in the last book (chapters j...i)
// Total profit = profit from chapters 1...j-1 + profit from book j...i
dp[i] = Math.max(dp[i], dp[j - 1] + profit[j][i]);
}
}
return dp[n];
}A5 — Space Tourism
Feb 20240/1 Knapsack problem for spacecraft payload optimization. Select tourists to maximize revenue while respecting weight capacity constraints.
// Greedy approach: select lightest passengers first
Arrays.sort(tourists);
int totalRevenue = 0;
int currentWeight = 0;
List<Integer> selectedPassengers = new ArrayList<>();
for (Tourist t : tourists) {
if (currentWeight + t.weight <= M) {
currentWeight += t.weight;
totalRevenue += t.price;
selectedPassengers.add(t.id);
}
}B4 — Project Delays
Feb 2024Topological sort with task scheduling. Find the minimum completion time for all tasks given their durations and dependencies using Kahn's algorithm.
private static int minimumCompletionTime(Task[] tasks,
List<Integer> completionOrder, int n) {
Queue<Integer> queue = new LinkedList<>();
int[] taskCompletionTime = new int[n + 1];
// Kahn's algorithm: start with tasks having no prerequisites
for (int i = 1; i <= n; i++) {
if (tasks[i].prerequisites == 0) {
queue.add(i);
taskCompletionTime[i] = tasks[i].duration;
}
}
int countCompleted = 0;
while (!queue.isEmpty()) {
int currentTask = queue.poll();
countCompleted++;
completionOrder.add(currentTask);
for (int nextTask : tasks[currentTask].nextTasks) {
taskCompletionTime[nextTask] = Math.max(
taskCompletionTime[nextTask],
taskCompletionTime[currentTask] + tasks[nextTask].duration);
tasks[nextTask].prerequisites--;
if (tasks[nextTask].prerequisites == 0) {
queue.add(nextTask);
}
}
}
if (countCompleted != n) return -1;
return Arrays.stream(taskCompletionTime).max().getAsInt();
}