An efficient two-phase exact algorithm for the automated truck freight transportation problem
An efficient two-phase exact algorithm for the automated truck freight transportation problem
复制标题
自动卡车货运问题的高效两阶段精确算法
DOI：
10.1016/j.cie.2017.04.030
复制
发表时间：
2017
影响因子：
7.9
通讯作者：
Fang Yunfei
中科院分区：
文献类型：
--
作者：
Wu Peng;Chu Feng;Che Ada;Fang Yunfei
最近的一项研究开发了一个整数线性规划和精确算法的自动卡车运输货运问题的车道预留。然而，由于其NP难性质，他们提出的方法变得难以在可接受的时间内解决大规模问题。本文首先通过增加有效的不等式，提出了一种改进的整数线性规划，并指出其几种特殊情况是经典的组合优化问题。在分析性质的基础上，提出了一种新的有效的两阶段精确算法。基准测试和最多700个节点和55个任务的新更大规模实例的计算结果表明，新算法的性能非常优于最先进的算法。
A recent study has developed an integer linear program and an exact algorithm for the automated truck transportation freight problem with lane reservation. However, due to its NP-hard nature, their proposed method becomes difficult to solve large-size problems within acceptable time. In this paper, we firstly present an improved integer linear program by adding valid inequalities and identify that its several special cases are classical combinatorial optimization problems. Based on analyzed properties, a new efficient two-phase exact algorithm is developed. Computational results on benchmark and new larger-size instances with up to 700 nodes and 55 tasks show that the new algorithm outperforms very favorably the state-of-the-art one.