列生成
车辆路径问题
最短路径问题
跳跃式监视
背景(考古学)
数学优化
约束最短路径优先
放松(心理学)
路径(计算)
布线(电子设计自动化)
节点(物理)
K最短路径路由
数学
计算机科学
算法
理论计算机科学
工程类
人工智能
生物
程序设计语言
古生物学
图形
社会心理学
结构工程
计算机网络
心理学
作者
Leonardo Lozano,Daniel Duque,Andrés L. Medaglia
出处
期刊:Transportation Science
[Institute for Operations Research and the Management Sciences]
日期:2016-02-01
卷期号:50 (1): 348-357
被引量:83
标识
DOI:10.1287/trsc.2014.0582
摘要
The elementary shortest path problem with resource constraints (ESPPRC) is an NP-hard problem that often arises in the context of column generation for vehicle routing problems. We propose an exact solution method that relies on implicit enumeration with a novel bounding scheme that dramatically narrows the search space. We embedded our algorithm within a column generation to solve the linear relaxation (root node) of the vehicle routing problem with time windows (VRPTW) and found that the proposed algorithm performs well when compared against state-of-the-art algorithms for the ESPPRC on the well-known Solomon’s test bed for the VRPTW.
科研通智能强力驱动
Strongly Powered by AbleSci AI