Efficient algorithms for optimal pickup-point selection in the selective pickup and delivery problem with time-window constraints
Efficient algorithms for optimal pickup-point selection in the selective pickup and delivery problem with time-window constraints
复制标题
DOI：
10.1299/jamdsm.2020jamdsm0074
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yosuke Takada;Masaru Shimazaki;Yannan Hu;M. Yagiura
中科院分区：
文献类型：
--
作者：
Yosuke Takada;Masaru Shimazaki;Yannan Hu;M. Yagiura
我们研究有时间窗约束的选择性提货和送货问题，即在运力和时间窗约束下，寻找到门店提货并送货给客户的车辆路线，以最小化路线总距离的问题。在本文中，设计一个局部搜索方法，这个问题，我们考虑以下几点：给定的顺序客户在一条路线上，我们确定的皮卡商店和最佳时间访问客户，使总的距离最小化。这就是所谓的最佳取货点问题，是一个子问题的选择性皮卡和交付问题的时间窗口的限制。我们表明，最佳皮卡点问题是NP-困难的一般，然后我们提出的动态规划方法，可以得到的上，下界在线性时间，最优解在伪多项式时间。
We address the selective pickup and delivery problem with time-window constraints, which is a problem of finding vehicle routes that pick up commodities at stores and deliver them to customers so as to minimize the total distance of the routes under capacity and time-window constraints. In this paper, to design a local search method for this problem, we consider the following: Given the order of customers in a route, we determine the pickup stores and optimal times of visiting at customers so that the total distance is minimized. This is called the optimal pickup point problem and is a subproblem of the selective pickup and delivery problem with time-window constraints. We show that the optimal pickup point problem is NP-hard in general, and then we propose dynamic programming methods, which can obtain upper and lower bounds in linear time, and optimal solution in pseudo-polynomial time.