Mathematical programming techniques for the solution of hard combinatorial optimization problems arising in transportation

用于解决运输中出现的硬组合优化问题的数学编程技术

• 批准号: 435824-2013
• 负责人: ContardoVera, Claudio
• 金额: $ 1.6万
• 依托单位: Université du Québec à Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=574193
• 关键词: Mathematical; programming; techniques; solution; hard

This research plan is intended to study several classes of vehicle routing problems with synchronization constraints, to propose modeling approaches and efficient exact and heuristic algorithms. Notably, we consider vehicle routing problems with transfers and multiple-echelon vehicle routing problems. These classes of vehicle routing problems share a common characteristic: either because of synchronization at transfer points or consolidation points, the underlying timing issue plays a crucial role in determining the efficiency of a given solution. Indeed, if the timing issue is not properly handled, one may end with a possibly cheaper solution in terms of traveling time, but much more expensive in terms of total ride time (which includes the dead times due to improper synchronization). The methodological plan can be summarized as follows: First, we seek to develop appropriate mixed-integer models for these classes of vehicle routing problems. We are not interested in just any type of model, but the ones that will allow us to exploit the underlying structure of each problem, either in the context of an exact solver or a heuristic algorithm. For the exact solvers, we will consider known paradigms such as the branch-and-cut method, the column generation framework and Benders decomposition. On the other hand, we will develop heuristic algorithms based on neighborhood search coupled with integer programming methods, the latter being adaptations of the exact methods developed before. We will complement these theoretical and algorithmic developments with actual applications to real-life logistics problems. To that end, we will search for industrial partners that may be interested into applying some of the techniques applied during this research plan to their operational planning.

本研究计画针对几类具有同步限制的车辆路径问题进行研究，提出模型化方法及有效的精确与启发式演算法。值得注意的是，我们认为车辆路径问题的转让和多级车辆路径问题。这些类别的车辆路径问题有一个共同的特点：无论是因为在转移点或合并点的同步，基本的时间问题起着至关重要的作用，在确定给定的解决方案的效率。实际上，如果定时问题没有被适当地处理，则可能以在行进时间方面可能更便宜的解决方案结束，但是在总行驶时间（其包括由于不适当的同步而导致的死区时间）方面昂贵得多。 方法计划可以概括如下：首先，我们寻求开发适当的混合整数模型，这些类的车辆路径问题。我们对任何类型的模型都不感兴趣，而是那些允许我们利用每个问题的底层结构的模型，无论是在精确求解器还是启发式算法的上下文中。对于精确求解器，我们将考虑已知的范例，如分支切割方法，列生成框架和Benders分解。另一方面，我们将开发基于邻域搜索的启发式算法，再加上整数规划方法，后者是以前开发的精确方法的适应。 我们将补充这些理论和算法的发展与实际应用到现实生活中的物流问题。为此，我们将寻找可能有兴趣将本研究计划中应用的一些技术应用于其运营规划的工业合作伙伴。