Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows

Gonzalo Lera-Romero; Juan J. Miranda Bront; Francisco J. Soulignac

首页> 外文期刊>Networks >Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows

【24h】

Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows

机译：线性边缘成本和标签算法：时间窗口时间依赖的车辆路由问题

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

In this paper we implement a branch-price and cut algorithm for a time dependent vehicle routing problem with time windows in which the goal is to minimize the total route duration. The travel time between two customers is given by a piecewise linear function on the departure time and, thus, it need not remain fixed along the planning horizon. We discuss different alternatives for the implementation of these linear functions within the labeling algorithm applied to solve the pricing problem. We also provide a tailored implementation for one of these alternatives, relying on efficient data structures for storing the labels, and show several strategies to accelerate the algorithm. Computational results show that the proposed techniques are effective and improve the column generation step, solving all instances with 25 customers, 49 of 56 with 50 customers, and many instances with 100 customers. Furthermore, heuristic adaptations are able to find good quality solutions in reasonable computation times.

机译：在本文中，我们实现了一个分支价格和剪切算法的时间依赖的车辆路由问题，其中目标是最小化总路线持续时间。两位客户之间的旅行时间由分段线性功能在出发时间上给出，因此，它不需要沿着规划地平线固定。我们讨论了在应用于解决定价问题的标签算法中实现这些线性函数的不同替代方案。我们还为其中一种替代方案提供量身定制的实现，依赖于用于存储标签的有效数据结构，并显示出几种加速算法的策略。计算结果表明，该技术是有效的，改善列生成步骤，解决了25个客户的所有实例，56名，共50个客户，以及100名客户的许多实例。此外，启发式适应能够在合理的计算时间内找到良好的质量解决方案。

著录项

来源
《Networks》 |2020年第1期|24-53|共30页
作者
Gonzalo Lera-Romero; Juan J. Miranda Bront; Francisco J. Soulignac;
展开▼
作者单位

Instituto de Investigation en Ciencias de la Computation (ICC) CONICET-Universidad de Buenos Aires Buenos Aires Argentina Consejo Nacional de Investigaciones Cientificas y Tecnicas Buenos Aires Argentina;

School of Business Universidad Torcuato Di Tella Buenos Aires Argentina Consejo Nacional de Investigaciones Cientificas y Tecnicas Buenos Aires Argentina;

Consejo Nacional de Investigaciones Cientificas y Tecnicas Buenos Aires Argentina Departamento de Ciencia y Tecnologia Universidad Nacional de Quilmes Buenos Aires Argentina Departamento de Computacion Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires Buenos Aires Argentina;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类
关键词
branch and price; dynamic programming; linear edge costs; time dependent travel times; time windows; vehicle routing problem;

机译：分公司和价格;动态编程;线性边缘成本;时间依赖旅行时间;时间窗;车辆路由问题;

相似文献

外文文献
中文文献
专利

1. A Comparative Study of Proposed Genetic Algorithm-Based Solution with Other Algorithms for Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supply Chain [J] . Suresh Nanda Kumar, Ramasamy Panneerselvam Journal of Service Science and Management . 2015,第6期

机译：电子商务供应链中带有时间窗的时变车辆路径问题的拟议基于遗传算法的解决方案与其他算法的比较研究
2. A hybrid algorithm for time-dependent vehicle routing problem with time windows [J] . Pan Binbin, Zhang Zhenzhen, Lim Andrew Computers & operations research . 2021,第Apra期

机译：时间窗口时间依赖性车辆路由问题的混合算法
3. A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm [J] . Suresh Nanda Kumar, Ramasamy Panneerselvam Intelligent Information Management . 2015,第4期

机译：带有时间窗的遗传算法在电子商务供应商站点取货的时变车辆路径问题
4. An Ant Colony Algorithm for Time-Dependent Vehicle Routing Problem with Time Windows [C] . Umman Mahir Yildirim, Bulent catay International Conference on Operations Research Operations Research . 2009

机译：时间窗口时间依赖性车辆路由问题的蚁群算法
5. A genetic algorithm for the vehicle routing problem with time-dependent travel times. [D] . Jung, Soojung. 2000

机译：具有时变行驶时间的车辆路径问题的遗传算法。
6. A Combination of Genetic Algorithm and Particle Swarm Optimization for Vehicle Routing Problem with Time Windows [O] . Sheng-Hua Xu, Ji-Ping Liu, Fu-Hao Zhang, 2015

机译：遗传算法与粒子群算法相结合求解带时间窗的车辆路径问题
7. A Comparative Study of Proposed Genetic Algorithm-Based Solution with Other Algorithms for Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supply Chain [O] . Suresh Nanda Kumar, Ramasamy Panneerselvam 2015

机译：基于遗传算法的其他算法与时间窗口的时间窗口与电子商务供应链的时间窗口的比较研究

Linear edge costs and labeling algorithms: The case of the time-dependent vehicle routing problem with time windows

摘要

著录项

相似文献

相关主题

期刊订阅