...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>INFORMS journal on computing >Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem
【24h】

Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem

机译：在时间窗口分配车辆路由问题中寻址定向对称性

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

摘要

The time window assignment vehicle routing problem (TWAVRP) is the problem of assigning time windows for delivery before demand volume becomes known. This implies that vehicle routes in different demand scenarios have to be synchronized such that the same client is visited around the same time in each scenario. For TWAVRP instances that are relatively difficult to solve, we observe many similar solutions in which one or more routes have a different orientation, that is, the clients are visited in the reverse order. We introduce an edge-based branching method combined with additional components to eliminate orientation symmetry from the search tree, and we present enhancements to make this method efficient in practice. Next, we present a branch-price-and-cut algorithm based on this branching method. Our computational experiments show that addressing orientation symmetry significantly improves our algorithm: The number of nodes in the search tree is reduced by 92.6% on average, and 25 additional benchmark instances are solved to optimality. Furthermore, the resulting algorithm is competitive with the state of the art. The main ideas of this paper are not TWAVRP specific and can be applied to other vehicle routing problems with consistency considerations or synchronization requirements.
机译：时间窗口分配车辆路由问题（TWAVRP）是在需求卷已知之前分配时间窗口以进行交付的问题。这意味着不同需求场景中的车辆路线必须同步，使得同一客户端在每个场景中同时访问。对于相对难以解决的TwaVRP实例，我们观察许多类似的解决方案，其中一个或多个路由具有不同的方向，即，以相反的顺序访问客户端。我们引入了基于边缘的分支方法，结合了附加组件，以消除从搜索树中的取向对称性，并且我们提高了在实践中实现了这种方法的增强功​​能。接下来，我们介绍了一种基于该分支方法的分支降价算法。我们的计算实验表明，寻址方向对称性显着提高了我们的算法：搜索树中的节点数量平均减少了92.6％，并且可以解决25个额外的基准实例。此外，所得到的算法与现有技术具有竞争力。本文的主要思想不是TWAVRP特定，可以应用于其他车辆路由问题，具有一致性考虑因素或同步要求。

著录项

  • 来源
    《INFORMS journal on computing》 |2021年第2期|495-510|共16页
  • 作者

    Kevin Dalmeijer; Guy Desaulniers;

  • 作者单位

    H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta Georgia 30332 Econometric Institute Erasmus School of Economics Erasmus University Rotterdam 3062 PA Rotterdam Netherlands;

    Department of Mathematics and Industrial Engineering Polytechnique Montreal Montreal Quebec H3T 1J4 Canada Group for Research in Decision Analysis (GERAD) Montreal Quebec H3T 1J4 Canada;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    vehicle routing; time window assignment; symmetry; synchronization; consistency; branch-price-and-cut;

    机译：车辆路线;时间窗口分配;对称;同步;一致性;分支价格和切割;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号