Superposition

Organising volunteer logistics with quantum computing

Comment

Inspiration

While talking to some of the founding members of the charity we selected (Children of Adam), we learnt that the organisers face lots of challenges whilst trying to effectively coordinate volunteers to collect and deliver donations. The charity doesn't have sufficient central storage due to high London costs, so volunteers often have to store donations in their trunks and car.

When donations need to be taken to a distribution point, logistics are often decided ad hoc over a WhatsApp group chat, which leaves a lot to be desired in terms of organisation and efficiency. This means that, sometimes, members who are allocated to the wrong delivery can spend hours moving goods in an inefficient way.

What it does

Superposition relies on a simple method of volunteer organisation - the auction. Whenever a shipment is required, we notify all of the volunteers asking for availability. We then algorithmically select a volunteer or volunteers to make the delivery based on their distance from the pick-up point and their "Karma" (a measure of how many deliveries they've made recently, to ensure that we don't overload the most eager volunteers).

To make the most out of each volunteer's trip, we calculate an optimal path for them to deliver their donations. As the volunteers often store some of the donations in their car, we can effectively treat them as vehicles in an instance of the Heterogeneous Vehicle Routing Problem (HVRP). We solve a slightly harder version of the HVRP due to the additional constraints such as timing of deliveries and capacity of each vehicle.

We solve the HVRP in two ways:

  1. We use a pick up and drop off approach where we use heuristics to greedily match volunteers based on the distance matrix from the auction and demand modelling.

  2. For our hybrid quantum-classical approach, we modified an existing QAOA (Quantum Approximate Optimisation Algorithm) approach to the heterogeneous Vehicle Routing Problem to account for the varying sizes of aid and capacities of volunteer cars. Using an Ising Hamiltonian, we described the initial problem and combined this with a Pauli-X Mixer Hamiltonian to traverse the entire solution space. We used the IBM Quantum Cloud to run our quantum estimator on a real 156 qubit IBM machine.

How we built it

Exploration has been absolutely essential to this project. After a brief period of learning about the tools we wanted to use, the best way to build was to dive right into making a functional prototype, starting from the database and building out from there. Using artificial intelligence has allowed us to turbocharge our productivity and get our project to a functional state in less than a day.

The frontend has been built from a reliable foundation, that is, hosting a React page on a Raspberry Pi. This ensures consistent support, the ability to use an agentic workflow, and the possibility of porting our tool to other platforms in the future.

We've used IBM's Quantum Cloud to find efficient solutions to the Vehicle Routing Problem in a small amount of time, allowing our software to run with very little delay from a driver's perspective.

Challenges we ran into

As with any hackathon project, final integration has been a challenge, but good practices with regards to the interconnect between parts of the program has allowed us to really get the most out of every part of the system.

Project management during a hackathon is always tough, but we were able to make a lot of the time during the night count.

Accomplishments that we're proud of

We're particularly happy about being able to use IBM's Quantum Cloud to implement some quantum computing techniques. This helps a lot with our HVRP solution (we also have a classical implementation due to the costs inherent with using cloud compute). Also, the lack of error correction or mitigation from the remote quantum computer can mean that simulating the qubits locally often yields better results.

What we learned

A lot of the team spent the 24 hours at ICHack working with tools they had never worked with before, like FastAPI and ORMs around SQL databases. AI was really useful for helping us produce production-ready code quickly and of a good quality.

What's next for Superposition

Hopefully, Superposition is in a position where it's relatively extensible. There are features we'd love to add, like porting to mobile, improving notifications, and providing a live navigation view for drivers to close the gap between Superposition and software like Uber from other industries.

We'd also love to see if and how Superposition gets used in real communities so we can work to make it even better as a public good.

Share this project:

Updates