关键词: 取送货车辆路径问题, 有效不等式, 改进分支切割算法

Abstract: This paper studies the pickup and delivery with order release dates and flexible time windows in the urban distribution, which consideres the factors such as orders’ pickup positions, orders’ delivery positions, order release dates, flexible time windows and vehicle capacity. A mixed integer linear model is provided to minimize the sum of distribution cost and timeout penalty firstly. Secondly, an improved branch-and-cut algorithm considering a set of valid inequalities and corresponding separation algorithms is designed to solve the model accurately. Finally, we analyze the effect of inequality on the performance of the algorithm, and verify the effectiveness of the algorithm by testing several sets of examples. Moreover, the results also show that appropr; abely reducing the numlet of vehicles and incteasing the loading capacity can effectioely reduce the lost.

Key words: pickup and delivery vehicle routing problem, valid inequalities, improved branch-and-cut