• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Affectation de locomotives aux trains avec contraintes d'entretien et de carburant.
【24h】

Affectation de locomotives aux trains avec contraintes d'entretien et de carburant.

机译：在维护和燃油受限的情况下，将机车分配给列车。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this thesis, we consider the problem of assigning locomotives to a large number of trains scheduled over a one-week or a one-month horizon while taking into account maintenance and, possibly, fueling constraints. Since the locomotives are all of the same type, demand for each train is expressed as a minimum number of locomotives. Maintenance and fueling constraints are given as minimum and maximum traveled distances between two consecutive maintenances or fuelings. Availability constraints for the locomotives and the maintenance shops must also be taken into account, as well as locomotive initial conditions. Locomotives can go to maintenance and fueling at all times without violating any constraints even if this requires traveling alight (with an engineer) or in deadhead (without engineer) pulled by one or several other locomotives. The objective consists of minimizing first the total number of locomotives used, second the total operational cost including the distance traveled in light moves and in deadhead, and last delayed maintenances with respect to the minimum distance between two maintenances. Despite similarities between this problem and those studied in the literature, the former requires a different approach because of the large number of trains to cover augmented by the large number of potential light moves, and also because of the constraints for different maintenance types and for fuel. Moreover, to treat the initial conditions of the locomotives, they roust be handled individually.; The problem is modeled by adapting the generic nonlinear multicommodity network flow model proposed in 1998 by Desaulniers, Desrosiers, Ioachim, Solomon and Soumis for tackling a large class of deterministic vehicle routing and crew scheduling problems. Each locomotive represents a commodity and is associated with a timespace network. Instead of developing a generic approach for all locomotive types, we develop a first approach for the problem of assigning electric locomotives and a second one for the problem of assigning diesel locomotives. These last locomotives need fueling about once per day and maintenance less frequently. The first approach works when short time maintenances like fueling is not considered. The second one is an extension of the first which includes a special treatment of the fueling constraints.; Given the size of the instances to solve for the electric locomotives, we propose a solution approach based on several decomposition strategies. Firstly, the planning horizon is discretized into overlapping time slices and a reasonable-sized problem is solved for each slice. Secondly, a small integer linear problem is solved to identify locomotives that need maintenance during the current time slice. These locomotives are said to be critical and the others non-critical. The routing of the critical locomotives is then performed sequentially by solving, for each of these locomotives, a shortest path problem with resource constraints. Finally, the non-critical locomotives are routed simultaneously by solving an integer linear problem. To improve solution quality, we propose two different modifications to this basic approach. The first corrects the greedy aspect of the critical locomotive routing procedure by reconsidering some parts of their routes in the time slice. The second uses the dual information obtained by solving a priori a relaxed version of the problem for better guiding the critical locomotives during their routing. Two other modificatons are also proposed for improving computational times. The first replaces the integer linear model for the non-critical locomotives by an equivalent network flow model. The second reduces the size of the underlying networks by efficiently selecting potential light moves.; When fueling is treated like maintenance, the first approach becomes almost totally greedy because almost all locomotives are critical for fueling in each time slice. To alleviate this difficulty, we propose
机译：在本文中，我们考虑将机车分配给安排在一周或一个月的时间范围内的大量列车的问题，同时考虑到维护和可能加油的约束。由于机车是相同类型的，因此对每个列车的需求表示为最小数量的机车。维护和加油限制条件是两次连续维护或加油之间的最小和最大行驶距离。还必须考虑机车和维修车间的可用性约束以及机车的初始条件。机车可以随时进行维护和加油，而不会违反任何约束条件，即使这需要由一名或数名其他机车拖下车（由一名工程师）或在无人驾驶的头部（无一名工程师）下进行。目标包括首先最大程度地减少所使用的机车总数，其次将总运营成本（包括轻型飞机和无人驾驶飞机所经过的距离）以及相对于两次维护之间的最小距离的最后延迟维护最小化。尽管该问题与文献中研究的问题相似，但前者仍需要采取不同的方法，因为有大量的火车可以覆盖大量潜在的轻运动，并且由于维护类型和燃料的限制。此外，为了处理机车的初始状况，应对它们进行单独处理。该问题是通过采用Desaulniers，Desrosiers，Ioachim，Solomon和Soumis在1998年提出的通用非线性多商品网络流动模型来建模的，以解决一大类确定性车辆路线和人员调度问题。每个机车代表一种商品，并与时空网络关联。我们没有为所有机车类型开发通用方法，而是为分配机车的问题开发了第一种方法，为柴油机车的问题开发了第二种方法。这些最后的机车每天需要加油一次，并且保养频率降低。第一种方法在不考虑加油等短期维护的情况下起作用。第二个是第一个的扩展，其中包括对加油限制的特殊处理。给定实例的大小来解决电力机车，我们提出了一种基于几种分解策略的解决方案。首先，将计划范围离散为重叠的时间片，并为每个片解决一个合理大小的问题。其次，解决了一个小的整数线性问题，以识别在当前时间段内需要维护的机车。据说这些机车是关键的，而其他则不是关键的。然后，通过为这些机车中的每一个解决具有资源约束的最短路径问题，依次执行关键机车的路由。最后，通过求解整数线性问题，同时路由非关键机车。为了提高解决方案质量，我们建议对此基本方法进行两种不同的修改。第一种通过在时间片中重新考虑其机车路线的某些部分来纠正关键机车路线程序的贪婪方面。第二种方法使用通过先验地解决问题的宽松版本而获得的双重信息，以便在关键机车的选路过程中更好地指导机车。还提出了两个其他改进措施，以缩短计算时间。第一种方法是用等效的网络流量模型代替非关键机车的整数线性模型。第二种通过有效地选择潜在的光移动来减小底层网络的大小。当将加油视为维护时，第一种方法几乎变得非常贪婪，因为几乎所有机车对于每个时间段的加油都是至关重要的。为了减轻这种困难，我们建议

著录项

  • 作者

    Diop, Mbaye.;

  • 作者单位

    Ecole Polytechnique, Montreal (Canada).;

  • 授予单位 Ecole Polytechnique, Montreal (Canada).;
  • 学科 Operations Research.
  • 学位 Ph.D.
  • 年度 2006
  • 页码 162 p.
  • 总页数 162
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 运筹学;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号