• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Methodes hybrides basees sur la generation de colonnes pour des problemes de tournees de vehicules avec fenetres de temps.
【24h】

Methodes hybrides basees sur la generation de colonnes pour des problemes de tournees de vehicules avec fenetres de temps.

机译：基于带有时间窗的车辆路径问题的列生成的混合方法。

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

摘要

In this thesis, we present an efficient heuristic method for solving a number of large-scale vehicle routing problems with time windows. The problems tackled are rich in the sense that they contain many non-conventional complex characteristics arising in real applications. We propose a hybrid between a large neighborhood search metaheuristic and a column generation exact method, hitherto the most efficient to solve constrained vehicle routing problems exactly.;Several operators are defined to select elements that will be removed from the incumbent solution in the destruction phase. At every iteration, an operator is randomly selected favoring those who managed to improve the incumbent solution in the past iterations. Afterwards, column generation is used to explore the neighborhood defined by the operator (reconstruction phase). Many aspects of the column generation approach are managed heuristically in order to obtain good solutions in reasonable time at the expense of ensuring optimality. The subproblems are solved by means of a tabu search algorithm and the column generation is stopped if the value of the solution of the linear relaxation does not improve enough over the last iterations. An aggressive branching scheme is used to derive integer solutions. Branching is done on the variable with the highest fractional value, which is fixed at 1 without the possibility to backtrack.;The proposed method is first developed in Chapter 4 for the vehicle routing problem with time windows. The objective is to minimize first the number of vehicles, and then the total distance traveled. That is why the method is adapted in two phases, one for each objective. At time of experimentation, the method managed to improve the best known solutions of 106 over 356 instances of size going from 100 to 1000 customers.;In order to put the method to the test on a more complex problem with real applications, European rules on driver working hours are added to the problem in Chapter 5. Indeed, as of April 2007, an update of the rules governing the driver working hours is in place in the European Union. Even though the rules have a concrete and very practical aspect, very few scientific papers were published on the subject from an optimization point of view. To check the feasibility of a route, a label-setting algorithm is proposed. The driver rules are modeled using complex resource extension functions that can generate multiple labels from one source label. Every time an insertion is evaluated by the tabu search solving the subproblem, the resulting route is checked for feasibility. We also demonstrate how to consider multiple insertions at once by bounding the resource values at each node of the current route of the tabu search. The computed bounds are also used to limit the domain of the label-setting algorithm. The method proposed to check the feasibility of the routes is generic for any algorithm using insertion movements. Compared to two other methods on academic instances, ours is definitely superior.;Finally, the method is generalized in Chapter 6 to a real problem arising in the heating oil distribution industry. Much more complex, the column generation formulation of the problem requires multiple subproblems. In addition, there is a heterogeneous fleet, start and end time of working shifts, multiple depots, intra-route replenishments and optional customers. It is however possible to had a move to the tabu search algorithm solving the subproblems, in order to switch between subproblems without slowing down the method too much. A concurrent tabu search is also presented to solve the whole problem. This method is also inserted into the large neighborhood search algorithm to explore the neighborhoods instead of the heuristic column generation. Computational results show that the large neighborhood search can be a good guiding mechanism for a metaheuristic. However the column generation reconstruction outperforms its tabu search counterpart over the solved instances. (Abstract shortened by UMI.)
机译：在本文中，我们提出了一种有效的启发式方法，用于解决带有时间窗的许多大型车辆路径问题。从实际意义上讲，它们包含了许多非常规的复杂特性，从某种意义上讲，解决的问题是丰富的。我们提出了一种在大型邻域搜索元启发式方法和列生成精确方法之间的混合方法，这是迄今为止精确解决约束车辆路径问题的最有效方法。定义了多个算子来选择在破坏阶段要从现有解决方案中删除的元素。在每次迭代中，都会随机选择一个运算符，以偏爱那些在过去的迭代中设法改善现有解决方案的人员。之后，使用列生成来探索操作员定义的邻域（重建阶段）。试探性地管理列生成方法的许多方面，以便在合理的时间内获得良好的解决方案，但要以确保最佳性为代价。子问题通过禁忌搜索算法解决，并且如果线性松弛解的值在最后一次迭代中没有得到足够的改善，则停止列生成。主动分支方案用于导出整数解。在分数值最大的变量上进行分支，该变量固定为1，没有回溯的可能性。所提出的方法首先在第4章中针对带有时间窗的车辆路径问题进行了开发。目的是首先使车辆数量最少，然后使总行驶距离最小。因此，该方法分为两个阶段，每个目标一个阶段。在试验时，该方法设法改进了356个实例（从100个到1000个客户）中106个最著名的解决方案。为了在实际应用中对更复杂的问题进行测试，欧洲对驾驶员工作时间已添加到第5章中。实际上，自2007年4月起，欧盟已对驾驶员工作时间进行了更新。即使规则具有具体且非常实用的方面，但从优化的角度来看，关于该主题的科学论文也很少发表。为了检查一条路线的可行性，提出了一种标签设置算法。使用复杂的资源扩展功能对驱动程序规则进行建模，这些功能可以从一个源标签生成多个标签。每次通过禁忌搜索解决子问题来评估插入时，都会检查所得路线的可行性。我们还演示了如何通过限制禁忌搜索当前路径的每个节点处的资源值来一次考虑多个插入。计算的边界还用于限制标签设置算法的范围。提出的检查路线可行性的方法对于使用插入运动的任何算法都是通用的。相较于其他两种在学术上的方法，我们的方法绝对是优越的。最后，该方法在第六章中被概括为一个在取暖用油分销行业中出现的实际问题。更复杂的是，问题的列生成公式需要多个子问题。此外，还有不同的车队，轮班的开始和结束时间，多个仓库，路线内补给和可选客户。但是，有可能转向解决子问题的禁忌搜索算法，以便在子问题之间切换而不会使方法变慢。还提出了并行禁忌搜索来解决整个问题。该方法也被插入到大型邻域搜索算法中以探索邻域，而不是启发式列生成。计算结果表明，大邻域搜索可以成为元启发式算法的良好指导机制。但是，在生成的实例上，列生成重建的性能优于其禁忌搜索。 （摘要由UMI缩短。）

著录项

  • 作者

    Prescott-Gagnon, Eric.;

  • 作者单位

    Ecole Polytechnique, Montreal (Canada).;

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

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号