论文标题
重新审视hurdle的调度问题,V.F.,1973年:一种新颖的数学解决方案方法和两种扩展
Revisit the scheduling problem in Hurdle, V.F., 1973: A novel mathematical solution approach and two extensions
论文作者
论文摘要
Hurdle(1973)中的调度问题是以一般形式提出的,同时涉及车辆派遣,循环,机队尺寸和顾客排队。作为一个约束的变异问题,数十年来一直无法完全解决。通过图形分析的技术能力,作者推出了最佳调度率的封闭式解决方案(虽然没有确定的关键变量),但仅建议最佳车队尺寸的下限和上限。此外,这种图形分析方法在计算特定的调度问题方面缺乏高效率,这些问题通常是大规模的(例如,数百个总线线路)。鉴于此,本文提出了一种新型的数学解决方案方法,该方法首先将原始问题放松到无约束的问题,然后使用变化的计算来攻击它。相应的Euler-Lagrange方程得出了最佳调度率的封闭形式解决方案,赫尔德的结果是一种特殊情况。多亏了拟议的方法,也可以解决最佳的车队尺寸。本文通过形式化解决方案方法并概括结果来完成Hurdle(1973)的工作。基于此,我们进一步对具有多个起源和目的地以及混合大小或模块化总线的一般总线线的调度问题进行了两次扩展。还可以通过新的见解获得封闭形式的结果。除其他外,我们发现航天飞机/进料线的解决方案是我们一般公交线结果的特殊情况。还提供了数值示例,以证明所提出方法的有效性和效率。
The scheduling problem in Hurdle (1973) was formulated in a general form that simultaneously concerned the vehicle dispatching, circulating, fleet sizing, and patron queueing. As a constrained variational problem, it remains not fully solved for decades. With technical prowess in graphic analysis, the author unveiled the closed-form solution for the optimal dispatch rates (with key variables undetermined though), but only suggested the lower and upper bounds of the optimal fleet size. Additionally, such a graphic analysis method lacks high efficiency in computing specific scheduling problems, which are often of a large scale (e.g., hundreds of bus lines). In light of this, the paper proposes a novel mathematical solution approach that first relaxes the original problem to an unconstrained one, and then attacks it using calculus of variations. The corresponding Euler-Lagrange equation yields the closed-form solution of the optimal dispatching rates, to which Hurdle's results are a special case. Thanks to the proposed approach, the optimal fleet size can also be solved. This paper completes the work of Hurdle (1973) by formalizing a solution method and generalizing the results. Based on that, we further make two extensions to the scheduling problem of general bus lines with multiple origins and destinations and that of mixed-size or modular buses. Closed-form results are also obtained with new insights. Among others, we find that the solutions for shuttle/feeder lines are a special case to our results of general bus lines. Numerical examples are also provided to demonstrate the effectiveness and efficiency of the proposed approach.