单车独占性带时间窗口装卸货问题的分析与算法

作者：贾永基; 谷寒雨; 席裕庚

来源：上海交通大学学报, 2005, (03): 409-412.

DOI：10.16183/j.cnki.jsjtu.2005.03.017

• 装卸货问题
• 时间复杂度
• 独占性
• 时间窗口 pickup and delivery problem(PDP)
• time complexity
• exclusive
• time windows

提出了一类广泛存在于运输领域的NP-hard组合优化问题——独占性带时间窗口装卸货(E-PDPTW)问题,给出了它的数学描述,分析了其性质并把问题简化为不对称带时间窗口旅行商问题(TSP),提出了求解单车E-PDPTW问题的两阶段快速算法,其时间复杂度只有O(n3),测试结果表明了该算法的有效性和快速性.

• 出版日期2005
• 单位上海交通大学