Transportation Network Analysis with Graph Theory

Use graph theory to optimize the road transportation network of a retail company

(Image by Author)

Road transportation is a major cost for retailers.

Are you looking to reduce these costs and improve your network’s efficiency?

Discover how Graph Theory with Python can help you visualize your transportation network and collaborate with your team to design optimal routing plans.

Objective

Build graphical representations of a road transportation network to support optimization studies.

Introduction

For a retailer, road transportation to deliver stores represents a major part of the logistics costs.

Companies often conduct route planning optimization studies to reduce these costs and improve the efficiency of their network.

It requires collaboration between continuous improvement engineers and the transportation teams managing daily operations.

In this article, we will use Graph Theory to design visual representations of a transportation network to support this collaboration and facilitate solution design.

💌 New articles straight in your inbox for free: Newsletter
📘 Your complete guide for Supply Chain Analytics: Analytics Cheat Sheet

SUMMARY
I. Distribution Network
Distribution centre of a retail company with 54 stores
II. Problem Statement
Optimization of the route planning to reduce transportation costs
1. Exploratory Data Analysis
1 year of deliveries to 50 stores
2. Multi-Store Delivery 
Use dedicated trucks to deliver several stores 
III. Solution using Graph Visualization
1. Visualization using the Graph Theory 
What are the stores that are delivered together?
2. Challenge the current routing 
Collaborate with the Transportation Planner to expand the routes
IV. Conclusion & Next Steps
1. Generative AI: Supply Chain Control Tower Powered by GPT
2. Next Steps

If you prefer, you can watch the YouTube video version

I. Optimizing Your Retail Company’s Distribution Network with Transportation Network Analysis

1. Distribution Network Overview

As a continuous improvement engineer of a retail company, you are in charge of reengineering warehousing and transportation operations.

In your scope, you have a major distribution centre in Shanghai (China) that delivers 54 hypermarkets.

Distribution Network of your Retail Company — (Image by Author)

2. Delivery by Truck

These stores, located in four different provinces, are delivered using 3rd party transportation service providers.

They provide trucks with three different capacities (3.5 Tons, 5 Tons, and 8 Tons).

(Image by Author)

Based on the routing and loading plans designed by the transportation planners, a dedicated truck is allocated to deliver stores.

3. Loading Plan Example

Let’s imagine a scenario with three stores in Shanghai that ordered 30 pallets (5 T).

• The warehouse team prepares the orders and put the cartons on pallets
• The transport planner decides to deliver these three stores with a single 5T truck
• Pallets are loaded into the truck

(Image by Author)

You are invoiced by the carrier using a price per truck (Rmb/Truck) based on the first city delivered on the route.

(Image by Author)

For the delivery of these three stores in Shanghai
Cost = 650 (Rmb)

The role of your transportation planning team is to design routes to ensure that your trucks are full when they leave the warehouse.

(Image by Author)

Therefore, they avoid as many single-store routes as possible to maximize the filling rate.

If you want to know more about the FTL Transportation

(Video by Author)

Samir Saci

II. Problem Statement

1. Objective

Your objective is to reduce the total cost of transportation.

Insights: Cost per Ton
A major lever of optimization is the size of trucks.

(Image by Author)

If you increase the average size of the trucks you reduce the overall cost per ton. A good method is to deliver more stores per route.

2. Analyzing Shipment Data

You have 12 months of shipments to understand the current routing.

(Image by Author)

Number of shipments per store
Most of the deliveries are in Shanghai and the neighbouring province of Jiangsu.

(Image by Author)

Trucks size
Except in Shanghai, where you have large hypermarkets driving a large part of the demand, the other provinces have stores of relatively the same size.

(Image by Author)

Number of routes per truck size
Except in January, the peak season before the Chinese New Year, most routes are delivered using small trucks.

Samir Saci

💡 Follow me on Medium for more articles related to 🏭 Supply Chain Analytics, 🌳 Sustainability and 🕜 Productivity.

You can find the source code with dummy data in my Github (Follow me :D) repository: Link

III. Solution using Graph Visualization

The objective is to design a new transportation plan to increase the average size of trucks by delivering more stores per route.

Constraints

Because of operational limitations, you need to respect the constraints below

• Delivery Time Window: Stores can receive products only at a certain time of the day
• Road Restrictions: Large trucks are forbidden on some roads
• Unloading Conditions: Some stores need to be delivered first

Collaboration with Graph Visualization

Because of these operational constraints, you cannot perform this analysis alone.

It is key to collaborate with the transportation teams that have experience in managing route planning daily.

Solution: Graph Theory
A graph is a structure that contains nodes (stores), and each related pair of nodes is called an edge.

(Image by Author)

An edge of two stores means that these stores have been delivered together at least once.

For instance, store 2 has been delivered with store 3, store 5 and store 1.

Question
With the current routing, which stores are delivered together?

3. Challenge the current routing

Let’s have a look at the results with the current routing.

Full-year Shipment Analysis

(Image by Author)

You can find different types of clusters

• Type 1: stores are all interconnected and usually represent a single route (it is good to group several stores in one route)
• Type 2: stores are sequentially connected, creating a chain
• Type 3: 1 store is connected to all the other stores

This visual can support discussions with the transportation team

• Why do we have 2 isolated stores in Zhejiang?
• Can we increase the average truck size if we group the two isolated pairs of Shanghai?
• Can we have more type 1 clusters?

Question
What is the impact of truck size?

Analysis of Small Truck Fleet

Our main issue is the high proportion of small trucks in our fleet.

Network Graph of 3.5T trucks

(Image by Author)

There are fewer interconnections for these routes. There are no major clusters of interconnected nodes.

Average Truck Size
The observation is confirmed by looking at the average number of deliveries per route for each truck size.

(Image by Author)

Except during the Chinese New Year peak period, you can see that large trucks have more deliveries per route.

Question
What is the difference between the lowest vs. highest ratio of stores per route?

(Image by Author)

For the best scenario (left), stores are highly interconnected (up to 4 connections). The contrast is clear with the other network, which is highly fragmented.

IV. Conclusion & Next Steps

Generative AI: Supply Chain Control Tower Powered by GPT

In November 2022, OpenAI released the first version of ChatGPT.

Generative AI became the opportunity to improve the user experience of any analytics products using Large Language Models.

Supply Chain Control Tower Agent with LangChain SQL Agent [Article Link] — (Image by Author)

In this article, I share my explorative journey of LLMs used to boost Supply Chain Analytics.

“The Supply Chain Analyst” — (Image by Author)

The Supply Chain Analyst” is a custom GPT agent designed to automate supply chain analytics tasks and interact with users using natural language.

I have also shared a case study where I designed with LangChain a smart agent connected to a TMS database that can answer operational questions.

High-Level Overview of the Solution — (Image by Author)

More details in these two articles,

Leveraging LLMs with LangChain for Supply Chain Analytics — A Control Tower Powered by GPT

Create GPTs to Automate Supply Chain Analytics

A Collaborative Tool

This tool visually represents the distribution network to support collaborative work between you and the transportation teams.

Sitting at the same table to find a solution ensures a smooth implementation as the planning teams have been involved in the design.

Based on your analysis, you can propose potential improvements (grouping additional stores, merging routes) and assess the operational feasibility with the teams.

Beyond Profit, Reduce the Environmental Footprint

The initial objective was to improve the truck loading rate to reduce the transportation cost per ton.

However, the positive side effect of improving the efficiency of your planning is the reduction of CO2 emissions.

CO2 Emissions by Transportation Mode — (Image by Author)

As the demand for transparency in emissions reductions from investors and customers has grown over the years, it is important to quantify the savings in emissions cuts.

There are analytics tools that can help you quantify your initiative's contribution to your company's green transformation.

For more details,

• Supply Chain Sustainability Reporting with Python, Samir Saci, Towards Data Science

Supply Chain Sustainability Reporting with Python

• Data Analytics for Supply Chain Sustainability, Samir Saci, Towards Data Science

Data Analytics for Supply Chain Sustainability

• Green Inventory Management — Case Study, Samir Saci, Towards Data Science

Green Inventory Management — Case Study

About Me

Let’s connect on Linkedin and Twitter, I am a Supply Chain Engineer using data analytics to improve logistics operations and reduce costs.

If you are interested in Data Analytics and Supply Chain, have a look at my website

Samir Saci | Data Science & Productivity

References

• Networkx, Network Analysis with Python, Link
• “4 Impacting Projects to Start Your Data Science for Supply Chain Journey”, Towards Data Science, Samir Saci
• “Road Transportation Network Visualization”, Towards Data Science, Samir Saci