A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing
A Network Flow Based Heuristic for Bulk Pickup and Delivery Routing
复制标题
DOI：
10.1287/trsc.29.1.45
复制
发表时间：
1995-02
期刊：
影响因子：
--
通讯作者：
M. Fisher;B. Tang;Zhang Zheng
中科院分区：
文献类型：
--
作者：
M. Fisher;B. Tang;Zhang Zheng
我们考虑这样一个问题：必须安排车队来提货和交付一组卡车数量的订单。我们描述了一种基于网络流松弛的新算法，该算法对从订单交付点到订单提货点的空车流施加必要条件。网络流模型提供了一个下限和一个几乎可行的解决方案，可以通过一些简单的启发式方法使其变得可行。我们的算法速度很快，并且在 430 多个测试问题上表现良好，其中包括从上海汽车运输公司获得的许多实际问题。对于实际问题以及使用实际取货和送货点生成的随机问题，该算法始终会生成最优性 1% 以内的解决方案。
We consider a problem in which a fleet of vehicles must be scheduled to pickup and deliver a set of orders in truckload quantities. We describe a new algorithm based on a network flow relaxation which imposes necessary conditions on the flow of empty vehicles from order delivery points to order pickup points. The network flow model provides a lower bound and a nearly feasible solution that can be made feasible with some simple heuristics. Our algorithm is fast and has performed well on a set of more than 430 test problems which include a number of real problems obtained from the Shanghai Truck Transportation Corporation. On real problems and on random problems generated using real pickup and delivery points, the algorithm consistently produces solutions within 1% of optimality.