The Ripple-Spreading Algorithm for the one-to-all Multi-Category Multi-Objective Path Optimization Problem
The multi-category multi-objective path optimization problems aims to determine all Pareto-optimal paths from one node to all other nodes on a graph with multiple additive and multiplicative weights.
Variables | Meaning |
---|---|
network | Dictionary, {node 1: {node 2: [[additive weights], [multiplicative weights]], ...}, ...} |
s_network | The network described by a crisp weight on which we conduct the ripple relay race |
source | The source node |
nn | The number of nodes |
na | The number of additive weights |
nm | The number of multiplicative weights |
neighbor | Dictionary, {node1: [the neighbor nodes of node1], ...} |
v | The ripple-spreading speed (i.e., the minimum length of arcs) |
t | The simulated time index |
nr | The number of ripples - 1 |
epicenter_set | List, the epicenter node of the i-th ripple is epicenter_set[i] |
path_set | List, the path of the i-th ripple from the source node to node i is path_set[i] |
radius_set | List, the radius of the i-th ripple is radius_set[i] |
active_set | List, active_set contains all active ripples |
objective_set | List, the objective value of the traveling path of the i-th ripple is objective_set[i] |
Omega | Dictionary, Omega[n] = i denotes that ripple i is generated at node n |
The red number associated with each arc is the additive weight, and the green number is the multiplicative weight.
if __name__ == '__main__':
test_network = {
0: {1: [[62], [0.9]], 2: [[44], [0.7]], 3: [[67], [0.6]]},
1: {0: [[62], [0.9]], 2: [[33], [0.8]], 4: [[52], [0.5]]},
2: {0: [[44], [0.7]], 1: [[33], [0.8]], 3: [[32], [0.8]], 4: [[52], [0.5]]},
3: {0: [[67], [0.6]], 2: [[32], [0.8]], 4: [[54], [0.8]]},
4: {1: [[52], [0.5]], 2: [[52], [0.5]], 3: [[54], [0.8]]},
}
source_node = 0
destination_node = 4
print(main(test_network, source_node, destination_node))
{
0: [{'path': [0], 'objective': [0, 1]}],
1: [{'path': [0, 1], 'objective': [62, 0.9]}],
2: [
{'path': [0, 2], 'objective': [44, 0.7]},
{'path': [0, 1, 2], 'objective': [95, 0.72]},
],
3: [{'path': [0, 3], 'objective': [67, 0.6]}],
4: [
{'path': [0, 2, 4], 'objective': [96, 0.35]},
{'path': [0, 1, 4], 'objective': [114, 0.45]},
{'path': [0, 3, 4], 'objective': [121, 0.48]},
]
}