|Gatecrash> - vehicle routing problem

Inspiration

emergency services are already stretched thin. ambulance dispatchers, food bank drivers, search and rescue crews: they're all solving some version of the same problem every single day: given a set of stops, what's the fastest way to hit all of them and get back? in an increasingly overpopulated world, that problem only gets harder. i wanted to know whether quantum computing had anything real to say about it, outside of the usual drug discovery pitch.

What it does

gatecrash solves the Vehicle Routing Problem using a time-indexed QUBO (Quadratic Unconstrained Binary Optimization) encoded for QAOA (Quantum Approximate Optimization Algorithm) and runs it against a classical greedy baseline in real time. you drop pins on a map, hit run, and both solvers race on the same distance matrix. the UI shows route distance, CO2 estimate, and compute time for each — side by side, no hidden numbers.

How I built it

Python backend using FastAPI to serve the solver results to a vanilla JS + Leaflet frontend. the quantum side runs on Qiskit 1.4.2 with the Aer statevector simulator. COBYLA handles the variational parameter optimization. no frameworks, no build step: just four Python files and a frontend that loads straight from the browser.

Challenges I ran into

the first QUBO formulation used edge-indicator variables: one binary variable per directed edge in the graph. the problem was that subtour elimination required additional constraints to prevent the solver from returning disconnected cycles that satisfied all the degree constraints but weren't actually a single Hamiltonian path. adding those constraints would have blown up the qubit count fast.

the fix was switching to a time-indexed formulation. instead of asking "is this edge used?", the new variables ask "is stop i the t-th visit?". two simple constraints — each stop visited exactly once, each time slot holding one stop — force the solution into a permutation matrix by construction. subtours become structurally impossible. no extra constraints needed, fewer qubits, and the solver actually works.

Accomplishments I'm proud of

i came into this with limited quantum knowledge but a pretty solid grasp of optimization. being able to bridge those two things: take a classical combinatorial problem i understood well and figure out how to encode it correctly in a quantum form, is something i'm genuinely proud of. more than the technical side though, it's the application that matters to me. the idea that better routing could help emergency services or food banks do their jobs more effectively is what made this feel worth building.

What I learned

quantum is hard. optimization is easier, at least for me. i leaned into what i already knew about mathematical modeling and built out the optimization formulation mostly independently. when it came to the quantum encoding specifically: the circuit structure, the Hamiltonian construction, the parameter optimization, that's where i relied more heavily on the internet and AI tools to fill in the gaps. it was a good lesson in knowing where your strengths are and not pretending otherwise.

What's next for gatecrash

right now the solver works on straight-line distances between coordinates. the obvious next step is routing on actual road networks, real paths with real travel times, one-way streets, bridges, detours. integrating something like the OpenStreetMap routing API would make the benchmark numbers mean something in the real world rather than just in euclidean space. after that, scaling to larger n as quantum hardware improves is the longer-term goal. the encoding is already there, it just needs hardware that can hold more coherent qubits.

Built With

• fastapi
• python
• qiskit