Local convex hulls for a special class of integer multicommodity flow problems. (English) Zbl 1352.90102

Summary: Based on previous work in rolling stock scheduling problems, we generalize a local convex hull method for a class of integer multicommodity flow problems, and discuss its feasibility range in high dimensional cases. Suppose a local convex hull can be divided into an up hull, a main hull and a down hull if certain conditions are met, it is shown theoretically that the main hull can only have at most two nonzero facets. The numbers of points in the up and down hull are explored mainly on an empirical basis. The above properties of local convex hulls have led to a slightly modified QuickHull algorithm (the “2-facet QuickHull”) based on the original version proposed by C. B. Barber et al. [ACM Trans. Math. Softw. 22, No. 4, 469–483 (1996; Zbl 0884.65145)]. As for the feasibility in applying this method to rolling stock scheduling, our empirical experiments show that for the problem instances of ScotRail and Southern Railway, two major train operating companies in the UK, even in the most difficult real-world or artificial conditions (e.g. supposing a train can be served by any of 11 compatible types of self-powered unit), the standard QuickHull [Barber et al., loc. cit.] can easily compute the relevant convex hulls. For some even more difficult artificial instances that may fall outside the scope of rolling stock scheduling (e.g. a node in a graph can be covered by more than 11 kinds of compatible commodities), there is evidence showing that the “2-facet QuickHull” can be more advantageous over the standard QuickHull for our tested instances. When the number of commodity types is even higher (e.g. \(>19\)), or the number of points in a high dimensional space (e.g. 15 dimensions) is not small (e.g. \(>2000\)), the local convex hulls cannot be computed either by the standard or the 2-facet QuickHull methods within practical time.


90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research


Zbl 0884.65145


Full Text: DOI


[1] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewoods Cliffs, USA (1993) · Zbl 1201.90001
[2] Alfieri, A; Groot, R; Kroon, LG; Schrijver, A, Efficient circulation of railway rolling stock, Transp. Sci., 40, 378-391, (2006)
[3] Barber, CB; Dobkin, DP; Huhdanpaa, H, The quickhull algorithm for convex hulls, ACM Trans. Math. Softw., 22, 469-483, (1996) · Zbl 0884.65145
[4] Bellmore, M; Bennington, G; Lubore, S, A multivehicle tanker scheduling problem, Transp. Sci., 5, 36-47, (1971)
[5] Cacchiani, V, Models and algorithms for combinatorial optimization problems arising in railway applications, Q. J. Oper. Res., 7, 109-112, (2009) · Zbl 1162.90330
[6] Cacchiani, V; Caprara, A; Toth, P, Solving a real-world train-unit assignment problem, Math. Progr. B, 124, 207-231, (2010) · Zbl 1198.90049
[7] Cacchiani, V., Caprara, A., Toth, P.: Models and algorithms for the train unit assignment problem. In: Combinatorial Optimization, Lecture Notes in Computer Science, vol. 7422, pp. 24-35. Springer, Heidelberg (2012) · Zbl 1312.90034
[8] Cacchiani, V; Caprara, A; Toth, P, A Lagrangian heuristic for a train-unit assignment problem, Discret. Appl. Math., 161, 1707-1718, (2013) · Zbl 1293.90035
[9] Cordeau, JF; Desaulniers, G; Lingaya, N; Soumis, F; Desrosiers, J, Simultaneous locomotive and car assignment at via rail Canada, Transp. Res. Part B Methodol., 35, 767-787, (2001)
[10] Cacchiani, V; Caprara, A; Maróti, G; Toth, P, On integer polytopes with few nonzero vertices, Oper. Res. Lett., 41, 74-77, (2013) · Zbl 1266.90129
[11] Cordeau, JF; Soumis, F; Desrosiers, J, Simultaneous assignment of locomotives and cars to passenger trains, Oper. Res., 49, 531-548, (2001) · Zbl 1163.90597
[12] Fioole, PJ; Kroon, L; Maróti, G; Schrijver, A, A rolling stock circulation model for combining and splitting of passenger trains, Eur. J. Oper. Res., 174, 1281-1297, (2006) · Zbl 1102.90312
[13] Grünbaum, B.: Measures of symmetry for convex sets. In: Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, vol. 7, p. 233. American Mathematical Society (1963)
[14] Lin, Z; Kwan, RSK, An integer fixed-charge multicommodity flow (FCMF) model for train unit scheduling, Electron. Notes Discret. Math., 41, 165-172, (2013)
[15] Lin, Z; Kwan, RSK, A two-phase approach for real-world train unit scheduling, Public Transp., 6, 35-65, (2014)
[16] Lingaya, N; Cordeau, JF; Desaulniers, G; Desrosiers, J; Soumis, F, Operational car assignment at VIA rail Canada, Transp. Res. Part B Methodol., 36, 755-778, (2002)
[17] Mahjoub, AR; Paschos, VT (ed.), Polyhedral approaches, chap. 10, 261-320, (2010), Hoboken, USA
[18] Maróti, G.: Operations research models for railway rolling stock planning. Ph.D. thesis, Eindhoven University of Technology, The Netherlands (2006)
[19] McMullen, P, The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184, (1970) · Zbl 0217.46703
[20] Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067
[21] Peeters, M; Kroon, LG, Circulation of railway rolling stock: a branch-and-price approach, Comput. Oper. Res., 35, 538-556, (2008) · Zbl 1141.90009
[22] Rouillon, S; Desaulniers, G; Soumis, F, An extended branch-and-bound method for locomotive assignment, Transp. Res. Part B Methodol., 40, 404-423, (2006)
[23] Schrijver, A, Minimum circulation of railway stock, CWI Q., 6, 205-217, (1993) · Zbl 0800.90397
[24] The Geometry Center of the University of Minnesota: The QuickHull’s official website. http://www.qhull.org/ · Zbl 1266.90129
[25] Varsi, G, The multidimensional content of the frustrum of the simplex, Pac. J. Math., 46, 303-314, (1973) · Zbl 0239.52003
[26] Webster, R.: Convexity. Oxford University Press, New York (1994) · Zbl 0835.52001
[27] Wolfenden, K., Wren, A.: Locomotive scheduling by computer. In: Proc. British Joint Computer Conference, vol. 1, pp. 31-37. IEEE Conference Publication No. 19, London, UK (1966)
[28] Wolsey, L.A.: Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1998) · Zbl 0930.90072
[29] Ziarati, K; Soumis, F; Desrosiers, J; Solomon, MM, A branch-first, cut-second approach for locomotive assignment, Manag. Sci., 45, 1156-1168, (1999) · Zbl 1231.90297
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.