行驶时间和服务时间随机的集配货一体的分批配送车辆路径优化

Optimization on simultaneous pick-up and delivery vehicle routing problem with split delivery and stochastic travel and service time

将铁路物流中心集配货路径问题抽象为行驶时间和服务时间随机的集送货一体的分批配送车辆路径问题进行优化.根据问题特点建立带修正的随机规划模型,对迭代局部搜索算法进行改进,设计允许分批配送的初始解构造算法、局部搜索算法和扰动机制.算例测试证实:分批配送在中等规模和大规模算例中能发挥较好的作用,大部分中等规模和大规模算例都比不允许分批配送时所得到的解更优,部分中等规模和大规模算例车辆数有所减少;配送点数随着算例规模的扩大而增加,但是配送点数占顾客点数的比例却逐步降低;随机因素随机性增加将导致目标函数增大,对分批配送点数的影响不大.

The pick-up and dispatch routing problem in the railway logistics center is considered as the vehicle routing problem with simultaneous pickup-delivery and stochastic travel and service time. A stochastic programming model with recourse is formulated. An improved iterated local search algorithm is designed, in which the split delivery is considered for the construction algorithm, local operators and perturbation mechanism. Three classes of instances, which are named small scale instances, medium scale instances and large scale instances, are tested. Better solutions are obtained because of the split delivery in most of the medium scale instances and large scale instances, where there are reductions for both the cost and the vehicles used in the optimum solution. The ratio of the delivery customers to the customers decreases as the scale of the instances grows, even through there are more split customers in the larger scale problem. With the level of stochastic factors getting high, the value of the objective grows, but the number of split customers are not affected.