Package Delivery Routing System
VRP-TW solver where one GA co-evolves truck loading and delivery sequence simultaneously — no two-pass split.
view on github ↗The VRP-TW shares two interwoven problems: which packages go on which truck (assignment) and in what order each truck delivers them (sequencing). Most implementations solve these in two separate passes. The WGU capstone that preceded this did worse — it hard-coded package-to-truck assignments written directly into source, a fixed 40-package / 3-truck assumption, and no tolerance for variable constraints. Any change required a developer and a redeploy.
A configurable GA that solves assignment and sequencing in a single chromosome, letting the two decisions co-evolve and inform each other across generations. Packages are procedurally generated per run with configurable deadline, delay, and refrigeration distributions. A bundle pre-processing step groups packages by address and validates constraint compatibility before the GA starts, reducing search space without losing solution quality. The fitness function scores five weighted objectives including a gradient deadline penalty. All major parameters are surfaced through a CLI; no source changes required to run different scenarios. Post-run, the CLI supports package status lookup by ID or address at any timestamp, reconstructed from simulation output.
- → Sentinel chromosome: negative integers act as truck boundaries in a flat array — a single crossover or mutation can affect both which truck a package goes on and the delivery order within that truck
- → Sentinel shift mutation moves a truck boundary left or right by one position — specifically prevents the initial capacity distribution from becoming permanent across generations
- → Gradient deadline penalty (minutes_late × 10) creates a smooth fitness landscape so the GA distinguishes a 5-minute miss from a 5-hour miss; binary pass/fail flattens the landscape and stalls convergence
- → Bundle pre-processing validates constraint compatibility before the GA runs: a package with a 9:30 AM availability window cannot be bundled with one that has a 9:00 AM deadline; 45-minute drive-time buffer applied
- → Adaptive mutation: rate doubles after 50 stagnant generations to escape local optima, resets on meaningful improvement (>0.1% threshold prevents resetting on marginal gains in flat landscapes)
- → Capacity-aware population seeding distributes bundles evenly across truck segments from generation zero — early populations are feasible rather than requiring the GA to spend generations on repair
- → Early termination after 500 stagnant generations enables convergence mode: set generations to a large number and let the algorithm run until done
Two bugs stalled performance for a while. First: Truck objects were maintaining state across fitness evaluations. Departure time set in generation N carried into generation N+1, corrupting the simulation for every subsequent chromosome. The fix was reinitializing truck state at the start of each route evaluation in fitness(). Second: the original sentinel encoding used strings ('|1|', '|2|', ...), requiring isinstance(gene, str) on every gene in every fitness call across thousands of generations. Replacing sentinels with negative integers (checking gene < 0) is the fastest comparison available in Python, allowing for a meaningful gain of efficiency in a tight hot loop.