Lin Zhiyuan, Kwan Raymond S K
School of Computing, University of Leeds, Leeds, LS2 9JT UK.
Comput Optim Appl. 2016;64(3):881-919. doi: 10.1007/s10589-016-9831-3. Epub 2016 Feb 12.
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.
基于先前在铁路车辆调度问题方面的研究工作（阿尔菲耶里等人，《交通科学》，2006年，第40卷，第378 - 391页；卡恰尼等人，《数学规划B》，2010年，第124卷，第207 - 231页；林和关，《离散数学电子笔记》，2013年，第41卷，第165 - 172页；施里弗，《CWI季刊》，1993年，第6卷，第205 - 217页；齐亚拉蒂等人，《管理科学》，1999年，第45卷，第1156 - 1168页），我们推广了一类整数多商品流问题的局部凸包方法，并讨论了其在高维情况下的可行范围。假设在满足某些条件时，局部凸包可分为上包、主包和下包，理论证明主包最多只能有两个非零面。上包和下包中的点数主要通过实证进行探索。局部凸包的上述性质促使我们在巴伯等人（《美国计算机协会数学软件汇刊》，1996年，第22卷，第469 - 483页）提出的原始版本基础上，对快速凸包算法进行了略微修改（即“双面孔快速凸包算法”）。至于将该方法应用于铁路车辆调度的可行性，我们经过实证实验发现，对于英国两家主要的铁路运营公司——苏格兰铁路公司和南方铁路公司的问题实例，即使在最困难的实际或人工条件下（例如假设一列火车可由11种兼容的自供电单元中的任何一种提供服务），标准快速凸包算法（巴伯等人，《美国计算机协会数学软件汇刊》，1996年，第22卷，第469 - 483页）也能轻松计算出相关凸包。对于一些甚至更困难的人工实例，这些实例可能超出铁路车辆调度的范围（例如图中的一个节点可被11种以上兼容商品覆盖），有证据表明，对于我们测试的实例，“双面孔快速凸包算法”比标准快速凸包算法更具优势。当商品类型数量更高（例如>19），或者高维空间中的点数（例如15维）不小（例如>2000）时，无论是标准快速凸包算法还是双面孔快速凸包算法，都无法在实际时间内计算出局部凸包。
