# Problem Instances

Contents

- 1 Problem Instances
- 1.1 Searching for Stable Fixed-Edge Graphs - Instances and Source Code
- 1.2 Snarks which do not contain perfect pseudo-matching whose contraction leads to planar/K5-minor-free/SUD-K5-minor-free graphs
- 1.3 Anytime Algorithms For Solving the Longest Common Palindromic Subsequence Problem (LCPS):
- 1.4 Service Point Distribution Problem (SPDP)
- 1.5 Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources (PC-JSOCMSR)
- 1.6 The Longest Common Palindromic Subsequence Problem
- 1.7 Particle Therapy Patient Scheduling
- 1.8 Job Sequencing with One Common and Multiple Secondary Resources (JSOCMSR)
- 1.9 Districting and Routing Problem for Security Control
- 1.10 Dial-a-Ride Problem
- 1.11 Network Design Problem with Relays
- 1.12 Directed Network Design Problem with Relays
- 1.13 Rooted Delay-Constrained Minimum Spanning Tree Problems
- 1.14 Consensus Tree Problem
- 1.15 Periodic Vehicle Routing Problem with Time Windows
- 1.16 Periodic Vehicle Routing Problem and Periodic Traveling Salesman Problem
- 1.17 Vehicle Routing Problem with Compartments
- 1.18 Bi-level Vehicle Routing Problem
- 1.19 Balancing Bicycle Sharing System (BBSS) Problem
- 1.20 Mulitmodal Home-Healthcare Scheduling (MHS) Problem
- 1.21 Competitive Facility Location Problems
- 1.22 Multi Layer Hierarchical Ring Network Design Problem
- 1.23 Two Dimensional Pre-Marshalling Problem
- 1.24 Generalized Vehicle Routing Problem with Stochastic Demands
- 1.25 Virtual Network Mapping Problem

## Searching for Stable Fixed-Edge Graphs - Instances and Source Code

Contact: Benedikt Klocker and/or Günther Raidl

Instance Set 1 (3-connected 3-regular planar graphs with minimum degree three) can be found here.

Instance Set 2 (after inserting some random degree two vertices into 3-connected 3-regular planar graphs with minimum degree three) can be found here.

Instance Set 3 (random potential candidate graphs for minimal counter example, grouped by number of faces) can be found here.

All instance files are in g6-format see here for a description of the format.

The source code for the program to check if a graph contains a SFE-cycle can be found here.

## Snarks which do not contain perfect pseudo-matching whose contraction leads to planar/K5-minor-free/SUD-K5-minor-free graphs

In the following we will provide a collection of all snarks with up to 32 vertices that do not contain a planarizing perfect pseudo-matching. For the definition of this property and also the terminology which will be used in the following see [1]. The algorithm used to check the properties is described in [2]. Furthermore, a collection of all snarks with up to 32 vertices provided by the House of Graphs was used.

The following table lists for each snark size (number of vertices) from 26 to 32 the total number of such snarks, the number of snarks which do not have a planarizing perfect pseudo-matching but do have a perfect pseudo-matching whose contraction leads to a K_{5}-minor-free graph [no pppm], the number of snarks which do not have a perfect pseudo matching whose contraction leads to a K_{5}-minor-free graph but have one whose contraction leads to a SUD-K_{5}-minor-free graph [no k5mfppm], and the number of snarks which do not have a perfect pseudo matching whose contraction leads to a SUD-K_{5}-minor-free graph but have one whose contraction leads to a graph containing a compatible circuit decomposition [no sk5mfppm].

You can download the list of all such snarks by pressing on the link of the appropriate cell. The graphs are listed one per line in the graph6 format, see Brendan McKay's website for a formal definition.

Every snark with up to 24 vertices contains a planarizing perfect pseudo-matching. Furthermore, all snarks with up to 32 vertices contain a perfect pseudo-matching whose contraction leads to a graph containinga compatible circuit decomposition.

size | total number of snarks | no pppm | no k5mfppm | no sk5mfppm |
---|---|---|---|---|

26 | 1297 | 2 | 0 | 0 |

28 | 12517 | 45 | 15 | 0 |

30 | 139854 | 933 | 578 | 33 |

32 | 1764950 | 24268 | 18537 | 1062 |

## Anytime Algorithms For Solving the Longest Common Palindromic Subsequence Problem (LCPS):

Contact: Marko Djukanovic and/or Günther Raidl

Instances for the 2-LCPS problem can be found here.

The supplementary file of this research can be found here.

## Service Point Distribution Problem (SPDP)

Contact: Thomas Jatschka, Günther Raidl

Instances for the EvoCOP 2019 can be found here.

Instances for the LOD 2019 are available here here.

## Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources (PC-JSOCMSR)

Contact: Matthias Horn, Johannes Maschler, Günther Raidl

Instances for the PC-JSOCMSR problem can be found here. For details on the instance format see the included description. The following publications consider these benchmark instances:
5 results

2021 | |

[5] | A*-based Construction of Decision Diagrams for a Prize-Collecting Scheduling ProblemComputers & Operations Research, volume 126, pages 105125, 2021.Note: previous technical report version at https://www.ac.tuwien.ac.at/files/tr/ac-tr-18-011a.pdf |

2020 | |

[4] | A* Search for Prize-Collecting Job Sequencing with One Common and Multiple Secondary ResourcesAnnals of Operations Research, 2020.Note: previous technical report version at https://www.ac.tuwien.ac.at/files/tr/ac-tr-19-002.pdf |

2019 | |

[3] | Multivalued Decision Diagrams for Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources 2019, Technical report AC-TR-19-003, Algorithms and Complexity Group, TU Wien. |

2018 | |

[2] | Multivalued Decision Diagrams for a Prize-Collecting Sequencing ProblemPATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, pages 375–397, 2018. |

[1] | An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time WindowsPATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, pages 235–256, 2018. |

## The Longest Common Palindromic Subsequence Problem

Contact: Marko Djukanovic and/or Günther Raidl

Instances for LCPSP (provided by Christian Blum ) can be found here.

## Particle Therapy Patient Scheduling

Contact: Johannes Maschler, Martin Riedler, Günther Raidl

### Particle Therapy Patient Scheduling Problem (PTPSP)

Instances for PTPSP can be found here. For details on the instance format and the applied preprocessing see the included description. The following publications consider these benchmark instances: 3 results

First instances for PTPSP including a description of the used file format can be found here. Updated instances and results can be found here. These benchmark instances have been considered by 1 result

### Simplified Intraday Particle Therapy Patient Scheduling Problem (SI-PTPSP)

The instances can be found here. For details on the instance format see the included README file.

The following publication considers these test instances:

1 result

2020 | |

[1] | An Iterative Time-Bucket Refinement Algorithm for a High-Resolution Resource-Constrained Project Scheduling ProblemInternational Transactions in Operational Research, jan 2020. |

## Job Sequencing with One Common and Multiple Secondary Resources (JSOCMSR)

Instances for the JSOCMSR can be found here

## Districting and Routing Problem for Security Control

Contact: Benjamin Biesinger, Christian Kloimüllner

Instances for the published results can be found here.

## Dial-a-Ride Problem

Contact: Martin Riedler, Günther Raidl

Instances including a description of the used file format can be found here.

## Network Design Problem with Relays

Contact: Markus Leitner, Ivana Ljubic, Martin Riedler, Mario Ruthmair

Instances including a description of the used file format can be found here.

Further instances from the literature can be found at https://sites.psu.edu/auk3/research/test-problems/.

## Directed Network Design Problem with Relays

Contact: Markus Leitner, Ivana Ljubic, Martin Riedler, Mario Ruthmair

The modified instances by Cabral et al. are available here.

Our newly generated Euclidean instances can be found here.

The used instance format is described in format-description.txt.

The instances by Konak can be retrieved at https://sites.psu.edu/auk3/research/test-problems/.

## Rooted Delay-Constrained Minimum Spanning Tree Problems

Contact: Mario Ruthmair

- C++-Code for reading instance format
- complete instance graphs with 100, 200, 500, 1000 nodes and random integer edge costs and delays in [1,99]

## Consensus Tree Problem

Contact: Sandro Pirkwieser

- instances based on real data
- new artificially generated instances
- new artificially generated small instances

## Periodic Vehicle Routing Problem with Time Windows

Contact: Sandro Pirkwieser

We created instances based on Solomon's VRPTW instances with 100 customers:

- planning period of four days
- planning period of six days
- planning period of eight days

Of the newly created instances with a planning horizon of four days we generated smaller ones for the exact approaches:

- having 36 customers
- having 50 customers

## Periodic Vehicle Routing Problem and Periodic Traveling Salesman Problem

Contact: Sandro Pirkwieser

We created larger instances having 336 to 576 customers and a planning horizon of four or six days

## Vehicle Routing Problem with Compartments

Contact: Sandro Pirkwieser

- benchmark instances of Derigs et al. available here
- modified petrol benchmark instances of Derigs et al. exhibiting a harder packing subproblem

## Bi-level Vehicle Routing Problem

Contact: Günther R. Raidl, Bin Hu

## Balancing Bicycle Sharing System (BBSS) Problem

Contact: Christian Kloimüllner, Petrina Papazek

The homepage of the Balancing Bicylce Sharing System (BBSS) project can be found here.

Our instances are based on real data from Citybike Wien. We got information about 92 stations which contain fill levels at different time in the system, capacity of stations, geographic coordinates, and traveling times between stations.

We constructed instances which contain:

- capacity,
- initial fill level,
- target fill level of stations,
- traveling times, and
- (user) demand values for dynamic rebalancing.

Furthermore, our instances have different size of stations, namely, 10, 20, 30, 60, 90, 120, 180, 240, 300, 400, 500, 600 and 700. Thus, we got a set of artificial stations from our partner, the AIT (Austrian Institute of Technology), which extend the real data we got from Citybike Wien. In particular, we choose the stations for our instances randomly from a set of 92 real stations plus 664 artificial stations.

For the following set of instances we took a snapshot from the system of Citybike Wien to derive initial fill levels for the stations. Furthermore, we set the target value of stations to be 50% of their capacities. We used exactly one depot and also one travel time matrix and the demands for the stations are derived randomly for eight different time points.

- bench2: Benchmark instances based on data from Citybike Wien (used in [1-3, 6])

In EVOCOP-2013 results we list complete computational results based on bench 2 for comparing our auxilary algroithms for deriving loading operations described in [2013,4].

The next benchmark instances contain (user) demand values for the real stations which we got from our partner, the AIT. For the artificial stations we calculated random demand values according to a Beta distribution.

Moreover, we adopted the initial fill levels and target values. The initial fill levels for the artificial stations have been calculated the same way like we did it for the demands, i.e., such that the distribution of the fill levels for artificial stations is similar to that one of the real stations. The target values were set according to their demand. For stations with a high bike demand we set the target value to be 75% of the stations capacity, for stations with a high slot demand to 25% and if both, the bike- as well as the slot demand, are similar we set their target value to 50% of the capacity.

Additionally, we provided four different travel time matrices which show the traveling time at 4:30 am, 8:00 am, 12:00 pm, as well as 6:15 pm.

- bench3: Benchmark instances with advanced initial and target fill levels and time-varying travel times (used in [4,5])

Publications using these benchmark instances

7 results## Mulitmodal Home-Healthcare Scheduling (MHS) Problem

Contact: Günther R. Raidl, Matthias Prandtstetter

- Appendix to "Metaheuristics for Solving a Multimodal Home-Healthcare Scheduling Problem", submitted to Central European Journal of Operations Research
- Benchmark instances based on real world data

## Competitive Facility Location Problems

Contact: Benjamin Biesinger, Bin Hu, Günther R. Raidl

- Benchmark instances with 50 and 100 customers for the Leader-Follower Facility Location Problem with Proportional Customer Behavior
- Benchmark instances with 150 and 200 customers for the Discrete (r|p)-Centroid Problem (RPCP)
- Full result tables of "A Hybrid Genetic Algorithm with Solution Archive for the Discrete (r|p)-Centroid Problem", accepted by Journal of Heuristics

## Multi Layer Hierarchical Ring Network Design Problem

Contact: Christian Schauer, Günther R. Raidl

- Benchmark instances ranging from 22 to 439 nodes
- All results for the Multi-Commodity Flow Based Mixed Integer Linear Programming Approach

## Two Dimensional Pre-Marshalling Problem

Contact: Günther Raidl Benchmark instances for the Two Dimensional Pre-Marshalling Problem (2D-PMP) with 4,6,8,10,12,and 14 columns width, 4 stacks height and 50% and 75% fullness ratio. By combining these parameters we obtain a total of 6*1*2=12 categories of instances. Each category contains 50 instances. The instances were generated using the instance generator found at (https://sites.google.com/site/gciports/premarshalling-problem/bay-generator) provided by:

- Exposito-Izquierdo, C., Melian-Batista, B., Moreno-Vega, M.: Pre-marshalling problem: Heuristic solution method and instances generator. Expert Systems with Applications 39(9) (2012) 8337-8349

File names are encoded using the following key: instance_w_h_c_x.txt

- w - width
- h - height
- c - number of containers within bay (defined by fullness ratio)
- x - instance number within category

## Generalized Vehicle Routing Problem with Stochastic Demands

Contact: Benjamin Biesinger, Bin Hu, Günther R. Raidl

- Benchmark instances for the Generalized Vehicle Routing Problem with Stochastic Demands based on the instances for the GVRP (http://www.personal.soton.ac.uk/tb12v07/gvrp.html) using the same format. In the demand section the expected demand d for each cluster is listed along with a number x. This number determines the possible demand values which are given by D={d-ceil(x*d),...,d+ceil(x*d)} and each demand value has equal probability 1 / |D|.
- Full result tables of "A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands", accepted by the EvoCOP 2015 coference.

## Virtual Network Mapping Problem

(Contact: Johannes Inführ, Günther Raidl)