开放式车辆路径问题及其应用研究

交通运输是国民经济的动脉，它对社会经济发展和人民生活起着极为重要的作用。各种运输方式在日常运输营运管理工作中都要面对这样一个共同的问题：如何为其载运工具(汽车、列车、轮船和飞机，以下统称为车辆)确定行驶路线及其时刻表，才能有效地运送各站点间的旅客和货物。运筹学界将此类问题统称为车辆路径问题。 可见，车辆路径问题是运输组织优化中的核心问题。在过去三十年间，以物流配送运输线路优化选择为背景的车辆路径问题得到了广泛的研究，并取得了丰富的研究成果。本文将首先对此类问题的特点、分类以及求解算法的研究现状等进行综述。 开放式车辆路径问题，是另一种类型的车辆路径问题，同时也是交通运输运筹学的一个新的研究领域，有着广泛的应用前景。它与基本的车辆路径问题的主要不同点是不要求车辆完成运输任务后返回原出发点，或者是若要求返回原出发点，则沿原去程路线返回。本文对带路程长度和装载能力约束的开放式车辆路径问题从理论上进行了研究。通过利用所研究的问题的特点，提出了新的邻域结构、并在搜索过程中引入一种随机多样性等，从而构造了一个求解该问题的禁忌搜索算法。分别以用随机方式和本文所提出的“最远者优先启发式算法”产生的初始解出发，用该禁忌搜索算法对16个标准测试问题进行求解，并与文献中相关算法的计算结果进行比较，其中有9个问题得到了更好的最终解。通过将从两种方式产生的初始解开始的求解效果进行比较，表明用该禁忌搜索算法求解这些基于完备网络的测试问题时，其初始解对最终解的质量没有太大的影响。 在理论研究的基础上，对带装载能力约束的开放式车辆路径问题的一个案例，校车路径问题进行了研究。通过分析，将该问题归结为一个多目标组合优化问题。根据问题的特殊结构，提出了求解该问题的一个基于最优化方法的启发式算法。用香港的一所幼儿园的数据对算法进行了测试，结果表明，用该算法所求出的校车线路与现有的手工方法相比，学生所花费的总乘车时间减少了29％；校车载有学生时的总行驶时间平均缩短22.8％。 此外，铁路旅客列车开行方案及其运行图编制问题也可以归结为一类带软时间窗约束的开放式车辆路径问题，本文对该案例问题的一个子问题，即旅客列车运行方案图编制问题，从新的角度进行了研究。 通过对问题的分析，认为在编图时，不同等级列车、路网上不同车站、 以及要优化的目标的重要性是不同的，不同旅行距离的旅客对始发和 终到时间窗也有着不同的偏好。基于这些事实，将问题归结为一个多 目标规划问题，并运用分层序列法的思想，将此多目标规划问题化为 多个单目标规划问题来求解。在定性分析的基础上，给出了系统的、 对列车始发点或终到点进行优化的定量分析方法。按照列车等级和车 站重要性的顺序，首先最小化总的旅客不方便程度，在此基础上再最 小化所需要的客车车底数。借助于求解带软时间窗的车辆路径问题时 构造惩罚函数的思想，引入了当列车的到发点落在不同的时间窗里 时，在不方便旅客和车底需要数方面的惩罚值，进而把问题转化为指 派问题来求解。为了求出相应的指派问题的所有最优解，又通过研究 提出了一个求指派问题所有最优解的分枝定界法。通过用全国铁路旅 客列车时刻表中的有关数据对这套算法进行测试，得到了满意的结 果。该套算法总能给出可行解，在编制旅客列车运行方案图时可被用 来对旅客列车的始发和终到时间窗进行优化，以便编图人员或计算机 辅助编图系统在编图时，从中选择列车始发点或终到点。