摘要
提出了一类广泛存在于运输领域的NP-hard组合优化问题——独占性带时间窗口装卸货(E-PDPTW)问题,给出了它的数学描述,分析了其性质并把问题简化为不对称带时间窗口旅行商问题(TSP),提出了求解单车E-PDPTW问题的两阶段快速算法,其时间复杂度只有O(n3),测试结果表明了该算法的有效性和快速性.
The exclusive pickup and delivery problem with time windows (E-PDPTW), an NP-hard combinatorial optimization problem existed extensively in the transportation domain, was proposed. The mathematical description of this problem was proposed and its properties were analyzed, and then the problem was simplified as an asymmetric traveling salesman problem (TSP) with time windows. A two-phase quick algorithm to solve single vehicle E-PDPTW was proposed, whose time complexity is only O(n3) and the test results indicate the algorithm is effective and quick.
出处
《上海交通大学学报》
EI
CAS
CSCD
北大核心
2005年第3期409-412,共4页
Journal of Shanghai Jiaotong University
基金
国家自然科学基金资助项目(60274013)
关键词
装卸货问题
时间复杂度
独占性
时间窗口
Computational complexity
Mathematical techniques
Time domain analysis
Traveling salesman problem
