March 12, 2025

A Multi-Objective Network Optimization Problem

Abstract

This blog post addresses the design of a sustainable logistic network for GreenForwarder—a multinational freight company—by balancing profitability, environmental emissions, and regional reach. A multi-objective network optimization problem is formulated over a graph that represents cities and potential transport connections. Using a modified Minimum Spanning Tree (MST) algorithm that incorporates capacity constraints and investment costs, the approach has been inspired by the Steiner Tree Problem and evaluates candidate edges dynamically by considering cost, emission factors, and a bonus for expanding regional reach. POC and LIVE differ significantly in their approaches, particularly in their starting points. POC begins by simplifying the “full” graph and focusing on optimizing its objective function, whereas LIVE prioritizes satisfying its unique constraint from the outset. For the MVP, two methods are employed to determine which approach would yield a better outcome, as the significance of profit’s contribution was unknown during the project’s initial stages. Detailed experimental results, analysis, and comparisons are provided in later sections.

If you are curious on this approach in code you can look at my github repository.

Introduction
1.1 Background and Motivation
1.2 Project Description and Problem Definition
Related Work and Theoretical Background
Algorithmic Approach
3.1 Algorithmic Approach and Configuration Details
Computational Experiments and Results
4.1 Performance Metrics
4.2 Results and Discussion
Conclusion and Future Work
5.1 Conclusions
5.2 Limitations
5.3 Recommendations
5.4 Future Research
Appendix

1. Introduction

1.1 Background and Motivation

The global logistics industry faces increasing pressures to operate both profitably and sustainably. Traditional freight network designs often fail to balance the need to reduce carbon emissions with the expansion of market reach. In response, GreenForwarder has initiated a radical redesign of its 2025 freight transport network. This new design must:

Maximize Profit: By connecting city pairs that yield high revenue.
Minimize Emissions: By selecting transport modalities with low carbon footprints.
Maximize Regional Reach: By covering as many distinct regions as possible.

Moreover, the network must adhere to strict capacity constraints and allow for investments to secure additional capacity when needed.

1.2 Project Description and Problem Definition

The problem is modeled as an undirected graph G = (V,E), where:

V = {v₁, v₂, …, vₙ} represents cities, each with geographic coordinates and regional identifiers.
E = {eᵢⱼ} represents potential connections (edges) between cities v₁ and v₂.

Each edge e ∈ E is associated with a transport modality from the set {Truck, Ship, Train, Plane}. These modalities have specific properties:

Transportation cost c(e): Measured in travel units.
Emission factor f(m): Varies by modality (Truck: 8, Ship: 1, Train: 3, Plane: 25).
Capacity constraint: Each modality has an initial free capacity of 50 units. This capacity can be expanded up to 75 through additional investment, with costs defined in Table 3.

In mathematical notation, each modality m with usage Uₘ must not exceed the available capacity:

$$U_m \leq 50 + \Delta C(m)$$

A valid network N ⊆ E must satisfy connectivity constraints, ensuring that all selected cities are reachable from Eindhoven, which is always included as the base. The goal is to optimize a weighted score based on:

Total Emissions:
$$E_{\text{total}} = \sum_{e \in N} c(e) \cdot f(m_e)$$
Investment Cost:
Let Uₘ be the cumulative usage for modality m. Then:
$$I = \sum_{m} \text{Cost}_{\text{investment}}(m, U_m)$$
Profit:
$$\text{Profit} = \text{Revenue} - I$$
Revenue is calculated from revenue-generating target pairs:
$$\text{Revenue} = \sum_{(v_i, v_j) \in T} R_{ij}$$ (if vᵢ and vⱼ are connected in N).
Reach:
Denoted R(N), it is the number of distinct regions covered by N.

The overall score is computed as:

For PoC:

$$Score = -E_{\text{total}} + 100 \cdot R(N)$$

For MVP and LIVE:

$$Score = 15 \cdot \text{Profit} - E_{\text{total}} + 100 \cdot R(N)$$

with the LIVE configuration adding the hard constraint:

$$\text{Profit} \geq 45\ \text{mln}$$

A key source of inspiration for this paper comes from the Steiner Tree Problem, which is concerned with finding the minimum-cost tree connecting a given subset of nodes (called terminal nodes) in a graph. Unlike the Minimum Spanning Tree (MST), which connects all nodes, the Steiner Tree Problem specifies certain nodes (terminal nodes) that must be reached, while other nodes (Steiner nodes) are used optionally for connectivity or improved output. This formulation is particularly useful in telecommunications, circuit design, and logistics.

In this approach, high-priority cities (those linked to significant revenue or reach potential) are designated as terminal nodes forming the backbone of the network. The algorithm dynamically evaluates candidate connections—similar to exploring potential Steiner nodes—to construct a network that minimizes a composite cost function incorporating travel cost, emission factors, and additional investment costs. This dynamic evaluation, combined with iterative improvement strategies (such as leaf pruning and network extension), helps avoid local optima while achieving a well-balanced network design that meets capacity constraints and sustainability objectives.

3. Algorithmic Approach

3.1 Algorithmic Approach and Configuration Details

The overall workflow proceeds in a chronological manner, beginning with data reading and terminal selection, followed by MST construction, and finally iterative refinement.

Data Loading and Setup:
The program reads the city, connection, and target (revenue) data. Each connection has an associated transport modality, travel cost, and emission factor.
Terminal Selection:
- PoC:
  Emphasizes only emissions and regional coverage. The algorithm selects one terminal node at random for each region (10 regions), performing multiple runs with different random draws and retaining the best-scoring solution.
- LIVE:
  Selects a subset of city pairs from the revenue file (e.g., 15 out of 32 pairs) and uses the union of these pairs’ cities as the terminal set. This approach focuses on higher-revenue cities, which increases overall profit and ensures the Profit ≥ 45 constraint is satisfied. Multiple runs with different random sets are performed to store the best feasible outcome.
- MVP:
  Experiments showed that a LIVE-based approach produced the best results, so the terminal nodes for MVP are chosen in the same way as for LIVE.
MST Construction (Initial Phase):
A modified Prim’s algorithm is used starting at Eindhoven (to ensure its inclusion). Each potential edge is evaluated using an effective cost, which includes:
- Emission Cost: ( (\text{travel cost}) \times (\text{emission factor}) )
- Investment Cost: Factored in if the edge’s usage exceeds 50 free units for a modality.
- Bonus: If a newly connected city belongs to a region not yet in the network, a bonus (e.g., 100) is subtracted from its cost, encouraging coverage of new regions.
Candidate edges are stored in a priority queue, and the MST grows iteratively by selecting edges with the lowest composite cost. At each stage, the score of the network is evaluated, and when the MST algorithm concludes (no more edges can be added), the iteration with the highest score is chosen for further optimization.
Differences in MST per configuration:
- PoC and MVP:
  The only difference lies in the edge evaluation. PoC considers only emissions and the reach bonus, while MVP also includes investment cost.
- LIVE:
  If the profit constraint is not met, the algorithm restarts with a different set of random profitable terminals to ensure that the final output meets the Profit ≥ 45 constraint.
Iterative Refinement (Post-MST):
Two optimization routines are applied:
- Leaf Pruning:
  Removing leaf nodes (other than Eindhoven) if their removal increases the overall score.
- Network Extension via Local Search:
  Additional edges are considered if they can be added without exceeding capacity (or by paying the additional investment cost) and if they increase the final score.
These routines repeat until no further improvement is possible.

4. Computational Experiments and Results

4.1 Performance Metrics

The following metrics were used to evaluate network performance:

Runtime: The total execution time of the algorithm.
Overall Score: As defined in Section 1.2 Project Description and Problem Definition.

For the PoC configuration, only the number of iterations was varied (e.g., 10,000; 100,000; 1,000,000; 2,000,000 iterations).
For MVP and LIVE configurations, two parameters were varied: the number of iterations and the random sample size (the set of pairs from the revenue file). Sample sizes of 10, 15, 20, and 25 were tested. Each test was run 10 times to reduce randomness.

4.2 Results and Discussion

Key Findings:

The optimal number of random city pairs for the MVP and LIVE configurations appears to be 15, though each sample size has its pros and cons.
Increasing the number of iterations results in incremental score improvements, with the trend resembling logarithmic growth rather than linear.

PoC Configuration:
Results (detailed in Appendix, Table 5) show that as the number of iterations increases, the score gradually improves. This is attributed to the random selection of a city within each region, which increases the probability of generating high-scoring networks.

MVP and LIVE Configuration:
Two tests were conducted:

Test 1:
With iterations fixed at 100,000 and varying the sample size, the LIVE configuration benefited from a larger sample size. For MVP, performance peaked around sample sizes of 15 to 20.
Test 2:
With a fixed sample size (15), increasing the iterations produced higher scores due to testing a greater number of permutations, although the relationship remained logarithmic.

Runtimes:

PoC: 20 milliseconds per iteration.
MVP and LIVE: 518 microseconds per iteration.

5. Conclusion and Future Work

5.1 Conclusions

This work presented a comprehensive approach for optimizing a sustainable logistic network under multiple objectives. Key contributions include:

A detailed mathematical model that integrates profit, emissions, and regional reach.
A dynamic MST-based algorithm with iterative refinements (leaf pruning and network extension) to address capacity and investment constraints.
A comparative study of three configurations (PoC, MVP, LIVE) with the enhanced MVP approach adopting the LIVE method (without the profit constraint) to significantly improve performance.

5.2 Limitations

Several limitations remain:

Scalability: The computational intensity increases with the network size.
Heuristic Nature: The approach does not guarantee global optimality.
Assumptions: Certain assumptions were made during the development of the three approaches without full justification.

5.3 Recommendations

Sample Size: With more computing power and time, a larger sample size can be used for MVP and LIVE configurations, potentially yielding higher scores due to increased optionality.
Optimization with Each Iteration: Instead of applying optimization only to the best MST result, consider applying the optimization routine to each generated graph to potentially capture a better overall score.
Terminal City Selection in PoC: Increasing the number of terminal cities per region may provide higher network optionality.
Code Optimization: Optimize the code by refactoring repeated operations (e.g., constructing the full graph outside of iterative loops).

5.4 Future Research

Future work could focus on:

Integrating hybrid metaheuristics (e.g., genetic algorithms, simulated annealing) to escape local optima.
Developing real-time adaptive methods that can re-optimize the network as new data become available.

6. Appendix

Highest Scores Achieved in Testing:

MVP: 1019 (this score also satisfies the LIVE constraints)
LIVE: 997
PoC: 640
(Results achieved with a sample size of 15 throughout testing.)

Figures:

Figure 1: Best PoC Network.
Figure 2: Best LIVE and MVP Network.

Detailed Results

Table 1: POC Detailed Results Summary and Modality Usage

Metric	Value
Total Cities Connected	11
Regions Reached	8
Total Emissions	160.00
Investment Cost	NA
Revenue	NA
Profit	NA
Final Score	640.00

Modality Usage:

Modality	Usage
Truck	38.00
Plane	0.00
Boat	52.00
Rail	70.00

Table 2: MVP and LIVE Detailed Results Summary and Modality Usage

Metric	Value
Total Cities Connected	21
Regions Reached	9
Total Emissions	646.00
Investment Cost	9.00
Revenue	60.00
Profit	51.00
Final Score	1019.00