Application of mathematical methods in logistics: using the traveling salesman problem and the auction method from game theory to optimize the selection of transport companies and cargo consolidation points

Introduction

In today's business world, particularly in logistics, minimizing costs and optimizing processes are becoming critical factors for success. This paper provides a detailed analysis of using game theory problems, specifically the auction method and the traveling salesman problem, to select optimal transport companies, determine cargo consolidation points, and calculate overall cost savings.

The auction method from game theory helps solve selection problems where multiple companies (players) compete for a contract. This model maximizes the organizer's benefit by minimizing costs through competitive bids. The traveling salesman problem, on the other hand, optimizes transportation and consolidation routes by minimizing the total distance.

The goal of this paper is to apply these methods for selecting transport companies for freight shipping from suppliers, calculating optimal locations for cargo consolidation, and demonstrating the economic impact based on real freight flow statistics.

Main Body

Theoretical Basis

The Auction Method in Game Theory

The auction method is used when multiple players (transport companies) bid to perform specific tasks (cargo transportation). Each transport company aims to win the contract by offering the lowest price that still allows them to remain profitable. The supplier organizing the auction selects the carrier with the lowest service cost. As a result, all players strive to offer the most competitive conditions. Formally, if we have several carriers offering their prices C_i for transportation from the supplier, the supplier's task is to select the carrier with the minimum C_i.

C_min = min (C₁, C₂, ..., C_n)

The Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) aims to minimize the total path length when visiting all points in a given route. Applying the TSP in logistics allows for the optimization of transportation routes so that carriers can collect goods from suppliers and deliver them to warehouses with minimal transportation costs. The formal statement of the problem is to find the minimal path length L, which connects all points P₁, P₂,...,P_n (supplier cities), such that the path is minimized:

𝐿 _min = min ∑ (𝑑(𝑃_𝑖,𝑃𝑖₊₁))

where 𝑑(𝑃_𝑖,𝑃_𝑖+1) is the distance between two consecutive points on the route.

Problem 1: Optimization of Carrier Selection for Each Supplier

Problem Description: The objective is to minimize the transportation costs of shipping goods from suppliers to consolidation warehouses in China. To achieve this, the optimal carrier for each supplier must be selected based on the transportation rates provided by logistics companies and the distances between supplier cities and consolidation warehouses.

Input Data:

1. List of supplier cities: Shenzhen, Guangzhou, Shanghai, Suzhou, Beijing, Chongqing, Tianjin, Chengdu, Dongguan, Nanjing, Qingdao, Hangzhou, Wuhan, Foshan, Xiamen
2. Consolidation points (warehouses): Shanghai, Qingdao

We have 13 supplier cities and three transport companies, each offering different transportation rates.

Transport companies' rates: (to be specified)

• Northern China includes Beijing, Tianjin, Qingdao.
• Central China includes Shanghai, Suzhou, Nanjing, Hangzhou, Wuhan, Chongqing, Chengdu.
• Southern China includes Shenzhen, Guangzhou, Dongguan, Foshan, Xiamen.

Objective of the Problem 1:

For each supplier, select the carrier that offers the lowest delivery cost to the nearest consolidation warehouse.

Solution to Problem 1:

We have the following:

• 13 suppliers in various cities across China.
• 2 consolidation warehouses: Shanghai and Qingdao.
• 3 transport companies offering different rates across regions (Northern, Central, and Southern China).

We need to:

• Determine the optimal warehouse for consolidating goods from each supplier.
• Select a carrier for each supplier that minimizes costs, using the auction method from game theory.

Part 1: Determining the Optimal Consolidation Warehouse

Step 1: Data Collection

For each supplier, the distances to the nearest warehouses (Shanghai or Qingdao) are determined, after which an auction is held among the carriers. The carrier offering the lowest transportation cost is selected.

Distances between supplier cities and consolidation warehouses (in km): (to be specified)

Step 2: Calculating the Delivery Cost to Each Warehouse

For each supplier, calculate the delivery cost to both warehouses, taking into account the minimum rates for the respective region.

Step 3: Selecting the Optimal Warehouse

Compare the delivery costs to Shanghai and Qingdao, and select the warehouse with the lowest cost for each supplier.

Table 1

Optimal Warehouse for Each Supplier

Here, the cost is calculated based on the minimum rate for the corresponding region.

Part 2: Selecting a Carrier Using the Auction Method from Game Theory

Theoretical Basis

The auction method from game theory models the competitive interaction between players (in this case, transport companies) for the right to provide a service (cargo transportation) at the lowest possible cost to the customer (you).

Players:

Supplier – the organizer of the auction, interested in minimizing their costs.

Transport companies – the participants in the auction, offering their rates.

Supplier's goal:

To select the carrier with the lowest transportation cost.

Transport companies' goal:

To win the contract by offering a competitive price, but not below their cost.

Steps to solve the problem:

1. Collecting information on rates and calculating initial bids

Each transport company provides its rates for transportation based on the region:

2. Calculating the Transportation Cost for Each Supplier and Carrier

• For each supplier, calculate the transportation cost to the selected warehouse for all three companies.

3. Conducting the Auction

• First round: Each company submits its bid (calculated transportation cost).
• Companies' strategy: They may lower their price to a certain level to win the auction but not below their cost price.
• Selecting the winner: The supplier chooses the carrier with the lowest price.

4. Analyzing Results and Making a Decision

• After the auction, the carrier offering the lowest price is selected for each supplier.

Detailed Example of Applying the Auction Method from Game Theory

Supplier from Shenzhen

1. Cost calculation for each carrier:

• Company 1: 1,460 km × $0.11 = $160.60
• Company 2: 1,460 km × $0.12 = $175.20
• Company 3: 1,460 km × $0.09 = $131.40

2. First round of the auction:

• Companies' bids:
  • Company 1: $160.60
  • Company 2: $175.20
  • Company 3: $131.40
• Selecting the winner:
  • Company 3 offers the lowest price ($131.40) and wins the auction.

Table 2

Auction Results for Each Supplier

Auction Results Analysis

• Southern China: Company 3 consistently offers the lowest price due to its low rate in Southern China ($0.09/ton·km).
• Central China: Company 2 wins auctions thanks to its lowest rate ($0.08/ton·km).
• Northern China: Company 1 prevails due to having the lowest rate ($0.07/ton·km).

Transport Companies' Strategies

• Company 1: Focuses on competitive rates in Northern China.
• Company 2: Offers the best rates in Central China, aiming to dominate this market.
• Company 3: Specializes in Southern China with low rates to win auctions in this region.

The Role of Game Theory

• Incomplete Information: Transport companies know their own rates but are unaware of competitors' rates.
• Strategic Behavior: Each company sets its rates to maximize profit while remaining competitive.
• Nash Equilibrium: As a result of competition, companies reach a set of rates where none can improve their position without worsening others.

Application of the Traveling Salesman Problem (TSP)

Context:

The Traveling Salesman Problem (TSP) in logistics involves finding the shortest route passing through a set of points (in this case, supplier cities) while minimizing total transportation costs.

Applying TSP to our Problem

Goal: Optimize carriers' routes to collect goods from multiple suppliers, reducing overall costs.

Constraints: Each carrier must collect goods from suppliers in a specific region and deliver them to the appropriate warehouse.

Solution Using Game Theory

• Players: Transport companies.
• Strategies: Choosing the route and order of visiting suppliers to minimize costs.
• Payoffs: Reducing transportation costs increases the company’s profit.
• Interaction Between Companies: Companies compete for routes with the lowest costs.

Example:

Southern China (Company 3):

Suppliers: Shenzhen, Guangzhou, Dongguan, Foshan, Xiamen.

Route Optimization:

Company 3 can design a route that sequentially passes through all these cities, minimizing the total distance and costs. Using TSP algorithms (e.g., nearest neighbor algorithm, branch and bound method), the company determines the optimal sequence of city visits.

Strategic Behavior of the Company:

Company 3 aims to minimize its transportation costs to maintain a competitive price advantage.

If the company does not optimize its route, its costs will rise, and it may lose out to competitors.

Impact on Supplier Choice:

Suppliers are interested in carriers minimizing their costs, as this leads to lower prices.

By optimizing its route, Company 3 can keep rates low and continue winning auctions.

Problem 2: Optimization of Cargo Consolidation Points Considering Freight Flow Distribution

Problem Statement:

The goal is to select two optimal locations for consolidating goods from suppliers, considering the following conditions:

The total freight flow is 750 tons per month.

The participation percentage of each supplier city in the overall freight flow is known.

Distances between supplier cities and potential consolidation points (warehouses) are provided.

After selecting the new consolidation points, the objective is to minimize transportation costs, considering distances and transport companies' rates.

Input Data:

Freight flows by supplier cities (in % of total volume): (to be specified).

Total Freight Flow: 750 tons per month.

1. Transport companies' rates by region (in $ per ton·km):

2. Classification of Regions by Cities:

• Northern China: Beijing, Tianjin, Qingdao.
• Central China: Shanghai, Suzhou, Nanjing, Hangzhou, Wuhan, Chongqing, Chengdu.
• Southern China: Shenzhen, Guangzhou, Dongguan, Foshan, Xiamen.

Objective of the Problem:

• Determine two optimal cargo consolidation points that minimize the weighted average distance from all suppliers, considering each supplier's freight flow percentage.
• After selecting the consolidation points, re-solve Problem 1 by choosing the optimal carriers based on the new distances to the new warehouses.

Solution to Problem 2

Step 1: Collecting Geographical Data

We will obtain the coordinates of each city:

Step 2: Classification of Regions

• Northern China: Beijing, Tianjin, Qingdao
• Central China: Shanghai, Suzhou, Nanjing, Hangzhou, Wuhan, Chongqing, Chengdu
• Southern China: Shenzhen, Guangzhou, Dongguan, Foshan, Xiamen

Step 3: Methodology for Determining Optimal Warehouse Locations

• We use the weighted cluster analysis method:
• Divide suppliers into two clusters based on geographical location and freight flow percentage.
• Calculate the weighted centroids for each cluster.
• Identify the optimal cities for warehouse locations based on the calculated centroids and logistical factors.

Step 4: Cluster Analysis

4.1. Cluster Division

Cluster 1 (North and Central):

• Beijing, Tianjin, Qingdao, Shanghai, Suzhou, Nanjing, Hangzhou, Wuhan, Chongqing, Chengdu
• Cluster 2 (South):
• Shenzhen, Guangzhou, Dongguan, Foshan, Xiamen

4.2. Calculating Weighted Centroids

Cluster 1:

• Total percentage: 71.23%
• Weighted Latitude

Weighted Latitude = ∑(Latitude_i ×Percentage_i) \ Total Percentage

Numerator Calculation:

(39.9042×8.84) + (39.3434×3.21) +(36.0671×3.35)+(31.2304×10.12) +(31.2989×7.57)+(32.0603×9.63)+(30.2741×2.38)+(30.5928×5.55)+(29.5630×9.91)+(30.5728×8.68)=2,274.183

Weighted Latitude:

Weighted Latitude = 2,274.183 \ 71.23 ≈ 31.93°N

Weighted Longitude:

We calculate similarly and obtain ≈ 115.12°E.

Cluster 2:

Total percentage: 28.77%

Weighted Latitude:

Weighted Latitude = 719.813 \ 28.77 ≈ 25.02°N
Weighted Longitude:

We calculate similarly and obtain ≈ 113.67°E.

Step 5: Determining Optimal Cities for Warehouses

Cluster 1:

Calculated centroid: 31.93°N, 115.12°E

Nearest major cities:

Wuhan (30.5928°N, 114.3055°E)

Nanjing (32.0603°N, 118.7969°E)

Warehouse Selection:

Wuhan is selected as the optimal city due to its central location relative to suppliers and its well-developed logistics infrastructure.

Cluster 2:

Calculated centroid: 25.02°N, 113.67°E

Nearest major cities:

Guangzhou (23.1291°N, 113.2644°E)

Xiamen (24.4798°N, 118.0894°E)

Warehouse Selection:

Guangzhou is chosen as the optimal city due to its strategic location and major port.

Step 6: Transportation Cost Analysis

6.1. Calculating Distances from Suppliers to the New Warehouses

We use the Haversine formula to calculate the geodesic distance between two points based on their coordinates.

6.2. Calculating Transportation Costs

Formula:

Cost = Distance × Tariff

We account for regional tariffs and select the lowest rate from the three companies for each region.

6.3. Total Costs

We calculate the total costs for all suppliers considering their percentage contribution to freight flow.

Example for Cluster 1 (Wuhan):

Supplier: Beijing

Distance to Wuhan: ≈ 1,050 km

Lowest tariff (Northern China): $0.07 (Company 1)

Cost:

1,050 km × 0.07 = 73.50 USD

Weighted cost considering freight flow percentage:

Weighted Cost = Cost×Percentage \ 100

Weighted Cost = $73.50 × 8.84 \ 100 = $6.50

We perform similar calculations for all suppliers in the cluster.

6.4. Comparison with Previous Warehouses

We compare the total costs when using the new warehouses (Wuhan and Guangzhou) with the costs when using the old warehouses (Shanghai and Qingdao).

Step 7: Results and Recommendations

7.1. Total Transportation Costs

• Using the new warehouses (Wuhan and Guangzhou):
  • Overall savings due to reduced distances and optimized tariffs.
• The comparison shows that choosing the new warehouses leads to a reduction in total costs.

7.2. Final Warehouse Selection

• Warehouse 1: Wuhan for suppliers from Northern and Central China.
• Warehouse 2: Guangzhou for suppliers from Southern China.

Based on the analysis and calculations, the optimal geographical locations for the two consolidation warehouses are Wuhan and Guangzhou. This choice allows for:

• Minimizing total transportation costs by reducing distances and utilizing the lowest tariffs.
• Improving logistical efficiency thanks to the developed infrastructure and strategic location of the selected cities.
• Considering the percentage distribution of freight flows, concentrating the warehouses in areas with the highest volume of goods.

Implementation Recommendations:

• Conduct a detailed logistical analysis considering actual routes, road infrastructure, and additional costs.
• Assess the availability of warehouse facilities in the selected cities and negotiate with local logistics operators.
• Consider factors such as safety, supply reliability, and delivery times in the final decision-making process.

For each supplier city, calculate the distances to Wuhan and Guangzhou.

Note: Distances are accurate to within 5 km and based on road distances.

Table 3

Distances from Suppliers to Warehouses

Step 2: Determining the Optimal Warehouse for Each Supplier

For each supplier, we compare the delivery costs to Wuhan and Guangzhou, and select the warehouse with the lowest cost.

Transport companies' rates:

Calculation of Delivery Costs to Each Warehouse Using the Minimum Regional Rate:

• Northern China: Minimum rate – $0.07 (Company 1)
• Central China: Minimum rate – $0.08 (Company 2)
• Southern China: Minimum rate – $0.09 (Company 3)

Example for Shenzhen:

• To Wuhan:
  • Cost = 1,100 km × $0.09 = $99.00
• To Guangzhou:
  • Cost = 140 km × $0.09 = $12.60

Comparison: $12.60 < $99.00 ⇒ We choose the warehouse in Guangzhou.

Table 4

Optimal Warehouse for Each Supplier

Step 3: Selecting a Carrier for Each Supplier

For each supplier, we select the carrier with the lowest delivery cost to the chosen warehouse.

Table 5

Carrier Selection for Each Supplier

Suppliers shipping to Wuhan:

Suppliers shipping to Guangzhou:

Step 4: Detailed Explanation of Carrier Selection Using Game Theory

Application of the Auction Method in Game Theory:

Players:

• Suppliers – the organizers of the auction, aiming to minimize their transportation costs.
• Transport companies – participants in the auction, offering their prices for the transportation service.

Transport Companies' Strategies:

• Propose competitive rates for the supplier’s region.
• Possibly reduce the price to the minimum feasible level in order to win the contract.

Auction Process for Each Supplier:

• First round: Each company submits its bid, calculated based on its rates and the distance.
• Bid analysis: The supplier compares the submitted bids.
• Winner selection: The supplier selects the carrier with the lowest bid.

Example for Shanghai:

• Distance to Wuhan: 800 km
• Rates:
  • Company 1: $0.09/ton·km ⇒ $72.00
  • Company 2: $0.08/ton·km ⇒ $64.00
  • Company 3: $0.11/ton·km ⇒ $88.00
• Selection: Company 2 offers the lowest price ($64.00) ⇒

Conclusions:

• Company 2 wins auctions in Central China due to the lowest rates.
• Company 1 dominates in Northern China.
• Company 3 is preferred in Southern China because of the lower tariffs in that region.

Step 5: Final Recommendations

Suppliers shipping to Wuhan:

• Establish contracts with Company 2 (Central China) and Company 1 (Northern China) to minimize costs.

Suppliers shipping to Guangzhou:

• Partner with Company 3, which offers the best rates in Southern China.

Overall Savings: Optimizing routes and selecting the most cost-effective carriers will significantly reduce transportation costs from suppliers to the consolidation warehouses.

Based on the provided data:

• Total freight flow per month: 750 tons.
• Freight flow distribution by suppliers (percentage).
• Old consolidation warehouses: Shanghai and Qingdao.
• New consolidation warehouses: Wuhan and Guangzhou.
• Transport companies’ rates.

We need to calculate the monthly cost savings after transitioning to the new warehouses.

Step 1: Calculation of Freight Volumes from Each Supplier

Step 2: Determining Warehouses for Each Supplier

Old Warehouses: Shanghai and Qingdao

Suppliers shipping to Shanghai:

• Shenzhen, Guangzhou, Shanghai, Suzhou, Dongguan, Nanjing, Hangzhou, Wuhan, Foshan, Xiamen.

Suppliers shipping to Qingdao:

• Beijing, Chongqing, Tianjin, Chengdu, Qingdao.

New Warehouses: Wuhan and Guangzhou

Suppliers shipping to Wuhan:

• Shanghai, Suzhou, Beijing, Chongqing, Tianjin, Chengdu, Nanjing, Hangzhou, Wuhan, Qingdao.

Suppliers shipping to Guangzhou:

• Shenzhen, Guangzhou, Dongguan, Foshan, Xiamen.

Step 3: Calculation of Transportation Costs for Each Supplier

Transport companies' rates: (to be calculated).

3.1. Calculation of Transportation Costs with Old Warehouses

Suppliers shipping to Shanghai:

Total cost for Shanghai: $32,937.71

Suppliers shipping to Qingdao:

Total cost for Qingdao: $23,816.32

Total cost with old warehouses:

$32,937.71+$23,816.32=$56,754.03

3.2. Calculation of Transportation Costs with New Warehouses

Suppliers shipping to Wuhan:

Total cost for Wuhan: $34,069.09

Suppliers shipping to Guangzhou:

Total cost for Guangzhou: $3,257.28

Total cost with new warehouses:

$34,069.09 + $3,257.28 = $37,326.37

Step 4: Calculation of Savings

Monthly savings:

Savings = Old cost - New cost = $56,754.03 - $37,326.37 = $19,427.66

Switching to the new warehouses in Wuhan and Guangzhou allows for a savings of $19,427.66 per month in transportation costs from suppliers to consolidation warehouses. The savings are achieved through:

Reduced transportation distances, especially for suppliers from Southern China.

Optimal selection of carriers with the lowest rates in their respective regions.

Efficient distribution of suppliers between warehouses, considering their geographic locations and freight volumes.

Conclusion

Game theory allows for modeling the competitive behavior of transport companies and their interactions in the marketplace.

The auction method helps suppliers choose the optimal carrier, minimizing their costs.

The Traveling Salesman Problem (TSP), applied in the context of game theory, allows carriers to optimize their routes and reduce costs, which improves their competitiveness in auctions.

Recommendations

• Use auction results to sign contracts with selected carriers at the lowest prices.
• Encourage carriers to optimize their routes (e.g., by offering long-term cooperation), enabling them to maintain low rates.
• Monitor market rates and periodically conduct new auctions to ensure the best conditions for your company.

Conclusions: Using the auction method from game theory and the Traveling Salesman Problem significantly reduces logistics costs. Optimizing carrier selection and cargo consolidation locations enables minimization of transportation expenses and improves logistics efficiency.

The monthly savings of $19,427.66 confirms the feasibility of applying these methods to optimize freight flows and logistics at the company level.