大规模车辆配送/收集问题的求解框架

Solution framework for the large scale vehicle delivery/collection problem

大规模车辆配送/收集问题是供应链末端的日常商品配送和逆向物流前端的废品收集过程中的典型问题,存在着车辆载重、工作时间和车辆服务区域固定等约束,属于扩展的有载重约束的车辆路径问题。该文对该类车辆问题进行了描述和特点分析,提出了一个3阶段的求解框架:采用基于主干道的网格法对客户进行区域化整合;采用车流模型和C-W、3-opt相结合的算法完成客户区域对车辆的分配;采用旅行商问题求解方法对区域内车辆路径进行优化。案例研究的结果证明了该求解框架的实用性和有效性。

The large scale vehicle delivery/collection problem is a typical problem in daily product delivery and waste collection. The constraints of capacity, maximum work time, and fixed vehicle territory make the problem an extension of the so called capacitated vehicle routing problem. The large scale delivery/collection problem was analyzed with a three-phase solution framework. First, the customers were seggregated into districts according to the main road grid system; then the customer districts were assigned to vehicles using the vehicle flow formulation model and the combined saving and 3-option algorithm. Finally, the vehicle routes were determined as a traveling salesman problem. The results of a case study show that the solution framework is practical and efficient.