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

该研究计划旨在研究几类带同步约束的车辆路径问题，提出建模方法和高效的精确启发式算法。值得注意的是，我们考虑了带有换乘的车辆路径问题和多梯队的车辆路径问题。这类车辆路径问题有一个共同的特点：由于换乘点或集合点的同步，潜在的时间问题在决定给定解决方案的效率方面起着至关重要的作用。事实上，如果计时问题处理不当，人们最终可能会得到一个可能在旅行时间方面更便宜的解决方案，但在总乘车时间(包括由于同步不正确而导致的停顿时间)方面则要昂贵得多。方法论计划可以总结如下：首先，我们试图为这类车辆路径问题建立适当的混合整数模型。我们对任何类型的模型都不感兴趣，而是那些允许我们在精确求解器或启发式算法的背景下开发每个问题的底层结构的模型。对于精确的求解器，我们将考虑已知的范例，如分支切割法、列生成框架和Bders分解。另一方面，我们将开发基于邻域搜索和整数规划方法的启发式算法，后者是对之前开发的精确方法的适应。我们将用实际应用于现实生活中的物流问题来补充这些理论和算法的发展。为此，我们将寻找可能有兴趣将本研究计划期间应用的一些技术应用于其运营规划的行业合作伙伴。

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.