TL;DR
This paper applies a hybrid machine learning and evolutionary algorithm approach called COIL to solve a critical real-world problem: scheduling last-mile delivery robots under strict human-monitoring constraints. By using a Variational Autoencoder (VAE) to map out a "safe" search space, the proposed method consistently finds valid schedules where standard Genetic Algorithms fail, while running 10% faster during daily re-optimization.
What Problem Does This Paper Address?
Last-mile delivery using autonomous robots is an eco-friendly and labor-saving alternative to traditional delivery vans. However, in real-world deployments (such as those trialed by the paper's industry partner, Panasonic), these robots aren't entirely unsupervised; human operators must remotely monitor them to intervene during tricky situations, like navigating crowded sidewalks.
Because human attention is a finite resource, there is a strict safety constraint: the number of robots operating simultaneously cannot exceed a specific threshold ($RT$). This creates a challenging optimization problem: how do you schedule robot start times and durations to maximize fulfilled customer deliveries without ever exceeding the safe monitoring limit? Standard optimization techniques struggle here because the valid search space is highly constrained and fractured.
Methods
The authors tackle this by adapting COIL (Constrained Optimization in Learned Latent Space), a hybrid framework combining unsupervised machine learning with evolutionary computation.
Instead of searching the raw, highly invalid problem space directly, COIL operates in three steps:
- Dataset Generation: A simple data-generating Genetic Algorithm (GA) runs offline to find a large set of diverse robot schedules that strictly satisfy the safety constraint (ignoring the delivery objective for now).
- Latent Space Learning: A Variational Autoencoder (VAE) is trained on this dataset. The VAE learns to compress these high-dimensional valid schedules into a lower-dimensional, continuous latent space ($\bar{z}$).
- Optimization: A second GA searches within this learned latent space to maximize the number of fulfilled delivery requests. Because the VAE's decoder maps latent vectors back to valid physical schedules, the GA is heavily biased toward exploring only safe solutions.
The authors compare COIL against a standard baseline GA that utilizes tournament selection to balance constraint satisfaction and objective maximization in the raw search space.
Datasets
The paper evaluates the algorithms using synthetic problem instances modeled after real-world parameters from Panasonic's trials:
- Customer Requests: Sets of 120 to 240 random delivery requests with durations ranging from 60 to 360 minutes, distributed across a 12-hour working day.
- Training Data: Datasets of valid schedules containing $2,500$, $5,000$, $7,500$, or $10,000$ unique data points generated by the offline GA to train the VAE.
Key Insights and Ideas
- Standard GAs "Cheat" on Hard Constraints: When safety constraints are tight, standard GAs fail completely. They maximize the delivery objective by simply ignoring the safety threshold, producing schedules that are unusable in the real world.
- The Dimensionality "Sweet Spot": The authors discovered that reducing the number of latent variables ($maxlv$) below the original problem dimensionality actually improves optimization performance and VAE training speed. However, reducing it too much degrades the VAE's reconstruction quality, revealing a clear performance "sweet spot."
- Latent Spaces Smooth the Search: Searching within a space pre-filtered by a VAE allows the evolutionary algorithm to find high-quality solutions rapidly without wasting evaluations on invalid regions.
Key Results
- Constraint Satisfaction: COIL successfully found valid solutions (zero safety constraints broken) across all tested design variations. In contrast, the baseline GA failed to find a single valid solution in difficult scenarios, averaging 44.7 constraint violations per run.
- Execution Speed: While COIL requires an intensive offline pre-computation step to train the VAE, its online daily optimization phase is 10% faster than the baseline GA (1.81 minutes vs 1.89 minutes for 100 runs). This makes it highly practical for daily morning rescheduling as new customer orders arrive.
Limitations and Future Work
- High Offline Overhead: Generating the initial dataset of valid solutions is computationally expensive, taking up to 25.8 hours for 10,000 data points in the most constrained scenarios.
- Simplified Simulation: The current model assumes fixed robot speeds and relies on a basic first-come, first-served scheduling heuristic to allocate requests to individual robots.
- Future Directions: The authors plan to explore advanced quality-diversity algorithms like MAP-Elites to accelerate the offline data generation phase, and intend to integrate more complex real-world variables, such as varying robot speeds and advanced fleet schedulers.
Summary updated