• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Transportation Science >Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures
【24h】

Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures

机译：具有灵活进度表结构的周期性车辆路径问题的分支与价格和切入

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

摘要

This paper addresses the periodic vehicle routing problem with time windows (PVRPTW). Therein, customers require one or several visits during a planning horizon of several periods. The possible visiting patterns (schedules) per customer are limited. In the classical PVRPTW, it is common to assume that each customer requires a specific visit frequency and offers all corresponding schedules with regular intervals between the visits. In this paper, we permit all kinds of schedule structures and the choice of the service frequency. We present an exact branch-and-price-and-cut algorithm for the classical PVRPTW and its variant with flexible schedules. The pricing problems are elementary shortest-path problems with resource constraints. They can be based on one of two new types of networks and solved with a labeling algorithm, which uses several known acceleration techniques, such as the ng-path relaxation and dynamic halfway points within bidirectional labeling. For instances in which schedule sets fulfill a certain symmetry condition, we present specialized improvements of the algorithm, such as constraint aggregation and symmetry breaking. Computational tests on benchmark instances for the PVRPTW show the effectiveness of our algorithm. Furthermore, we analyze the impact of different schedule structures on run times and objective function values.
机译：本文解决带有时间窗（PVRPTW）的周期性车辆路径问题。其中，客户需要在几个时期的计划期内进行一次或多次访问。每个客户可能的访问方式（时间表）是有限的。在经典的PVRPTW中，通常假定每个客户都需要特定的访问频率，并提供所有相应的计划，并且两次访问之间的间隔是固定的。在本文中，我们允许各种时间表结构和服务频率的选择。我们为经典的PVRPTW及其变型方案提供了精确的分枝和削价算法，并具有灵活的时间表。定价问题是具有资源约束的基本的最短路径问题。它们可以基于两种新型网络之一，并可以通过标记算法解决，该算法使用了几种已知的加速技术，例如ng-path松弛和双向标记内的动态中途点。对于计划集满足一定对称性条件的实例，我们提出了该算法的专门改进，例如约束聚合和对称性破坏。对PVRPTW的基准实例进行的计算测试表明了我们算法的有效性。此外，我们分析了不同时间表结构对运行时间和目标函数值的影响。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号