This archive is distributed under the MIT license.
The software and data in this repository were used in the research reported in the article "An Open-Source Generator for Realistic Instances of the Scheduled Service Network Design Problem" by Louis Bonnet, Simon Belieres, Mike Hewitt, and Sandra Ulrich Ngueveu.
The Service Network Design Problem (SNDP), and its timed variant the Scheduled SNDP (SSNDP), are challenging optimization problems arising in freight transportation systems. This software generates realistic instances with hub-and-spoke networks for these problems with some of its parameters based metrics from the literature on Complex Networks and Complex Networks Analysis.
Each instance, either of the SNDP or the SSNDP, consists of:
- A directed network with a node set and an arc set
- A set of commodities
Networks and instances can be generated using controlled parameters that govern structural features such as density, reciprocity, and hub–spoke organization.
src/
├── Config.py # Configuration parsing and validation
├── Structures.py # Core data structures (nodes, arcs, commodities)
├── NetworkGenerator.py # Network generator (hub-and-spoke, random, and emulation)
├── InstanceGenerator.py # Instance and demand generator
├── main.py # Entry point for execution
├── environment.yml # Environment configuration for conda.
├── requirements.txt # Environment requirements for pip.
└── Config.txt # Configuration file
data/
├── Networks/ # Default path for generated networks
├── Instances/ # Default path for generated instances
└── Networks/Benchmark/ # Benchmark networks used in the articleTo generate networks and instances, run:
python src/main.py
The generator automatically reads parameters from Config.txt.
By default, the generated networks are stored in Networks/, and the generated instances in Instances/. It can be changed with the parameters defaultInstancePath and defaultNetworkPath, respectively.
All the parameters are read from the file Config.txt. All the parameters marked as optional can be assigned the value None to be disabled.
The file is organized in three sections:
| Parameter | Type | Description |
|---|---|---|
defaultInstancePath |
Path | Default path for reading/writing instances (data/Instances) |
defaultNetworkPath |
Path | Default path for reading/writing networks (data/Networks) |
folder |
str | Optional subfolder for organizing runs |
networkNb |
int > 0 | Number of networks to generate |
instanceNb |
int > 0 | Number of instances to generate per network |
networkSeed |
int > 0 | Optional seed for reproducible network generation |
demandSeed |
int > 0 | Optional seed for reproducible demand generation |
| Parameter | Type | Description |
|---|---|---|
networkEmulationPath |
Path | If provided, emulate an existing network instead of generating a new one |
networkEmulationTimeLimit |
float > 0 | Time limit for network emulation |
randomGeneration |
bool | Whether to use random or structured hub-and-spoke generation |
capacity |
float > 0 | Capacity of each arc |
bboxWidth, bboxHeight |
float > 0 | Dimensions of the bounding box for arc distance |
targetNodeNb |
int > 0 | Number of nodes |
targetArcNb |
int > 0 | Arc budget (optional alternative to density) |
targetDensity |
float ∈ [0,1] | Desired network density |
targetReciprocity |
float ∈ [0,1] | Desired proportion of bidirectional arcs |
decayRate |
float > 0 | Decay rate controlling how spread out clusters are |
hnRatio |
float ∈ (0,1] | Ratio of hub nodes to total nodes |
ufCostRatio |
float > 0 | Ratio between unit and fixed costs |
mode |
int ∈ {1,2,3,4} | Transportation mode: 1 (LTL), 2 (Liner), 3 (Rail), 4 (Express) |
ltlRangeDensity |
(float,float) ∈ [0,1]2 | Density lower and upper bound of the LTL transportation mode networks. Default: (0.06,0.74). |
ltlRangeReciprocity |
(float,float) ∈ [0,1]2 | Reciprocity lower and upper bound of the LTL transportation mode networks. Default: (0.71,1.0). |
linerRangeDensity |
(float,float) ∈ [0,1]2 | Density lower and upper bound of the Liner transportation mode networks. Default: (0.02,0.82). |
linerRangeReciprocity |
(float,float) ∈ [0,1]2 | Reciprocity lower and upper bound of the Liner transportation mode networks. Default: (0.58,1.0). |
railRangeDensity |
(float,float) ∈ [0,1]2 | Density lower and upper bound of the Rail transportation mode networks. Default: (0.02,0.06). |
railRangeReciprocity |
(float,float) ∈ [0,1]2 | Reciprocity lower and upper bound of the Rail transportation mode networks. Default: (1.0,1.0). |
expressRangeDensity |
(float,float) ∈ [0,1]2 | Density lower and upper bound of the Express transportation mode networks. Default: (0.03,0.06). |
expressRangeReciprocity |
(float,float) ∈ [0,1]2 | Reciprocity lower and upper bound of the Express transportation mode networks. Default: (0.19,0.81). |
| Parameter | Type | Description |
|---|---|---|
doStatic |
bool | If true, generate SNDP; otherwise, generate SSNDP |
commodityNb |
int > 0 | Number of commodities |
quantityToCapaMean, quantityToCapaDev |
float ∈ [0,1] | Mean and standard deviation of commodity size relative to arc capacity |
sameRegionRatio |
float ∈ [0,1] | Ratio of commodities with origin-destinations lying in the same cluster |
disparityRatio |
float ∈ [0,1] | Likelihood of uneven distribution of demand origins/destinations |
horizon |
int > 0 | Planning horizon (time periods) |
flexibilityMean, flexibilityDev |
float ∈ [0,1] | Distribution of time flexibility relative to shortest path |
criticalTime |
int > 0 | Time rounding for available and due times |
distributionPattern |
list[float] | Probability distribution of available times, size must be equal to horizon |
preProcessingSSNDP |
bool | Whether to add preprocessing information (time windows) for SSNDP instances |
The range of the parameters is checked before the generation and an error is reported to the user if incoherent values are given.
In order to produce networks and instances with different inputs more easily, values given to parameters in the file Config.txt can be written as lists. For instance, if targetDensity=[0.2,0.5,0.8], and all other parameters have a single value (e.g. , targetReciprocity=0.5), three sets of configuration paremeters will be used for each of the values of the parameter targetDensity.
Any parameter in Config.txt can take multiple values (as a list).
All combinations across parameters are automatically enumerated.
Example:
targetDensity=[0.2,0.5,0.8]
targetReciprocity=0.5Generates three sets of networks with the same reciprocity and varying densities.
The software validates all parameter values before execution. An error is returned to the user if incoherent values are detected (i.e., out of bound or invalid type values).
Each generated network or instance file includes encoded parameters in its name.
| Parameter | Label |
|---|---|
decayRate |
DR |
hubNodeRatio |
A |
ufCostRatio |
UF |
targetReciprocity |
R |
targetDensity |
D |
targetNodeNb |
N |
networkSeed |
S |
| Parameter | Label |
|---|---|
quantityToCapaMean |
MCQ |
quantityToCapaDev |
DCQ |
sameRegionRatio |
SR |
disparityRatio |
DR |
horizon |
H |
flexibilityMean |
FM |
flexibilityDev |
FD |
criticalTime |
CT |
demandSeed |
S |
Values in [0,1] are scaled by 100 and rounded. Additional suffixes:
- I: Index of the generated file (e.g., I0)
- Prefix SNDP_ or SSNDP_ indicates the instance type
Examples of outputs names:
- DR30_A1_UF5_R20_D5_N50_I0_S0: network with decayRate=30 ; hubNodeRatio=0.01 ; ufCostRatio=0.05 ; targetReciprocity=0.2 ; targetDensity=0.05 ; targetNodeNb=50 ; networkIdx=0 ; networkSeed=0
- SNDP_MCQ10_DCQ50_C100_I0_DR30_A20_UF5_R50_D50_N50_I0_S0: SNDP instance with quantityToCapaMean=0.1 ; quantityToCapaDev=0.5 ; targetCommodityNb=100 ; instanceIdx=0 ; decayRate=30 ; hubNodeRatio=0.2 ; ufCostRatio=0.05 ; targetReciprocity=0.5 ; targetDensity=0.5 ; targetNodeNb=50 ; networkIdx=0 ; networkSeed=0
- SSNDP_MCQ10_DCQ50_SR100_DR50_H24_FM50_FD17_CT5_C100_I0_DR30_A20_UF5_R50_D50_N50_I0_S0: SSNDP instance with quantityToCapaMean=0.1 ; quantityToCapaDev=0.5 ; sameRegionRatio=1.0 ; disparityRatio=0.5 ; horizon=24 ; flexibilityMean=0.5 ; flexibilityDev=0.17 ; criticalTime=5 ; targetCommodityNb=100 ; instanceIdx=0 ; decayRate=30 ; hubNodeRatio=0.2 ; ufCostRatio=0.05 ; targetReciprocity=0.5 ; targetDensity=0.5 ; targetNodeNb=50 ; networkIdx=0 ; networkSeed=0
The file structure of the outputs of the generator follows the structure:
NODES,\<number of nodes generated\>
...
node id, cluster id, x, y
...
ARCS,\<number of arcs generated\>
...
arc id, origin id, destination id, unit cost, fixed cost, capacity, distance
...
COMMODITIES,\<number of commodities generated\>
...
commodity id, origin id, destination id, quantity, available time, due time
...
horizon=\<length of the planning horizon\>
distribution_pattern=\<_distributionPattern_\>
COMMODITY_NODE_TIMEWINDOWS,\<number of per commodity, per node, time windows\>
...
time window id, commodity id, node id, lower bound, upper bound
...
COMMODITY_ARC_TIMEWINDOWS,\<number of per commodity, per arc, time windows\>
...
time window id, commodity id, arc id, lower bound, upper bound
...
Some remarks:
- The cluster id value is not given in the case of a random network.
- The x and y coordinates are not given if no bounding box width and heigth was specified.
- The arc distance, in network files, is an euclidean distance represented by float numbers. It is not given in SNDP instance files. It is given as a number of time period in SSNDP instance files.
- The horizon is only given for SSNDP instance files.
- The distribution pattern is only given for SSNDP instance files where the associated parameter was specified.
- The two lists of time windows (for arcs and nodes) are given only for SSNDP instance files when the parameter preProcessingSSNDP=True.
This project is designed to be fully reproducible using either pip or conda. Use either requirements.txt or environment.yml to do so.
Thank you for considering contributing to our project! To report bugs and ask questions, please refer to the issue tracker. You can also address a problem by (1) forking the project, (2) correcting the bug / adding a feature, and (3) generating a pull request. However, we recommend that you first contact the authors and discuss the desired feature request.
You are also very welcome if you want to upload in our repository the instances you generated with our generator and used in your work! In this way, other researchers can use the same set of instances as benchmark, without having to re-generate such instances using the parameters you used. If this is the case, please send us an email.