Sioux Falls Variants for Network Design

Sioux Falls has been used quite often in the literature as a benchmark continuous network design problem (CNDP). Unfortunately, it occurs in several variants and it is often not quite clear from the cited references what variant was used in a specific paper. Sometimes the provided references, results and data are contradictory. Fredrik Hellman identified four variants of the Sioux Falls network, denoted A–D. The data for these four variants is provided here in machine-readable format. Description of the variants is given below (see also Bar-Gera et al. TBD). This is followed by a list of known references that contain Sioux-Falls CNDP results. The variant used in each reference is also indicated, in the cases that have been verified with the authors.

All four variants share the same objective function definition, and rely on the same Node Coordinates.

Variant A: Sioux-Falls A Network; Trip A Table. The objective function at the reference point (x=0) is 101.0615.

Variant B: Sioux-Falls B Network; Trip B Table. The objective function at the reference point (x=0) is 100.9690.

Variant C: Sioux-Falls C Network; Trip C Table. The objective function at the reference point (x=0) is 99.9413.

Variant D: Sioux-Falls D Network; Trip D Table. The objective function at the reference point (x=0) is 99.9411.

The Sioux Falls network was first published in Morlok et al. (1973) as traffic equilibrium network. The continuous network design problem on the Sioux Falls network was introduced in Abdulaal and LeBlanc (1979), but it is Suwansirikul et al. (1987) that has been most widely cited as the Sioux Falls benchmark network for algorithms on continuous network design problems; see e.g., Friesz et al. (1992); Marcotte and Marquis (1992); Meng et al. (2001); Lim (2002); Chiou (2005); Josefsson and Patriksson (2007); Luathep et al. (2011); Bar-Gera et al. (2013). The presentation of the Sioux Falls network design problem in Suwansirikul et al. (1987) is, however, ambiguous. The network data is defined both in a text with references and in two tables. It is indicated in the text that the network is the same as in Leblanc (1975); LeBlanc et al. (1975); LeBlanc and Morlok (1976); Abdulaal and LeBlanc (1979). However, the Sioux Falls networks presented in those papers are not mutually similar. For instance, links between nodes 15 and 19; 15 and 22; and 10 and 16 have different cost functions in Leblanc (1975) and LeBlanc et al. (1975). The table for cost function data in Suwansirikul et al. (1987) is identical to that in Leblanc (1975). Regarding the travel demand, the text in Suwansirikul et al. (1987) reads that the travel demand values have been multiplied by 0.11 compared to the source references. Multiplying the travel demand values from, e.g., Leblanc (1975) by 0.11 yields values equal to the travel demands presented in the table in Suwansirikul et al. (1987), except for the travel demand from node 16 to 9, which is 1.64 in Suwansirikul et al. (1987) instead of 1.54. Regarding the investment cost data, no deviations have been found.

In view of the above, let t(x) = a + b*x⁴ be the cost function and d the travel demand. The four variants are defined by:

A) a, b and d from the tables in Suwansirikul et al. (1987).

B) a, b and d from Leblanc (1975), with d multiplied by 0.11.

C) a, b and d from LeBlanc et al. (1975), with d multiplied by 0.11.

D) a and d from LeBlanc et al. (1975), b from Leblanc (1975), with d multiplied by 0.11.

Variant A is included since that is the network data presented in the tables in Suwansirikul et al. (1987). Variant B and C are included because they are both possible variants if you follow the references in the text in Suwansirikul et al. (1987).

Sioux-Falls CNDP results can be found in the following publications:

Publication	Variant
Abdulaal and LeBlanc (1979)
Suwansirikul et al. (1987)
Friesz et al. (1992)
Marcotte and Marquis (1992)
Meng et al. (2001)
Lim (2002)
Chiou (2005)
Josefsson and Patriksson (2007)	D
Luathep et al. (2011)
Bar-Gera et al. (2013)	C
Bar-Gera et al. (TBD)	B

References

1. Abdulaal, M., LeBlanc, L.J., 1979. Continuous equilibrium network design models. Transportation Research Part B 13, 19–32.

2. Bar-Gera, H., Hellman, F., Patriksson, M., 2013. Computational precision of traffic equilibria sensitivities in automatic network design and road pricing. Procedia - Social and Behavioral Sciences 80, 41–60. 20th International Symposium on Transportation and Traffic Theory (ISTTT 2013).

3. Bar-Gera, H., Hellman, F., Patriksson, M., TBD. Computational precision of traffic equilibria sensitivities in automatic network design and road pricing. Accepted for publication in Transportation Research Part B.

4. Chiou, S.W., 2005. Bilevel programming for the continuous transport network design problem. Transportation Research Part B 39, 383-361.

5. Friesz, T.L., Hsun-jung, C., Mehta, N.J., Tobin, R.L., Anandalingam, G., 1992. A simulated annealing approach to the network design problem with variational inequality constraints. Transportation Science 26, 18–26.

6. Josefsson, M., Patriksson, M., 2007. Sensitivity analysis of separable traffic equilibria, with application to bilevel optimization in network design. Transportation Research Part B 41, 4–31.

7. Leblanc, L.J., 1975. An algorithm for the discrete network design problem. Transportation Science 9, 183–199.

8. LeBlanc, L.J., Morlok, E.K., 1976. An analysis and comparison of behavioral assumptions in traffic assignment, in: Florian, M. (Ed.), Traffic Equilibrium Methods. Springer-Verlag, Berlin. volume 118 of Lecture Notes in Economics and Mathematical Systems, pp. 413-425.

9. LeBlanc, L.J., Morlok, E.K., Pierskalla, W.P., 1975. An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Research 9, 309–318.

10. Lim, A.C., 2002. Transportation Network Design Problems: AnMPEC Approach. Ph.D. thesis. Department ofMathematical Sciences, The Johns Hopkins University. Baltimore, MD, USA.

11. Luathep, P., Sumalee, A., Lam,W.H.K., Li, Z.C., Lo, H.K., 2011. Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach. Transportation Research Part B 45, 808–827.

12. Marcotte, P., Marquis, G., 1992. Efficient implementation of heuristics for the continuous network design problem. Annals of Operations Research 34, 163–176.

13. Meng, Q., Yang, H., Bell, M.G.H., 2001. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transportation Research Part B 35, 83–105.

14. Morlok, E.K., Schofer, J.L., Pierskalla, W.P., Marsten, R.E., Agarwal, S.K., Stoner, J.W., Edwards, J.L., LeBlanc, L.J., , Spacek, D.T., 1973. Development and Application of a Highway Network Design Model, Volumes 1 and 2. Final Report: FHWA Contract Number DOT-PH-11. Northwestern University.

15. Suwansirikul, C., Friesz, T.L., Tobin, R.L., 1987. Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem. Transportation Science 40, 540–542.