The time-dependent capacitated profitable tour problem with time windows and precedence constraints
The time-dependent capacitated profitable tour problem with time windows and precedence constraints
复制标题
DOI：
10.1016/j.ejor.2017.07.004
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
P. Sun;Lucas P. Veelenturf;S. Dabia;T. Woensel
中科院分区：
文献类型：
--
作者：
P. Sun;Lucas P. Veelenturf;S. Dabia;T. Woensel
引入了带时间窗和优先约束的时间依赖的有能力约束的有利可图的旅游问题。这个问题涉及到确定一个行程和它在停车场的出发时间，使所收集的利润减去总旅行成本（由总旅行时间衡量）最大化。为了应对道路拥堵，行程时间被认为是时间相关的。我们开发了一个量身定制的标签算法来找到最佳的旅游。此外，我们引入优势准则，以丢弃没有前途的标签。我们的计算结果表明，该算法能够解决最多150个位置（75个拾取和交付请求）的最优实例。此外，我们提出了一个受限制的动态规划启发式，以提高计算时间。这种启发式算法不能保证最优性，但能够为34个实例中的32个实例找到最优解。
We introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time-dependent. We develop a tailored labeling algorithm to find the optimal tour. Furthermore, we introduce dominance criteria to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 150 locations (75 pickup and delivery requests) to optimality. Additionally, we present a restricted dynamic programing heuristic to improve the computation time. This heuristic does not guarantee optimality, but is able to find the optimal solution for 32 instances out of the 34 instances.