With Kaan Karamete, Matt Brown, Kyle Sutton, and Chad Meley

About The Project

The ‘traveling salesperson’ problem is one of the most common Graph problems and has numerous implementations. In the practice, however, problems are much more complicated. In the world of logistics, a more realistic setup is typically the Multiple Supply Demand Chain Optimization (MSDO), where there are multiple sources and sinks and we’re looking for the most optimal delivery routes.

To demonstrate Multiple Supply Demand Chain Optimization (MSDO) with an immediate challenge we face globally, we’ve modeled the challenge of vaccine donations. The US has excess vaccine supply which expires over time. If supply is expiring, it is better to donate it abroad before expiration, as quickly as possible. The White House has been doing this. But can it be done more efficiently?

This is a complex problem:

• We have multiple supply sites (each state or region) which can feed into major international airports
• We have multiple demand sites (many nations), many of which desperately require more vaccine supply
• We have time constraints since accumulation, transport, and distribution need to be faster than expiration timelines
• Everything above is dynamic — the supply and demand constantly changes with broad usage and infection trends

We have a Multiple Supply Demand Chain Optimization (MSDO) problem! We’ve modeled the supply, demand, routes, and have everything ready to run on a database (to respond to daily changes in global supply and demand.)

The setup documentation can be seen in this Supply Chain Optimization Example in Python

It will be more instructive to run it yourself with the Kinetica Developer Edition or on Kinetica Cloud on Azure

Getting Started

Import from GitHub:

	git clone git@github.com:kineticadb/community-vaccines.git
	cd community-vaccines

Set up python dependencies:

	pip install -r requirements.txt

Set up Kinetica Developer Edition or Kinetica Cloud and export your credentials as environment variables. The Jupyter notebook will lead you from start to finish!

	jupyter notebook

Results

Quick Test Run: Single Source –> Multiple Destinations

You can see some results below, but we encourage you to run this yourself and tune the optimization per your liking. The best way is to run the Jupyter Notebook https://github.com/kineticadb/community-vaccines/blob/master/start-here.ipynb Finally, we plot out the full route we would use for the round-trip:

Incremental Improvement: Two Sources –> Multiple Destinations

This is good, but lets continue to refine this. We can add a second departure hub in the US to route vaccine supply from the south, lets set up both IAD (Washington Dulles Airport) and DFW (Dallas Fort Worth Airport.) There are a lot of possibilities here, and you can customize this any way you wish — the best way is to run the Jupyter Notebook https://github.com/kineticadb/community-vaccines/blob/master/start-here.ipynb

Taking This Further

Real life is complex. To make predictions or decisions, we create models to represent reality the best we can — balancing trade-offs between correctness with complexity. So far, we’ve made a number of simplifying assumptions, but we can continue to refine the model to introduce more features and address nuances. Some reasonable next steps would be:

• Start with the working Jupyter Notebook and refine iteratively
• Come up with a more advanced supply model using CDC data but with more nuance around vaccine expirations, expected usage before expiration, etc. (change the SQL view vaccine_supply_usa)
• Come up with a more advanced demand model using OWID data, but with your thoughts on prioritization approaches — do we prioritize the elderly population (more at risk), or prioritize the young (more likely to be outside and spread disease), or prioritize countries with the most deaths, or prioritize the countries with the least access to vaccination? (change the SQL view vaccine_demand_intl)
• Add several more regional US centers, perhaps one for the midwest (Chicago ORD) and one for the west (San Francisco SFO). We have references to all the US airports, and you can use geodesic distance with SQL
• Consider that multi-hop drop-offs themselves require time, and thus, consider how many days to expiration are required on vaccines beyond which we should avoid transporting them

Contact Us

• https://www.kinetica.com/contact/
• We’re a global team, and you can reach us on Slack

Data Sources

• Daily Vaccine Distribution Data (US) by the CDC
• Global COVID Statistics from Our World in Data

References

1. Travelling Salesperson Problem
2. White House Fact Sheet: President Biden Announces Major Milestone in Administration’s Global Vaccination Efforts: More Than 100 Million U.S. COVID-⁠19 Vaccine Doses Donated and Shipped Abroad
3. Multiple Supply Demand Chain Optimization (MSDO)
4. YouTube: A short introduction to graph network analytics
5. YouTube: An overview of graph network analysis with Kinetica