Local convex hulls for a special class of integer multicommodity flow problems

Zhiyuan Lin () and Raymond S. K. Kwan ()
Additional contact information
Zhiyuan Lin: University of Leeds
Raymond S. K. Kwan: University of Leeds

Computational Optimization and Applications, 2016, vol. 64, issue 3, No 11, 919 pages

Abstract: Abstract Based on previous work in rolling stock scheduling problems (Alfieri et al. in Transp Sci 40:378–391, 2006; Cacchiani et al. in Math Progr B 124:207–231, 2010; Lin and Kwan in Electron Notes Discret Math 41:165–172, 2013; Schrijver in CWI Q 6:205–217, 1993; Ziarati et al. in Manag Sci 45:1156–1168, 1999), 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 Barber et al. (ACM Trans Math Softw 22:469–483, 1996). 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. in ACM Trans Math Softw 22:469–483, 1996) 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.

Keywords: Integer multicommodity network flow; Convex hull computation; Rolling stock scheduling (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-016-9831-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:64:y:2016:i:3:d:10.1007_s10589-016-9831-3

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-016-9831-3

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().